Euclidean algorithm - Revision history

Citation bot: Add: location, issue. | Use this bot. Report bugs. | Suggested by Dominic3203 | Linked from User:Mathbot/Most_linked_math_articles | #UCB_webform_linked 659/1913

2025-04-30T16:35:39Z

Add: location, issue. | Use this bot. Report bugs. | Suggested by Dominic3203 | Linked from User:Mathbot/Most_linked_math_articles | #UCB_webform_linked 659/1913

← Previous revision		Revision as of 16:35, 30 April 2025
Line 471:		Line 471:
	</math>		</math>

	There are ''φ''(''a'') coprime integers less than ''a'', where ''φ'' is [[Euler's totient function]]. This tau average grows smoothly with ''a''<ref>{{harvnb\|Knuth\|1997}}, p. 357</ref><ref>{{cite journal \| last = Tonkov \| first= T. \| year = 1974 \| title = On the average length of finite continued fractions \| journal = Acta Arithmetica \| volume = 26 \| pages = 47–57\| doi= 10.4064/aa-26-1-47-57 \| doi-access = free }}</ref>		There are ''φ''(''a'') coprime integers less than ''a'', where ''φ'' is [[Euler's totient function]]. This tau average grows smoothly with ''a''<ref>{{harvnb\|Knuth\|1997}}, p. 357</ref><ref>{{cite journal \| last = Tonkov \| first= T. \| year = 1974 \| title = On the average length of finite continued fractions \| journal = Acta Arithmetica \| volume = 26 \| issue= 1 \| pages = 47–57\| doi= 10.4064/aa-26-1-47-57 \| doi-access = free }}</ref>

	:<math>\tau(a) = \frac{12}{\pi^2}\ln 2 \ln a + C + O(a^{-1/6-\varepsilon})</math>		:<math>\tau(a) = \frac{12}{\pi^2}\ln 2 \ln a + C + O(a^{-1/6-\varepsilon})</math>
Line 487:		Line 487:
	}}</ref> and equals		}}</ref> and equals
	: <math>C= -\frac 1 2 + \frac{6 \ln 2}{\pi^2}\left(4\gamma -\frac{24}{\pi^2}\zeta'(2) + 3\ln 2 - 2\right) \approx 1.467</math>		: <math>C= -\frac 1 2 + \frac{6 \ln 2}{\pi^2}\left(4\gamma -\frac{24}{\pi^2}\zeta'(2) + 3\ln 2 - 2\right) \approx 1.467</math>
	where {{math\|''γ''}} is the [[Euler–Mascheroni constant]] and {{math\|''ζ''{{′}}}} is the [[derivative]] of the [[Riemann zeta function]].<ref>{{cite journal \| last = Porter \| first = J. W. \| year = 1975 \| title = On a Theorem of Heilbronn \| journal = [[Mathematika]] \| volume = 22 \| pages = 20–28 \| doi = 10.1112/S0025579300004459}}</ref><ref>{{cite journal \| last = Knuth\|first = D. E. \| author-link = Donald Knuth \| year = 1976 \| title = Evaluation of Porter's Constant \| journal = Computers and Mathematics with Applications \| volume = 2 \| pages = 137–139 \| doi = 10.1016/0898-1221(76)90025-0 \| issue = 2\| doi-access = free }}</ref> The leading coefficient (12/π<sup>2</sup>) ln 2 was determined by two independent methods.<ref>{{cite journal \| last = Dixon \| first = J. D. \| year = 1970 \| title = The Number of Steps in the Euclidean Algorithm \| journal = J. Number Theory \| volume = 2 \| pages = 414–422 \| doi = 10.1016/0022-314X(70)90044-2 \| issue = 4\|bibcode = 1970JNT.....2..414D \| doi-access = free }}</ref><ref>{{cite book \| last = Heilbronn \| first = H. A. \| author-link = Hans Heilbronn \| year = 1969 \| chapter = On the Average Length of a Class of Finite Continued Fractions \| title = Number Theory and Analysis \| editor = Paul Turán \| publisher = Plenum \| location = New York \| pages = 87–96 \| lccn = 76016027}}</ref>		where {{math\|''γ''}} is the [[Euler–Mascheroni constant]] and {{math\|''ζ''{{′}}}} is the [[derivative]] of the [[Riemann zeta function]].<ref>{{cite journal \| last = Porter \| first = J. W. \| year = 1975 \| title = On a Theorem of Heilbronn \| journal = [[Mathematika]] \| volume = 22 \| issue = 1 \| pages = 20–28 \| doi = 10.1112/S0025579300004459}}</ref><ref>{{cite journal \| last = Knuth\|first = D. E. \| author-link = Donald Knuth \| year = 1976 \| title = Evaluation of Porter's Constant \| journal = Computers and Mathematics with Applications \| volume = 2 \| pages = 137–139 \| doi = 10.1016/0898-1221(76)90025-0 \| issue = 2\| doi-access = free }}</ref> The leading coefficient (12/π<sup>2</sup>) ln 2 was determined by two independent methods.<ref>{{cite journal \| last = Dixon \| first = J. D. \| year = 1970 \| title = The Number of Steps in the Euclidean Algorithm \| journal = J. Number Theory \| volume = 2 \| pages = 414–422 \| doi = 10.1016/0022-314X(70)90044-2 \| issue = 4\|bibcode = 1970JNT.....2..414D \| doi-access = free }}</ref><ref>{{cite book \| last = Heilbronn \| first = H. A. \| author-link = Hans Heilbronn \| year = 1969 \| chapter = On the Average Length of a Class of Finite Continued Fractions \| title = Number Theory and Analysis \| editor = Paul Turán \| publisher = Plenum \| location = New York \| pages = 87–96 \| lccn = 76016027}}</ref>

	Since the first average can be calculated from the tau average by summing over the divisors ''d'' of ''a''<ref>{{harvnb\|Knuth\|1997}}, p. 354</ref>		Since the first average can be calculated from the tau average by summing over the divisors ''d'' of ''a''<ref>{{harvnb\|Knuth\|1997}}, p. 354</ref>
Line 495:		Line 495:
	: <math> T(a) = \frac 1 a \sum_{d \mid a} \varphi(d) \tau(d)		: <math> T(a) = \frac 1 a \sum_{d \mid a} \varphi(d) \tau(d)
	</math>		</math>
	it can be approximated by the formula<ref name="Norton_1990">{{cite journal \| last = Norton \| first = G. H. \| year = 1990 \| title = On the Asymptotic Analysis of the Euclidean Algorithm \| journal = Journal of Symbolic Computation \| volume = 10 \| pages = 53–58 \| doi = 10.1016/S0747-7171(08)80036-3\| doi-access = free }}</ref>		it can be approximated by the formula<ref name="Norton_1990">{{cite journal \| last = Norton \| first = G. H. \| year = 1990 \| title = On the Asymptotic Analysis of the Euclidean Algorithm \| journal = Journal of Symbolic Computation \| volume = 10 \| issue = 1 \| pages = 53–58 \| doi = 10.1016/S0747-7171(08)80036-3\| doi-access = free }}</ref>
	: <math>T(a) \approx C + \frac{12}{\pi^2} \ln 2\, \biggl({\ln a} - \sum_{d \mid a} \frac{\Lambda(d)} d\biggr)</math>		: <math>T(a) \approx C + \frac{12}{\pi^2} \ln 2\, \biggl({\ln a} - \sum_{d \mid a} \frac{\Lambda(d)} d\biggr)</math>
	where Λ(''d'') is the [[von Mangoldt function\|Mangoldt function]].<ref>{{harvnb\|Knuth\|1997}}, p. 355</ref>		where Λ(''d'') is the [[von Mangoldt function\|Mangoldt function]].<ref>{{harvnb\|Knuth\|1997}}, p. 355</ref>
Line 543:		Line 543:
	One inefficient approach to finding the GCD of two natural numbers ''a'' and ''b'' is to calculate all their common divisors; the GCD is then the largest common divisor. The common divisors can be found by dividing both numbers by successive integers from 2 to the smaller number ''b''. The number of steps of this approach grows linearly with ''b'', or exponentially in the number of digits. Another inefficient approach is to find the prime factors of one or both numbers. As noted [[#Greatest common divisor\|above]], the GCD equals the product of the prime factors shared by the two numbers ''a'' and ''b''.<ref name="Schroeder_21" /> Present methods for [[integer factorization\|prime factorization]] are also inefficient; many modern cryptography systems even rely on that inefficiency.<ref name="Schroeder_216" />		One inefficient approach to finding the GCD of two natural numbers ''a'' and ''b'' is to calculate all their common divisors; the GCD is then the largest common divisor. The common divisors can be found by dividing both numbers by successive integers from 2 to the smaller number ''b''. The number of steps of this approach grows linearly with ''b'', or exponentially in the number of digits. Another inefficient approach is to find the prime factors of one or both numbers. As noted [[#Greatest common divisor\|above]], the GCD equals the product of the prime factors shared by the two numbers ''a'' and ''b''.<ref name="Schroeder_21" /> Present methods for [[integer factorization\|prime factorization]] are also inefficient; many modern cryptography systems even rely on that inefficiency.<ref name="Schroeder_216" />

	The [[binary GCD algorithm]] is an efficient alternative that substitutes division with faster operations by exploiting the [[binary numeral system\|binary]] representation used by computers.<ref>{{harvnb\|Knuth\|1997}}, pp. 321–323</ref><ref>{{cite journal \| last = Stein \| first = J. \| year = 1967 \| title = Computational problems associated with Racah algebra \| journal = Journal of Computational Physics \| volume = 1 \| pages = 397–405 \| doi = 10.1016/0021-9991(67)90047-2 \| issue = 3\| bibcode = 1967JCoPh...1..397S }}</ref> However, this alternative also scales like [[big-O notation\|''O''(''h''²)]]. It is generally faster than the Euclidean algorithm on real computers, even though it scales in the same way.<ref name="Crandall_2001">{{harvnb\|Crandall\|Pomerance\|2001}}, pp. 77–79, 81–85, 425–431</ref> Additional efficiency can be gleaned by examining only the leading digits of the two numbers ''a'' and ''b''.<ref>{{harvnb\|Knuth\|1997}}, p. 328</ref><ref>{{cite journal \| last = Lehmer\|first = D. H.\|author-link=Derrick Henry Lehmer \| year = 1938 \| title = Euclid's Algorithm for Large Numbers \| journal = The American Mathematical Monthly \| volume = 45 \| pages = 227–233 \| doi = 10.2307/2302607 \| jstor = 2302607 \| issue = 4}}</ref> The binary algorithm can be extended to other bases (''k''-ary algorithms),<ref>{{cite journal \| last = Sorenson \|first=J. \| year = 1994 \| title = Two fast GCD algorithms \| journal = J. Algorithms \| volume = 16 \| pages = 110–144 \| doi = 10.1006/jagm.1994.1006}}</ref> with up to fivefold increases in speed.<ref>{{cite journal \| last = Weber \|first=K. \| year = 1995 \| title = The accelerated GCD algorithm \| journal = ACM Trans. Math. Softw. \| volume = 21 \| pages = 111–122 \| doi = 10.1145/200979.201042\|s2cid=14934919 \| doi-access = free }}</ref> [[Lehmer's GCD algorithm]] uses the same general principle as the binary algorithm to speed up GCD computations in arbitrary bases.		The [[binary GCD algorithm]] is an efficient alternative that substitutes division with faster operations by exploiting the [[binary numeral system\|binary]] representation used by computers.<ref>{{harvnb\|Knuth\|1997}}, pp. 321–323</ref><ref>{{cite journal \| last = Stein \| first = J. \| year = 1967 \| title = Computational problems associated with Racah algebra \| journal = Journal of Computational Physics \| volume = 1 \| pages = 397–405 \| doi = 10.1016/0021-9991(67)90047-2 \| issue = 3\| bibcode = 1967JCoPh...1..397S }}</ref> However, this alternative also scales like [[big-O notation\|''O''(''h''²)]]. It is generally faster than the Euclidean algorithm on real computers, even though it scales in the same way.<ref name="Crandall_2001">{{harvnb\|Crandall\|Pomerance\|2001}}, pp. 77–79, 81–85, 425–431</ref> Additional efficiency can be gleaned by examining only the leading digits of the two numbers ''a'' and ''b''.<ref>{{harvnb\|Knuth\|1997}}, p. 328</ref><ref>{{cite journal \| last = Lehmer\|first = D. H.\|author-link=Derrick Henry Lehmer \| year = 1938 \| title = Euclid's Algorithm for Large Numbers \| journal = The American Mathematical Monthly \| volume = 45 \| pages = 227–233 \| doi = 10.2307/2302607 \| jstor = 2302607 \| issue = 4}}</ref> The binary algorithm can be extended to other bases (''k''-ary algorithms),<ref>{{cite journal \| last = Sorenson \|first=J. \| year = 1994 \| title = Two fast GCD algorithms \| journal = J. Algorithms \| volume = 16 \|issue=1 \| pages = 110–144 \| doi = 10.1006/jagm.1994.1006}}</ref> with up to fivefold increases in speed.<ref>{{cite journal \| last = Weber \|first=K. \| year = 1995 \| title = The accelerated GCD algorithm \| journal = ACM Trans. Math. Softw. \| volume = 21 \|issue=1 \| pages = 111–122 \| doi = 10.1145/200979.201042\|s2cid=14934919 \| doi-access = free }}</ref> [[Lehmer's GCD algorithm]] uses the same general principle as the binary algorithm to speed up GCD computations in arbitrary bases.

	A recursive approach for very large integers (with more than 25,000 digits) leads to [[quasilinear time\|quasilinear]] integer GCD algorithms,<ref>{{cite book \| last1 = Aho \| first1 = A. \| author1-link = Alfred Aho \| last2 = Hopcroft \| first2 = J. \| author2-link = John Hopcroft \| last3 = Ullman \| first3 = J. \| author3-link = Jeffrey Ullman \| year = 1974 \| title = The Design and Analysis of Computer Algorithms \| publisher = Addison–Wesley \| location = New York \| pages = [https://archive.org/details/designanalysisof00ahoarich/page/300 300–310] \| isbn = 0-201-00029-6 \| url = https://archive.org/details/designanalysisof00ahoarich/page/300 }}</ref> such as those of Schönhage,<ref>{{cite journal \| last = Schönhage\|first= A. \|author-link=Arnold Schönhage\| title = Schnelle Berechnung von Kettenbruchentwicklungen \|language=de \| journal = Acta Informatica \| volume = 1 \| pages = 139–144 \| doi = 10.1007/BF00289520 \| year = 1971 \| issue = 2\|s2cid= 34561609 }}</ref><ref>{{cite book \| last = Cesari\|first= G. \| year = 1998 \| chapter = Parallel implementation of Schönhage's integer GCD algorithm \| title = Algorithmic Number Theory: Proc. ANTS-III, Portland, OR \| editor = G. Buhler \| publisher = Springer-Verlag \| location = New York \| pages = 64–76\|volume=1423\|series=Lecture Notes in Computer Science}}</ref> and Stehlé and Zimmermann.<ref>{{cite book \| last1 = Stehlé\|first1=D.\|last2=Zimmermann\|first2=P. \| year = 2005 \| chapter = [[Gal's accurate tables]] method revisited \| title = Proceedings of the 17th IEEE Symposium on Computer Arithmetic (ARITH-17) \| publisher = [[IEEE Computer Society Press]] \| location = Los Alamitos, CA}}</ref> These algorithms exploit the 2×2 matrix form of the Euclidean algorithm given [[#Matrix method\|above]]. These quasilinear methods generally scale as {{math\|''O''(''h'' log ''h''{{sup\|2}} log log ''h'').}}<ref name="Crandall_2001" /><ref name="Moller08">{{cite journal \| last = Möller\|first= N. \| title = On Schönhage's algorithm and subquadratic integer gcd computation \| journal = Mathematics of Computation \| volume = 77 \| pages = 589–607 \| doi = 10.1090/S0025-5718-07-02017-0 \| year = 2008 \| url=http://www.lysator.liu.se/~nisse/archive/sgcd.pdf \| issue = 261\| bibcode = 2008MaCom..77..589M \| doi-access = free }}</ref>		A recursive approach for very large integers (with more than 25,000 digits) leads to [[quasilinear time\|quasilinear]] integer GCD algorithms,<ref>{{cite book \| last1 = Aho \| first1 = A. \| author1-link = Alfred Aho \| last2 = Hopcroft \| first2 = J. \| author2-link = John Hopcroft \| last3 = Ullman \| first3 = J. \| author3-link = Jeffrey Ullman \| year = 1974 \| title = The Design and Analysis of Computer Algorithms \| publisher = Addison–Wesley \| location = New York \| pages = [https://archive.org/details/designanalysisof00ahoarich/page/300 300–310] \| isbn = 0-201-00029-6 \| url = https://archive.org/details/designanalysisof00ahoarich/page/300 }}</ref> such as those of Schönhage,<ref>{{cite journal \| last = Schönhage\|first= A. \|author-link=Arnold Schönhage\| title = Schnelle Berechnung von Kettenbruchentwicklungen \|language=de \| journal = Acta Informatica \| volume = 1 \| pages = 139–144 \| doi = 10.1007/BF00289520 \| year = 1971 \| issue = 2\|s2cid= 34561609 }}</ref><ref>{{cite book \| last = Cesari\|first= G. \| year = 1998 \| chapter = Parallel implementation of Schönhage's integer GCD algorithm \| title = Algorithmic Number Theory: Proc. ANTS-III, Portland, OR \| editor = G. Buhler \| publisher = Springer-Verlag \| location = New York \| pages = 64–76\|volume=1423\|series=Lecture Notes in Computer Science}}</ref> and Stehlé and Zimmermann.<ref>{{cite book \| last1 = Stehlé\|first1=D.\|last2=Zimmermann\|first2=P. \| year = 2005 \| chapter = [[Gal's accurate tables]] method revisited \| title = Proceedings of the 17th IEEE Symposium on Computer Arithmetic (ARITH-17) \| publisher = [[IEEE Computer Society Press]] \| location = Los Alamitos, CA}}</ref> These algorithms exploit the 2×2 matrix form of the Euclidean algorithm given [[#Matrix method\|above]]. These quasilinear methods generally scale as {{math\|''O''(''h'' log ''h''{{sup\|2}} log log ''h'').}}<ref name="Crandall_2001" /><ref name="Moller08">{{cite journal \| last = Möller\|first= N. \| title = On Schönhage's algorithm and subquadratic integer gcd computation \| journal = Mathematics of Computation \| volume = 77 \| pages = 589–607 \| doi = 10.1090/S0025-5718-07-02017-0 \| year = 2008 \| url=http://www.lysator.liu.se/~nisse/archive/sgcd.pdf \| issue = 261\| bibcode = 2008MaCom..77..589M \| doi-access = free }}</ref>
Line 617:		Line 617:
	If the function {{mvar\|f}} corresponds to a [[field norm\|norm]] function, such as that used to order the Gaussian integers [[#Gaussian integers\|above]], then the domain is known as ''[[Norm-Euclidean field\|norm-Euclidean]]''. The norm-Euclidean rings of quadratic integers are exactly those where {{mvar\|D}} is one of the values −11, −7, −3, −2, −1, 2, 3, 5, 6, 7, 11, 13, 17, 19, 21, 29, 33, 37, 41, 57, or 73.<ref>{{Harvnb\|Cohn\|1980\|pp=104–110}}</ref><ref>{{cite book \| last = LeVeque \| first = W. J. \| author-link = William J. LeVeque \| title = Topics in Number Theory, Volumes I and II \| publisher = Dover Publications \| location = New York \| year = 2002 \| orig-year = 1956 \| isbn = 978-0-486-42539-9 \| zbl = 1009.11001 \| pages = II:57,81 \| url = https://archive.org/details/topicsinnumberth0000leve }}</ref> The cases {{math\|1=''D'' = −1}} and {{math\|1=''D'' = −3}} yield the [[Gaussian integer]]s and [[Eisenstein integer]]s, respectively.		If the function {{mvar\|f}} corresponds to a [[field norm\|norm]] function, such as that used to order the Gaussian integers [[#Gaussian integers\|above]], then the domain is known as ''[[Norm-Euclidean field\|norm-Euclidean]]''. The norm-Euclidean rings of quadratic integers are exactly those where {{mvar\|D}} is one of the values −11, −7, −3, −2, −1, 2, 3, 5, 6, 7, 11, 13, 17, 19, 21, 29, 33, 37, 41, 57, or 73.<ref>{{Harvnb\|Cohn\|1980\|pp=104–110}}</ref><ref>{{cite book \| last = LeVeque \| first = W. J. \| author-link = William J. LeVeque \| title = Topics in Number Theory, Volumes I and II \| publisher = Dover Publications \| location = New York \| year = 2002 \| orig-year = 1956 \| isbn = 978-0-486-42539-9 \| zbl = 1009.11001 \| pages = II:57,81 \| url = https://archive.org/details/topicsinnumberth0000leve }}</ref> The cases {{math\|1=''D'' = −1}} and {{math\|1=''D'' = −3}} yield the [[Gaussian integer]]s and [[Eisenstein integer]]s, respectively.

	If {{mvar\|f}} is allowed to be any Euclidean function, then the list of possible values of {{mvar\|D}} for which the domain is Euclidean is not yet known.<ref name="Clark_1994">{{cite journal \| last=Clark \| first=D. A. \| year = 1994 \| title = A quadratic field which is Euclidean but not norm-Euclidean \| journal = Manuscripta Mathematica \| volume = 83 \| pages = 327–330 \| doi = 10.1007/BF02567617 \| doi-access=free \| zbl=0817.11047 \| s2cid=895185 }}</ref> The first example of a Euclidean domain that was not norm-Euclidean (with {{math\|1=''D'' = 69}}) was published in 1994.<ref name="Clark_1994" /> In 1973, Weinberger proved that a quadratic integer ring with {{math\|''D'' > 0}} is Euclidean if, and only if, it is a [[principal ideal domain]], provided that the [[generalized Riemann hypothesis]] holds.<ref name="weinberger">{{cite journal \| last = Weinberger \| first = P. \| title = On Euclidean rings of algebraic integers \| journal = Proc. Sympos. Pure Math. \| series = Proceedings of Symposia in Pure Mathematics \| year = 1973 \| volume = 24 \| pages = 321–332\| doi = 10.1090/pspum/024/0337902 \| isbn = 9780821814246 }}</ref>		If {{mvar\|f}} is allowed to be any Euclidean function, then the list of possible values of {{mvar\|D}} for which the domain is Euclidean is not yet known.<ref name="Clark_1994">{{cite journal \| last=Clark \| first=D. A. \| year = 1994 \| title = A quadratic field which is Euclidean but not norm-Euclidean \| journal = Manuscripta Mathematica \| volume = 83 \| issue=1 \| pages = 327–330 \| doi = 10.1007/BF02567617 \| doi-access=free \| zbl=0817.11047 \| s2cid=895185 }}</ref> The first example of a Euclidean domain that was not norm-Euclidean (with {{math\|1=''D'' = 69}}) was published in 1994.<ref name="Clark_1994" /> In 1973, Weinberger proved that a quadratic integer ring with {{math\|''D'' > 0}} is Euclidean if, and only if, it is a [[principal ideal domain]], provided that the [[generalized Riemann hypothesis]] holds.<ref name="weinberger">{{cite journal \| last = Weinberger \| first = P. \| title = On Euclidean rings of algebraic integers \| journal = Proc. Sympos. Pure Math. \| series = Proceedings of Symposia in Pure Mathematics \| year = 1973 \| volume = 24 \| pages = 321–332\| location = Providence, Rhode Island \| doi = 10.1090/pspum/024/0337902 \| isbn = 9780821814246 }}</ref>

	=== Noncommutative rings ===		=== Noncommutative rings ===

David Eppstein: split off reprint isbn

2025-04-20T07:11:06Z

split off reprint isbn

← Previous revision		Revision as of 07:11, 20 April 2025
Line 551:		Line 551:

	=== Rational and real numbers ===		=== Rational and real numbers ===
	Euclid's algorithm can be applied to [[real number]]s, as described by Euclid in Book 10 of his ''[[Euclid's Elements\|Elements]]''. The goal of the algorithm is to identify a real number {{mvar\|g}} such that two given real numbers, {{mvar\|a}} and {{mvar\|b}}, are integer multiples of it: {{math\|1=''a'' = ''mg''}} and {{math\|1=''b'' = ''ng''}}, where {{mvar\|m}} and {{mvar\|n}} are [[integer]]s.<ref name="Weil_1983" /> This identification is equivalent to finding an [[integer relation algorithm\|integer relation]] among the real numbers {{mvar\|a}} and {{mvar\|b}}; that is, it determines integers {{mvar\|s}} and {{mvar\|t}} such that {{math\|1=''sa'' + ''tb'' = 0}}. If such an equation is possible, ''a'' and ''b'' are called commensurable lengths, otherwise they are [[Commensurability (mathematics)\|incommensurable lengths]].<ref>{{cite book \| last1 = Boyer \| first1 = C. B. \| last2 = Merzbach \| first2 = U. C. \| author2-link = Uta Merzbach \| year = 1991 \| title = A History of Mathematics \| edition = 2nd \| publisher = Wiley \| location = New York \| isbn = 0-471-54397-7 \| pages = [https://archive.org/details/historyofmathema00boye/page/116 116–117] \| url = https://archive.org/details/historyofmathema00boye/page/116 }}</ref><ref>{{cite book \| author-link = Florian Cajori\|last=Cajori\|first= F \| year = 1894 \| title = A History of Mathematics \| url = https://archive.org/details/in.ernet.dli.2015.73802\| publisher = Macmillan \| location = New York \| page = [https://archive.org/details/in.ernet.dli.2015.73802/page/n78 70] \| ~~isbn~~ = 0-486-43874-0}}</ref>		Euclid's algorithm can be applied to [[real number]]s, as described by Euclid in Book 10 of his ''[[Euclid's Elements\|Elements]]''. The goal of the algorithm is to identify a real number {{mvar\|g}} such that two given real numbers, {{mvar\|a}} and {{mvar\|b}}, are integer multiples of it: {{math\|1=''a'' = ''mg''}} and {{math\|1=''b'' = ''ng''}}, where {{mvar\|m}} and {{mvar\|n}} are [[integer]]s.<ref name="Weil_1983" /> This identification is equivalent to finding an [[integer relation algorithm\|integer relation]] among the real numbers {{mvar\|a}} and {{mvar\|b}}; that is, it determines integers {{mvar\|s}} and {{mvar\|t}} such that {{math\|1=''sa'' + ''tb'' = 0}}. If such an equation is possible, ''a'' and ''b'' are called commensurable lengths, otherwise they are [[Commensurability (mathematics)\|incommensurable lengths]].<ref>{{cite book \| last1 = Boyer \| first1 = C. B. \| last2 = Merzbach \| first2 = U. C. \| author2-link = Uta Merzbach \| year = 1991 \| title = A History of Mathematics \| edition = 2nd \| publisher = Wiley \| location = New York \| isbn = 0-471-54397-7 \| pages = [https://archive.org/details/historyofmathema00boye/page/116 116–117] \| url = https://archive.org/details/historyofmathema00boye/page/116 }}</ref><ref>{{cite book \| author-link = Florian Cajori\|last=Cajori\|first= F \| year = 1894 \| title = A History of Mathematics \| url = https://archive.org/details/in.ernet.dli.2015.73802\| publisher = Macmillan \| location = New York \| page = [https://archive.org/details/in.ernet.dli.2015.73802/page/n78 70]}} Reprinted, Dover Publications, 2004, {{isbn\|0-486-43874-0}}</ref>

	The real-number Euclidean algorithm differs from its integer counterpart in two respects. First, the remainders {{math\|''r''<sub>''k''</sub>}} are real numbers, although the quotients {{math\|''q''<sub>''k''</sub>}} are integers as before. Second, the algorithm is not guaranteed to end in a finite number {{mvar\|N}} of steps. If it does, the fraction {{math\|''a''/''b''}} is a rational number, i.e., the ratio of two integers		The real-number Euclidean algorithm differs from its integer counterpart in two respects. First, the remainders {{math\|''r''<sub>''k''</sub>}} are real numbers, although the quotients {{math\|''q''<sub>''k''</sub>}} are integers as before. Second, the algorithm is not guaranteed to end in a finite number {{mvar\|N}} of steps. If it does, the fraction {{math\|''a''/''b''}} is a rational number, i.e., the ratio of two integers

DuncanHill: /* Bibliography */ Use archive.org instead of google books, for better access.

2025-04-18T19:40:41Z

Bibliography: Use archive.org instead of google books, for better access.

← Previous revision		Revision as of 19:40, 18 April 2025
Line 662:		Line 662:
	\| year = 2003}}		\| year = 2003}}
	* {{cite book \|last=Cohen \|first=H. \|author-link=Henri Cohen (number theorist) \|year=1993 \|title=A Course in Computational Algebraic Number Theory \|url=https://books.google.com/books?id=hXGr-9l1DXcC \|publisher=Springer-Verlag \|location=New York \|isbn=0-387-55640-0 }}		* {{cite book \|last=Cohen \|first=H. \|author-link=Henri Cohen (number theorist) \|year=1993 \|title=A Course in Computational Algebraic Number Theory \|url=https://books.google.com/books?id=hXGr-9l1DXcC \|publisher=Springer-Verlag \|location=New York \|isbn=0-387-55640-0 }}
	* {{cite book \|last=Cohn \|first=H. \|year=1980 \|title=Advanced Number Theory \|url=https://~~books~~.~~google.com~~/~~books?id=yMGeElJ8M0wC~~ \|publisher=Dover \|location=New York \|isbn=0-486-64023-X}}		* {{cite book \|last=Cohn \|first=H. \|year=1980 \|title=Advanced Number Theory \|url=https://archive.org/details/Cohn_Harvey_-_Advanced_Number_Theory/mode/2up \|publisher=Dover \|location=New York \|isbn=0-486-64023-X}}
	* {{cite book \|last1=Cox \|first1=D. \|author-link1=David A. Cox \|last2=Little \|first2=J. \|last3=O'Shea \|first3=D. \|author-link3=Donal O'Shea \|year=1997 \|title=Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra \|url=https://books.google.com/books?id=7eLkq0wQytAC \|edition=2nd \|publisher = Springer-Verlag \|isbn=0-387-94680-2 }}		* {{cite book \|last1=Cox \|first1=D. \|author-link1=David A. Cox \|last2=Little \|first2=J. \|last3=O'Shea \|first3=D. \|author-link3=Donal O'Shea \|year=1997 \|title=Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra \|url=https://books.google.com/books?id=7eLkq0wQytAC \|edition=2nd \|publisher = Springer-Verlag \|isbn=0-387-94680-2 }}
	* {{cite book \|last1=Crandall \|first1=R. \|author-link1=Richard Crandall \|last2=Pomerance \|first2=C. \|author-link2=Carl Pomerance \| year = 2001 \| title = Prime Numbers: A Computational Perspective \| edition = 1st \| publisher = Springer-Verlag \| location = New York \| isbn = 0-387-94777-9 }}		* {{cite book \|last1=Crandall \|first1=R. \|author-link1=Richard Crandall \|last2=Pomerance \|first2=C. \|author-link2=Carl Pomerance \| year = 2001 \| title = Prime Numbers: A Computational Perspective \| edition = 1st \| publisher = Springer-Verlag \| location = New York \| isbn = 0-387-94777-9 }}

DuncanHill: Fixing harv/sfn reference errors introduced by User:Someguy707. Please install User:Trappist the monk/HarvErrors.js and watchlist :Category:Harv and Sfn no-target errors to help you spot such errors when reading and editing.

2025-04-18T19:39:56Z

Fixing harv/sfn reference errors introduced by User:Someguy707. Please install User:Trappist the monk/HarvErrors.js and watchlist Category:Harv and Sfn no-target errors to help you spot such errors when reading and editing.

← Previous revision		Revision as of 19:39, 18 April 2025
Line 217:		Line 217:
	=== Bézout's identity ===		=== Bézout's identity ===
	{{main\|Bézout's identity}}		{{main\|Bézout's identity}}
	Bézout's identity states that the greatest common divisor {{math\|''g''}} of two integers {{math\|''a''}} and {{math\|''b''}} can be represented as a linear sum of the original two numbers {{math\|''a''}} and {{math\|''b''}}.<ref>{{cite book \| last1 = Jones \|first1=G. A. \| last2 = Jones \| first2 = J. M. \| year = 1998 \| chapter = Bezout's Identity \| title = Elementary Number Theory \| publisher = Springer-Verlag \| location = New York \| pages = 7–11}}</ref> In other words, it is always possible to find integers {{math\|''s''}} and {{math\|''t''}} such that {{math\|1=''g'' = ''sa'' + ''tb''}}.<ref>{{Harvnb\|Rosen\|2000\|p=81}}</ref><ref>{{Harvnb\|Cohn\|~~1962~~\|p=104}}</ref>		Bézout's identity states that the greatest common divisor {{math\|''g''}} of two integers {{math\|''a''}} and {{math\|''b''}} can be represented as a linear sum of the original two numbers {{math\|''a''}} and {{math\|''b''}}.<ref>{{cite book \| last1 = Jones \|first1=G. A. \| last2 = Jones \| first2 = J. M. \| year = 1998 \| chapter = Bezout's Identity \| title = Elementary Number Theory \| publisher = Springer-Verlag \| location = New York \| pages = 7–11}}</ref> In other words, it is always possible to find integers {{math\|''s''}} and {{math\|''t''}} such that {{math\|1=''g'' = ''sa'' + ''tb''}}.<ref>{{Harvnb\|Rosen\|2000\|p=81}}</ref><ref>{{Harvnb\|Cohn\|1980\|p=104}}</ref>

	The integers {{math\|''s''}} and {{math\|''t''}} can be calculated from the quotients {{math\|''q''<sub>0</sub>}}, {{math\|''q''<sub>1</sub>}}, etc. by reversing the order of equations in Euclid's algorithm.<ref>{{Harvnb\|Rosen\|2000\|p=91}}</ref> Beginning with the next-to-last equation, {{math\|''g''}} can be expressed in terms of the quotient {{math\|''q''<sub>''N''−1</sub>}} and the two preceding remainders, {{math\|''r''<sub>''N''−2</sub>}} and {{math\|''r''<sub>''N''−3</sub>}}:		The integers {{math\|''s''}} and {{math\|''t''}} can be calculated from the quotients {{math\|''q''<sub>0</sub>}}, {{math\|''q''<sub>1</sub>}}, etc. by reversing the order of equations in Euclid's algorithm.<ref>{{Harvnb\|Rosen\|2000\|p=91}}</ref> Beginning with the next-to-last equation, {{math\|''g''}} can be expressed in terms of the quotient {{math\|''q''<sub>''N''−1</sub>}} and the two preceding remainders, {{math\|''r''<sub>''N''−2</sub>}} and {{math\|''r''<sub>''N''−3</sub>}}:
Line 597:		Line 597:

	=== Euclidean domains ===		=== Euclidean domains ===
	A set of elements under two [[binary operation]]s, denoted as addition and multiplication, is called a [[Euclidean domain]] if it forms a [[commutative ring]] {{mvar\|R}} and, roughly speaking, if a generalized Euclidean algorithm can be performed on them.<ref>{{Harvnb\|Stark\|1978\|p=290}}</ref><ref>{{Harvnb\|Cohn\|~~1962~~\|pp=104–105}}</ref> The two operations of such a ring need not be the addition and multiplication of ordinary arithmetic; rather, they can be more general, such as the operations of a [[group (mathematics)\|mathematical group]] or [[monoid]]. Nevertheless, these general operations should respect many of the laws governing ordinary arithmetic, such as [[commutative property\|commutativity]], [[associative property\|associativity]] and [[distributive property\|distributivity]].		A set of elements under two [[binary operation]]s, denoted as addition and multiplication, is called a [[Euclidean domain]] if it forms a [[commutative ring]] {{mvar\|R}} and, roughly speaking, if a generalized Euclidean algorithm can be performed on them.<ref>{{Harvnb\|Stark\|1978\|p=290}}</ref><ref>{{Harvnb\|Cohn\|1980\|pp=104–105}}</ref> The two operations of such a ring need not be the addition and multiplication of ordinary arithmetic; rather, they can be more general, such as the operations of a [[group (mathematics)\|mathematical group]] or [[monoid]]. Nevertheless, these general operations should respect many of the laws governing ordinary arithmetic, such as [[commutative property\|commutativity]], [[associative property\|associativity]] and [[distributive property\|distributivity]].

	The generalized Euclidean algorithm requires a ''Euclidean function'', i.e., a mapping {{mvar\|f}} from {{mvar\|R}} into the set of nonnegative integers such that, for any two nonzero elements {{mvar\|a}} and {{mvar\|b}} in {{mvar\|R}}, there exist {{mvar\|q}} and {{mvar\|r}} in {{mvar\|R}} such that {{math\|1=''a'' = ''qb'' + ''r''}} and {{math\|''f''(''r'') < ''f''(''b'')}}.<ref>{{cite book\|title=Concrete Abstract Algebra: From Numbers to Gröbner Bases\|first=Niels\|last=Lauritzen\|publisher=Cambridge University Press\|year=2003\|isbn=9780521534109\|page=130\|url=https://books.google.com/books?id=BdAbcje-TZUC&pg=PA130}}</ref> Examples of such mappings are the absolute value for integers, the degree for [[univariate polynomial]]s, and the norm for Gaussian integers [[#Gaussian integers\|above]].<ref>{{harvtxt\|Lauritzen\|2003}}, p. 132</ref><ref>{{harvtxt\|Lauritzen\|2003}}, p. 161</ref> The basic principle is that each step of the algorithm reduces ''f'' inexorably; hence, if {{mvar\|f}} can be reduced only a finite number of times, the algorithm must stop in a finite number of steps. This principle relies on the [[well-order]]ing property of the non-negative integers, which asserts that every non-empty set of non-negative integers has a smallest member.<ref name="sharpe">{{cite book\|title=Rings and Factorization\|first=David\|last=Sharpe\|publisher=Cambridge University Press\|year=1987\|isbn=9780521337182\|page=[https://archive.org/details/ringsfactorizati0000shar/page/55 55]\|url=https://archive.org/details/ringsfactorizati0000shar\|url-access=registration}}</ref>		The generalized Euclidean algorithm requires a ''Euclidean function'', i.e., a mapping {{mvar\|f}} from {{mvar\|R}} into the set of nonnegative integers such that, for any two nonzero elements {{mvar\|a}} and {{mvar\|b}} in {{mvar\|R}}, there exist {{mvar\|q}} and {{mvar\|r}} in {{mvar\|R}} such that {{math\|1=''a'' = ''qb'' + ''r''}} and {{math\|''f''(''r'') < ''f''(''b'')}}.<ref>{{cite book\|title=Concrete Abstract Algebra: From Numbers to Gröbner Bases\|first=Niels\|last=Lauritzen\|publisher=Cambridge University Press\|year=2003\|isbn=9780521534109\|page=130\|url=https://books.google.com/books?id=BdAbcje-TZUC&pg=PA130}}</ref> Examples of such mappings are the absolute value for integers, the degree for [[univariate polynomial]]s, and the norm for Gaussian integers [[#Gaussian integers\|above]].<ref>{{harvtxt\|Lauritzen\|2003}}, p. 132</ref><ref>{{harvtxt\|Lauritzen\|2003}}, p. 161</ref> The basic principle is that each step of the algorithm reduces ''f'' inexorably; hence, if {{mvar\|f}} can be reduced only a finite number of times, the algorithm must stop in a finite number of steps. This principle relies on the [[well-order]]ing property of the non-negative integers, which asserts that every non-empty set of non-negative integers has a smallest member.<ref name="sharpe">{{cite book\|title=Rings and Factorization\|first=David\|last=Sharpe\|publisher=Cambridge University Press\|year=1987\|isbn=9780521337182\|page=[https://archive.org/details/ringsfactorizati0000shar/page/55 55]\|url=https://archive.org/details/ringsfactorizati0000shar\|url-access=registration}}</ref>
Line 615:		Line 615:
	: <math>\omega = \frac{1 + \sqrt{D}}{2} .</math>		: <math>\omega = \frac{1 + \sqrt{D}}{2} .</math>

	If the function {{mvar\|f}} corresponds to a [[field norm\|norm]] function, such as that used to order the Gaussian integers [[#Gaussian integers\|above]], then the domain is known as ''[[Norm-Euclidean field\|norm-Euclidean]]''. The norm-Euclidean rings of quadratic integers are exactly those where {{mvar\|D}} is one of the values −11, −7, −3, −2, −1, 2, 3, 5, 6, 7, 11, 13, 17, 19, 21, 29, 33, 37, 41, 57, or 73.<ref>{{Harvnb\|Cohn\|~~1962~~\|pp=104–110}}</ref><ref>{{cite book \| last = LeVeque \| first = W. J. \| author-link = William J. LeVeque \| title = Topics in Number Theory, Volumes I and II \| publisher = Dover Publications \| location = New York \| year = 2002 \| orig-year = 1956 \| isbn = 978-0-486-42539-9 \| zbl = 1009.11001 \| pages = II:57,81 \| url = https://archive.org/details/topicsinnumberth0000leve }}</ref> The cases {{math\|1=''D'' = −1}} and {{math\|1=''D'' = −3}} yield the [[Gaussian integer]]s and [[Eisenstein integer]]s, respectively.		If the function {{mvar\|f}} corresponds to a [[field norm\|norm]] function, such as that used to order the Gaussian integers [[#Gaussian integers\|above]], then the domain is known as ''[[Norm-Euclidean field\|norm-Euclidean]]''. The norm-Euclidean rings of quadratic integers are exactly those where {{mvar\|D}} is one of the values −11, −7, −3, −2, −1, 2, 3, 5, 6, 7, 11, 13, 17, 19, 21, 29, 33, 37, 41, 57, or 73.<ref>{{Harvnb\|Cohn\|1980\|pp=104–110}}</ref><ref>{{cite book \| last = LeVeque \| first = W. J. \| author-link = William J. LeVeque \| title = Topics in Number Theory, Volumes I and II \| publisher = Dover Publications \| location = New York \| year = 2002 \| orig-year = 1956 \| isbn = 978-0-486-42539-9 \| zbl = 1009.11001 \| pages = II:57,81 \| url = https://archive.org/details/topicsinnumberth0000leve }}</ref> The cases {{math\|1=''D'' = −1}} and {{math\|1=''D'' = −3}} yield the [[Gaussian integer]]s and [[Eisenstein integer]]s, respectively.

	If {{mvar\|f}} is allowed to be any Euclidean function, then the list of possible values of {{mvar\|D}} for which the domain is Euclidean is not yet known.<ref name="Clark_1994">{{cite journal \| last=Clark \| first=D. A. \| year = 1994 \| title = A quadratic field which is Euclidean but not norm-Euclidean \| journal = Manuscripta Mathematica \| volume = 83 \| pages = 327–330 \| doi = 10.1007/BF02567617 \| doi-access=free \| zbl=0817.11047 \| s2cid=895185 }}</ref> The first example of a Euclidean domain that was not norm-Euclidean (with {{math\|1=''D'' = 69}}) was published in 1994.<ref name="Clark_1994" /> In 1973, Weinberger proved that a quadratic integer ring with {{math\|''D'' > 0}} is Euclidean if, and only if, it is a [[principal ideal domain]], provided that the [[generalized Riemann hypothesis]] holds.<ref name="weinberger">{{cite journal \| last = Weinberger \| first = P. \| title = On Euclidean rings of algebraic integers \| journal = Proc. Sympos. Pure Math. \| series = Proceedings of Symposia in Pure Mathematics \| year = 1973 \| volume = 24 \| pages = 321–332\| doi = 10.1090/pspum/024/0337902 \| isbn = 9780821814246 }}</ref>		If {{mvar\|f}} is allowed to be any Euclidean function, then the list of possible values of {{mvar\|D}} for which the domain is Euclidean is not yet known.<ref name="Clark_1994">{{cite journal \| last=Clark \| first=D. A. \| year = 1994 \| title = A quadratic field which is Euclidean but not norm-Euclidean \| journal = Manuscripta Mathematica \| volume = 83 \| pages = 327–330 \| doi = 10.1007/BF02567617 \| doi-access=free \| zbl=0817.11047 \| s2cid=895185 }}</ref> The first example of a Euclidean domain that was not norm-Euclidean (with {{math\|1=''D'' = 69}}) was published in 1994.<ref name="Clark_1994" /> In 1973, Weinberger proved that a quadratic integer ring with {{math\|''D'' > 0}} is Euclidean if, and only if, it is a [[principal ideal domain]], provided that the [[generalized Riemann hypothesis]] holds.<ref name="weinberger">{{cite journal \| last = Weinberger \| first = P. \| title = On Euclidean rings of algebraic integers \| journal = Proc. Sympos. Pure Math. \| series = Proceedings of Symposia in Pure Mathematics \| year = 1973 \| volume = 24 \| pages = 321–332\| doi = 10.1090/pspum/024/0337902 \| isbn = 9780821814246 }}</ref>

Someguy707: Fixed ISBN / Date incompatibility

2025-04-18T02:15:50Z

Fixed ISBN / Date incompatibility

← Previous revision		Revision as of 02:15, 18 April 2025
Line 662:		Line 662:
	\| year = 2003}}		\| year = 2003}}
	* {{cite book \|last=Cohen \|first=H. \|author-link=Henri Cohen (number theorist) \|year=1993 \|title=A Course in Computational Algebraic Number Theory \|url=https://books.google.com/books?id=hXGr-9l1DXcC \|publisher=Springer-Verlag \|location=New York \|isbn=0-387-55640-0 }}		* {{cite book \|last=Cohen \|first=H. \|author-link=Henri Cohen (number theorist) \|year=1993 \|title=A Course in Computational Algebraic Number Theory \|url=https://books.google.com/books?id=hXGr-9l1DXcC \|publisher=Springer-Verlag \|location=New York \|isbn=0-387-55640-0 }}
	* {{cite book \|last=Cohn \|first=H. \|year=~~1962~~ \|title=Advanced Number Theory \|url=https://books.google.com/books?id=yMGeElJ8M0wC \|publisher=Dover \|location = New York \|isbn=0-486-64023-X }}		* {{cite book \|last=Cohn \|first=H. \|year=1980 \|title=Advanced Number Theory \|url=https://books.google.com/books?id=yMGeElJ8M0wC \|publisher=Dover \|location=New York \|isbn=0-486-64023-X}}
	* {{cite book \|last1=Cox \|first1=D. \|author-link1=David A. Cox \|last2=Little \|first2=J. \|last3=O'Shea \|first3=D. \|author-link3=Donal O'Shea \|year=1997 \|title=Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra \|url=https://books.google.com/books?id=7eLkq0wQytAC \|edition=2nd \|publisher = Springer-Verlag \|isbn=0-387-94680-2 }}		* {{cite book \|last1=Cox \|first1=D. \|author-link1=David A. Cox \|last2=Little \|first2=J. \|last3=O'Shea \|first3=D. \|author-link3=Donal O'Shea \|year=1997 \|title=Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra \|url=https://books.google.com/books?id=7eLkq0wQytAC \|edition=2nd \|publisher = Springer-Verlag \|isbn=0-387-94680-2 }}
	* {{cite book \|last1=Crandall \|first1=R. \|author-link1=Richard Crandall \|last2=Pomerance \|first2=C. \|author-link2=Carl Pomerance \| year = 2001 \| title = Prime Numbers: A Computational Perspective \| edition = 1st \| publisher = Springer-Verlag \| location = New York \| isbn = 0-387-94777-9 }}		* {{cite book \|last1=Crandall \|first1=R. \|author-link1=Richard Crandall \|last2=Pomerance \|first2=C. \|author-link2=Carl Pomerance \| year = 2001 \| title = Prime Numbers: A Computational Perspective \| edition = 1st \| publisher = Springer-Verlag \| location = New York \| isbn = 0-387-94777-9 }}

Remsense: Reverted 1 edit by 2600:100A:B051:BEF8:0:17:43A1:1F01 (talk) to last revision by Mr. X 235528

2025-03-29T15:30:17Z

Reverted 1 edit by 2600:100A:B051:BEF8:0:17:43A1:1F01 (talk) to last revision by Mr. X 235528

← Previous revision		Revision as of 15:30, 29 March 2025
Line 1:		Line 1:
	{{Short description\|Algorithm for computing greatest common divisors}}		{{Short description\|Algorithm for computing greatest common divisors}}
			{{About\|an algorithm for the greatest common divisor\|the mathematics of space\|Euclidean geometry\|other uses of "Euclidean"\|Euclidean (disambiguation)}}
			{{Distinguish\|Euclidean division}}
	{{Featured article}}		{{Featured article}}

	<!-- FOR REASONS OF ACCESSIBILITY TO VISUALLY-IMPAIRED READERS (see [[WP:ACCESS]]), THIS ARTICLE AVOIDS <math> (i.e. LaTeX) MODE, UNLESS IT IS NECESSARY. PLEASE DO NOT ADD <math>-MODE FORMULAE, UNLESS YOU ALSO ADD THE CORRESPONDING ALT TEXT AS WELL, E.G., <math alt="description">. EXAMPLES CAN BE FOUND BELOW, E.G., IN THE "Matrix method" SECTION. -->In mathematics, the '''Euclidean algorithm''', or '''Euclid's algorithm''', is an efficient method for computing the greatest common divisor (GCD) of two integers, the largest number that divides them both without a remainder. It is named after the ancient Greek mathematician Euclid, who first described it in his ''Elements'' ().		<!-- FOR REASONS OF ACCESSIBILITY TO VISUALLY-IMPAIRED READERS (see [[WP:ACCESS]]), THIS ARTICLE AVOIDS <math> (i.e. LaTeX) MODE, UNLESS IT IS NECESSARY. PLEASE DO NOT ADD <math>-MODE FORMULAE, UNLESS YOU ALSO ADD THE CORRESPONDING ALT TEXT AS WELL, E.G., <math alt="description">. EXAMPLES CAN BE FOUND BELOW, E.G., IN THE "Matrix method" SECTION. -->
			[[File: Euclid's algorithm Book VII Proposition 2 3.svg\|upright=1.2\|thumb\|right\|Euclid's method for finding the greatest common divisor (GCD) of two starting lengths BA and DC, both defined to be multiples of a common "unit" length. The length DC being shorter, it is used to "measure" BA, but only once because the remainder EA is less than DC. EA now measures (twice) the shorter length DC, with remainder FC shorter than EA. Then FC measures (three times) length EA. Because there is no remainder, the process ends with FC being the GCD. On the right [[Nicomachus]]'s example with numbers 49 and 21 resulting in their GCD of 7 (derived from Heath 1908:300).]]
⚫	It is an example of an ''algorithm'', a step-by-step procedure for performing a calculation according to well-defined rules,
⚫	and is one of the oldest algorithms in common use. It can be used to reduce ~~fractions~~ to their simplest form, and is a part of many other number-theoretic and cryptographic calculations.

			In [[mathematics]], the '''Euclidean algorithm''',<ref group=note>Some widely used textbooks, such as [[I. N. Herstein]]'s ''Topics in Algebra'' and [[Serge Lang]]'s ''Algebra'', use the term "Euclidean algorithm" to refer to [[Euclidean division]]</ref> or '''Euclid's algorithm''', is an efficient method for computing the [[greatest common divisor]] (GCD) of two [[integers]], the largest number that divides them both without a [[remainder]]. It is named after the ancient Greek [[mathematician]] [[Euclid]], who first described it in [[Euclid's Elements\|his ''Elements'']] ({{circa\|300 BC}}).
⚫	The Euclidean algorithm is based on the principle that the greatest common divisor of two numbers does not change if the larger number is replaced by its difference with the smaller number. For example, {{math\|21}} is the GCD of and (as and , and the same number is also the GCD of and . Since this replacement reduces the larger of the two numbers, repeating this process gives successively smaller pairs of numbers until the two numbers become equal. When that occurs, that number is the GCD of the original two numbers. By reversing the steps or using the extended Euclidean algorithm, the GCD can be expressed as a linear combination of the two original numbers, that is the sum of the two numbers, each multiplied by an integer (for example, ). The fact that the GCD can always be expressed in this way is known as Bézout's identity.
		⚫	It is an example of an ''[[algorithm]]'', a step-by-step procedure for performing a calculation according to well-defined rules,
		⚫	and is one of the oldest algorithms in common use. It can be used to reduce [[Fraction (mathematics)\|fraction]]s to their [[Irreducible fraction\|simplest form]], and is a part of many other number-theoretic and cryptographic calculations.

		⚫	The Euclidean algorithm is based on the principle that the greatest common divisor of two numbers does not change if the larger number is replaced by its difference with the smaller number. For example, {{math\|21}} is the GCD of {{math\|252}} and {{math\|105}} (as {{math\|252 {{=}} 21 × 12}} and {{math\|105 {{=}} 21 × 5)}}, and the same number {{math\|21}} is also the GCD of {{math\|105}} and {{math\|252 − 105 {{=}} 147}}. Since this replacement reduces the larger of the two numbers, repeating this process gives successively smaller pairs of numbers until the two numbers become equal. When that occurs, that number is the GCD of the original two numbers. By [[#Bézout's identity\|reversing the steps]] or using the [[extended Euclidean algorithm]], the GCD can be expressed as a [[linear combination]] of the two original numbers, that is the sum of the two numbers, each multiplied by an [[integer]] (for example, {{math\|21 {{=}} 5 × 105 + (−2) × 252}}). The fact that the GCD can always be expressed in this way is known as [[Bézout's identity]].
⚫	The version of the Euclidean algorithm described above—which follows Euclid's original presentation—may require many subtraction steps to find the GCD when one of the given numbers is much bigger than the other. A more efficient version of the algorithm shortcuts these steps, instead replacing the larger of the two numbers by its remainder when divided by the smaller of the two (with this version, the algorithm stops when reaching a zero remainder). With this improvement, the algorithm never requires more steps than five times the number of digits (base 10) of the smaller integer. This was proven by Gabriel Lamé in 1844 (Lamé's Theorem), and marks the beginning of computational complexity theory. Additional methods for improving the algorithm's efficiency were developed in the 20th century.

		⚫	The version of the Euclidean algorithm described above—which follows Euclid's original presentation—may require many subtraction steps to find the GCD when one of the given numbers is much bigger than the other. A more efficient version of the algorithm shortcuts these steps, instead replacing the larger of the two numbers by its remainder when divided by the smaller of the two (with this version, the algorithm stops when reaching a zero remainder). With this improvement, the algorithm never requires more steps than five times the number of digits (base 10) of the smaller integer. This was proven by [[Gabriel Lamé]] in 1844 ([[Lamé’s Theorem\|Lamé's Theorem]]),<ref>{{cite journal \|last=Lamé \|first=Gabriel \|year=1844 \|title=Note sur la limite du nombre des divisions dans la recherche du plus grand commun diviseur entre deux nombres entiers \|journal=Comptes Rendus des Séances de l'Académie des Sciences \|language=French \|volume=19 \|pages=867–870}}</ref><ref>{{cite journal \|last=Shallit \|first=Jeffrey \|date=1994-11-01 \|title=Origins of the analysis of the Euclidean algorithm \|journal=Historia Mathematica \|language=en \|volume=21 \|issue=4 \|pages=401–419 \|doi=10.1006/hmat.1994.1031 \|issn=0315-0860\|doi-access=free }}</ref> and marks the beginning of [[computational complexity theory]]. Additional methods for improving the algorithm's efficiency were developed in the 20th century.
⚫	The Euclidean algorithm has many theoretical and practical applications. It is used for reducing ~~fractions~~ to their simplest form and for performing division in modular arithmetic. Computations using this algorithm form part of the cryptographic ~~protocols~~ that are used to secure internet communications, and in methods for breaking these cryptosystems by factoring large composite numbers. The Euclidean algorithm may be used to solve Diophantine ~~equations~~, such as finding numbers that satisfy multiple congruences according to the Chinese remainder theorem, to construct continued ~~fractions~~, and to find accurate rational approximations to real numbers. Finally, it can be used as a basic tool for proving theorems in number theory such as Lagrange's four-square theorem and the uniqueness of prime factorizations.

		⚫	The Euclidean algorithm has many theoretical and practical applications. It is used for reducing [[Fraction (mathematics)\|fraction]]s to their [[Irreducible fraction\|simplest form]] and for performing [[Division (mathematics)\|division]] in [[modular arithmetic]]. Computations using this algorithm form part of the [[cryptographic protocol]]s that are used to secure [[internet]] communications, and in methods for breaking these cryptosystems by [[integer factorization\|factoring large composite numbers]]. The Euclidean algorithm may be used to solve [[Diophantine equation]]s, such as finding numbers that satisfy multiple congruences according to the [[Chinese remainder theorem]], to construct [[simple continued fraction\|continued fraction]]s, and to find accurate [[Diophantine approximation\|rational approximations]] to real numbers. Finally, it can be used as a basic tool for proving theorems in [[number theory]] such as [[Lagrange's four-square theorem]] and the [[fundamental theorem of arithmetic\|uniqueness of prime factorizations]].
⚫	The original algorithm was described only for natural numbers and geometric lengths (real numbers), but the algorithm was generalized in the 19th century to other types of numbers, such as Gaussian ~~integers~~ and ~~polynomials~~ of one variable. This led to modern abstract ~~algebraic~~ notions such as Euclidean ~~domains~~.

		⚫	The original algorithm was described only for natural numbers and geometric lengths (real numbers), but the algorithm was generalized in the 19th century to other types of numbers, such as [[Gaussian integer]]s and [[polynomial]]s of one variable. This led to modern [[abstract algebra]]ic notions such as [[Euclidean domain]]s.

	== Background: greatest common divisor ==		== Background: greatest common divisor ==

2600:100A:B051:BEF8:0:17:43A1:1F01: Fixed all problems

2025-03-29T15:26:12Z

Fixed all problems

← Previous revision		Revision as of 15:26, 29 March 2025
Line 1:		Line 1:
	{{Short description\|Algorithm for computing greatest common divisors}}		{{Short description\|Algorithm for computing greatest common divisors}}
	{{About\|an algorithm for the greatest common divisor\|the mathematics of space\|Euclidean geometry\|other uses of "Euclidean"\|Euclidean (disambiguation)}}
	{{Distinguish\|Euclidean division}}
	{{Featured article}}		{{Featured article}}

	<!-- FOR REASONS OF ACCESSIBILITY TO VISUALLY-IMPAIRED READERS (see [[WP:ACCESS]]), THIS ARTICLE AVOIDS <math> (i.e. LaTeX) MODE, UNLESS IT IS NECESSARY. PLEASE DO NOT ADD <math>-MODE FORMULAE, UNLESS YOU ALSO ADD THE CORRESPONDING ALT TEXT AS WELL, E.G., <math alt="description">. EXAMPLES CAN BE FOUND BELOW, E.G., IN THE "Matrix method" SECTION. -->		<!-- FOR REASONS OF ACCESSIBILITY TO VISUALLY-IMPAIRED READERS (see [[WP:ACCESS]]), THIS ARTICLE AVOIDS <math> (i.e. LaTeX) MODE, UNLESS IT IS NECESSARY. PLEASE DO NOT ADD <math>-MODE FORMULAE, UNLESS YOU ALSO ADD THE CORRESPONDING ALT TEXT AS WELL, E.G., <math alt="description">. EXAMPLES CAN BE FOUND BELOW, E.G., IN THE "Matrix method" SECTION. -->In mathematics, the '''Euclidean algorithm''', or '''Euclid's algorithm''', is an efficient method for computing the greatest common divisor (GCD) of two integers, the largest number that divides them both without a remainder. It is named after the ancient Greek mathematician Euclid, who first described it in his ''Elements'' ().
		⚫	It is an example of an ''algorithm'', a step-by-step procedure for performing a calculation according to well-defined rules,
	[[File: Euclid's algorithm Book VII Proposition 2 3.svg\|upright=1.2\|thumb\|right\|Euclid's method for finding the greatest common divisor (GCD) of two starting lengths BA and DC, both defined to be multiples of a common "unit" length. The length DC being shorter, it is used to "measure" BA, but only once because the remainder EA is less than DC. EA now measures (twice) the shorter length DC, with remainder FC shorter than EA. Then FC measures (three times) length EA. Because there is no remainder, the process ends with FC being the GCD. On the right [[Nicomachus]]'s example with numbers 49 and 21 resulting in their GCD of 7 (derived from Heath 1908:300).]]
		⚫	and is one of the oldest algorithms in common use. It can be used to reduce fractions to their simplest form, and is a part of many other number-theoretic and cryptographic calculations.

		⚫	The Euclidean algorithm is based on the principle that the greatest common divisor of two numbers does not change if the larger number is replaced by its difference with the smaller number. For example, {{math\|21}} is the GCD of and (as and , and the same number is also the GCD of and . Since this replacement reduces the larger of the two numbers, repeating this process gives successively smaller pairs of numbers until the two numbers become equal. When that occurs, that number is the GCD of the original two numbers. By reversing the steps or using the extended Euclidean algorithm, the GCD can be expressed as a linear combination of the two original numbers, that is the sum of the two numbers, each multiplied by an integer (for example, ). The fact that the GCD can always be expressed in this way is known as Bézout's identity.
	In [[mathematics]], the '''Euclidean algorithm''',<ref group=note>Some widely used textbooks, such as [[I. N. Herstein]]'s ''Topics in Algebra'' and [[Serge Lang]]'s ''Algebra'', use the term "Euclidean algorithm" to refer to [[Euclidean division]]</ref> or '''Euclid's algorithm''', is an efficient method for computing the [[greatest common divisor]] (GCD) of two [[integers]], the largest number that divides them both without a [[remainder]]. It is named after the ancient Greek [[mathematician]] [[Euclid]], who first described it in [[Euclid's Elements\|his ''Elements'']] ({{circa\|300 BC}}).
⚫	It is an example of an ''[[algorithm]]'', a step-by-step procedure for performing a calculation according to well-defined rules,
⚫	and is one of the oldest algorithms in common use. It can be used to reduce ~~[[Fraction (mathematics)\|fraction]]s~~ to their ~~[[Irreducible fraction\|~~simplest form]], and is a part of many other number-theoretic and cryptographic calculations.

		⚫	The version of the Euclidean algorithm described above—which follows Euclid's original presentation—may require many subtraction steps to find the GCD when one of the given numbers is much bigger than the other. A more efficient version of the algorithm shortcuts these steps, instead replacing the larger of the two numbers by its remainder when divided by the smaller of the two (with this version, the algorithm stops when reaching a zero remainder). With this improvement, the algorithm never requires more steps than five times the number of digits (base 10) of the smaller integer. This was proven by Gabriel Lamé in 1844 (Lamé's Theorem), and marks the beginning of computational complexity theory. Additional methods for improving the algorithm's efficiency were developed in the 20th century.
⚫	The Euclidean algorithm is based on the principle that the greatest common divisor of two numbers does not change if the larger number is replaced by its difference with the smaller number. For example, {{math\|21}} is the GCD of ~~{{math\|252}}~~ and ~~{{math\|105}}~~ (as ~~{{math\|252 {{=}} 21 × 12}}~~ and ~~{{math\|105 {{=}} 21 × 5)}}~~, and the same number ~~{{math\|21}}~~ is also the GCD of ~~{{math\|105}}~~ and ~~{{math\|252 − 105 {{=}} 147}}~~. Since this replacement reduces the larger of the two numbers, repeating this process gives successively smaller pairs of numbers until the two numbers become equal. When that occurs, that number is the GCD of the original two numbers. By ~~[[#Bézout's identity\|~~reversing the steps]] or using the [[extended Euclidean algorithm]], the GCD can be expressed as a [[linear combination]] of the two original numbers, that is the sum of the two numbers, each multiplied by an [[integer]] (for example, ~~{{math\|21 {{=}} 5 × 105 + (−2) × 252}}~~). The fact that the GCD can always be expressed in this way is known as [[Bézout's identity]].

		⚫	The Euclidean algorithm has many theoretical and practical applications. It is used for reducing fractions to their simplest form and for performing division in modular arithmetic. Computations using this algorithm form part of the cryptographic protocols that are used to secure internet communications, and in methods for breaking these cryptosystems by factoring large composite numbers. The Euclidean algorithm may be used to solve Diophantine equations, such as finding numbers that satisfy multiple congruences according to the Chinese remainder theorem, to construct continued fractions, and to find accurate rational approximations to real numbers. Finally, it can be used as a basic tool for proving theorems in number theory such as Lagrange's four-square theorem and the uniqueness of prime factorizations.
⚫	The version of the Euclidean algorithm described above—which follows Euclid's original presentation—may require many subtraction steps to find the GCD when one of the given numbers is much bigger than the other. A more efficient version of the algorithm shortcuts these steps, instead replacing the larger of the two numbers by its remainder when divided by the smaller of the two (with this version, the algorithm stops when reaching a zero remainder). With this improvement, the algorithm never requires more steps than five times the number of digits (base 10) of the smaller integer. This was proven by [[Gabriel Lamé]] in 1844 (~~[[Lamé’s Theorem\|~~Lamé's Theorem]]),<ref>{{cite journal \|last=Lamé \|first=Gabriel \|year=1844 \|title=Note sur la limite du nombre des divisions dans la recherche du plus grand commun diviseur entre deux nombres entiers \|journal=Comptes Rendus des Séances de l'Académie des Sciences \|language=French \|volume=19 \|pages=867–870}}</ref><ref>{{cite journal \|last=Shallit \|first=Jeffrey \|date=1994-11-01 \|title=Origins of the analysis of the Euclidean algorithm \|journal=Historia Mathematica \|language=en \|volume=21 \|issue=4 \|pages=401–419 \|doi=10.1006/hmat.1994.1031 \|issn=0315-0860\|doi-access=free }}</ref> and marks the beginning of [[computational complexity theory]]. Additional methods for improving the algorithm's efficiency were developed in the 20th century.

		⚫	The original algorithm was described only for natural numbers and geometric lengths (real numbers), but the algorithm was generalized in the 19th century to other types of numbers, such as Gaussian integers and polynomials of one variable. This led to modern abstract algebraic notions such as Euclidean domains.
⚫	The Euclidean algorithm has many theoretical and practical applications. It is used for reducing ~~[[Fraction (mathematics)\|fraction]]s~~ to their ~~[[Irreducible fraction\|~~simplest form]] and for performing ~~[[Division (mathematics)\|~~division]] in [[modular arithmetic]]. Computations using this algorithm form part of the [[cryptographic ~~protocol]]s~~ that are used to secure [[internet]] communications, and in methods for breaking these cryptosystems by ~~[[integer factorization\|~~factoring large composite numbers]]. The Euclidean algorithm may be used to solve [[Diophantine ~~equation]]s~~, such as finding numbers that satisfy multiple congruences according to the [[Chinese remainder theorem]], to construct ~~[[simple~~ continued ~~fraction\|continued fraction]]s~~, and to find accurate ~~[[Diophantine approximation\|~~rational approximations]] to real numbers. Finally, it can be used as a basic tool for proving theorems in [[number theory]] such as [[Lagrange's four-square theorem]] and the ~~[[fundamental theorem of arithmetic\|~~uniqueness of prime factorizations]].

⚫	The original algorithm was described only for natural numbers and geometric lengths (real numbers), but the algorithm was generalized in the 19th century to other types of numbers, such as [[Gaussian ~~integer]]s~~ and ~~[[polynomial]]s~~ of one variable. This led to modern [[abstract ~~algebra]]ic~~ notions such as [[Euclidean ~~domain]]s~~.

	== Background: greatest common divisor ==		== Background: greatest common divisor ==

Mr. X 235528: /* Noncommutative rings */

2025-02-03T20:45:57Z

Noncommutative rings

← Previous revision		Revision as of 20:45, 3 February 2025
Line 622:		Line 622:
	The Euclidean algorithm may be applied to some noncommutative rings such as the set of [[Hurwitz quaternion]]s.<ref name="stillwell151-152">{{Harvnb\|Stillwell\|2003\|pp=151–152}}</ref><ref name=bgv>{{harvtxt\|Bueso\|Gómez-Torrecillas\|Verschoren\|2003}}; see pp. 37-38 for non-commutative extensions of the Euclidean algorithm and Corollary 4.35, p. 40, for more examples of noncommutative rings to which they apply.</ref> Let {{mvar\|α}} and {{mvar\|β}} represent two elements from such a ring. They have a common right divisor {{mvar\|δ}} if {{math\|1=''α'' = ''ξδ''}} and {{math\|1=''β'' = ''ηδ''}} for some choice of {{mvar\|ξ}} and {{mvar\|η}} in the ring. Similarly, they have a common left divisor if {{math\|1=''α'' = ''dξ''}} and {{math\|1=''β'' = ''dη''}} for some choice of {{mvar\|ξ}} and {{mvar\|η}} in the ring. Since multiplication is not commutative, there are two versions of the Euclidean algorithm, one for right divisors and one for left divisors.<ref name="stillwell151-152"/><ref name=bgv/> Choosing the right divisors, the first step in finding the {{math\|gcd(''α'', ''β'')}} by the Euclidean algorithm can be written		The Euclidean algorithm may be applied to some noncommutative rings such as the set of [[Hurwitz quaternion]]s.<ref name="stillwell151-152">{{Harvnb\|Stillwell\|2003\|pp=151–152}}</ref><ref name=bgv>{{harvtxt\|Bueso\|Gómez-Torrecillas\|Verschoren\|2003}}; see pp. 37-38 for non-commutative extensions of the Euclidean algorithm and Corollary 4.35, p. 40, for more examples of noncommutative rings to which they apply.</ref> Let {{mvar\|α}} and {{mvar\|β}} represent two elements from such a ring. They have a common right divisor {{mvar\|δ}} if {{math\|1=''α'' = ''ξδ''}} and {{math\|1=''β'' = ''ηδ''}} for some choice of {{mvar\|ξ}} and {{mvar\|η}} in the ring. Similarly, they have a common left divisor if {{math\|1=''α'' = ''dξ''}} and {{math\|1=''β'' = ''dη''}} for some choice of {{mvar\|ξ}} and {{mvar\|η}} in the ring. Since multiplication is not commutative, there are two versions of the Euclidean algorithm, one for right divisors and one for left divisors.<ref name="stillwell151-152"/><ref name=bgv/> Choosing the right divisors, the first step in finding the {{math\|gcd(''α'', ''β'')}} by the Euclidean algorithm can be written
	: <math>\rho_0 = \alpha - \psi_0\beta = (\xi - \psi_0\eta)\delta,</math>		: <math>\rho_0 = \alpha - \psi_0\beta = (\xi - \psi_0\eta)\delta,</math>
	where {{math\|''ψ''<sub>0</sub>}} represents the quotient and {{math\|''ρ''<sub>0</sub>}} the remainder. Here the ~~quotent~~ and remainder are chosen so that (if nonzero) the remainder has {{math\|''N''(''ρ''<sub>0</sub>) < ''N''(''β'')}} for a "Euclidean function" ''N'' defined analogously to the Euclidean functions of [[Euclidean domain]]s in the non-commutative case.<ref name=bgv/> This equation shows that any common right divisor of {{mvar\|α}} and {{mvar\|β}} is likewise a common divisor of the remainder {{math\|''ρ''<sub>0</sub>}}. The analogous equation for the left divisors would be		where {{math\|''ψ''<sub>0</sub>}} represents the quotient and {{math\|''ρ''<sub>0</sub>}} the remainder. Here the quotient and remainder are chosen so that (if nonzero) the remainder has {{math\|''N''(''ρ''<sub>0</sub>) < ''N''(''β'')}} for a "Euclidean function" ''N'' defined analogously to the Euclidean functions of [[Euclidean domain]]s in the non-commutative case.<ref name=bgv/> This equation shows that any common right divisor of {{mvar\|α}} and {{mvar\|β}} is likewise a common divisor of the remainder {{math\|''ρ''<sub>0</sub>}}. The analogous equation for the left divisors would be
	: <math>\rho_0 = \alpha - \beta\psi_0 = \delta(\xi - \eta\psi_0).</math>		: <math>\rho_0 = \alpha - \beta\psi_0 = \delta(\xi - \eta\psi_0).</math>

Quondum: further fmt

2025-01-12T02:20:46Z

further fmt

Show changes

Quondum: fmt (replacing nbsp inside {{math}} with sp, partially adding {{math}} to some plaintext formulae for more uniformity); IMO this article is way too big to qualify as a featured article

2025-01-11T17:17:09Z

fmt (replacing nbsp inside {{math}} with sp, partially adding {{math}} to some plaintext formulae for more uniformity); IMO this article is way too big to qualify as a featured article

Show changes

← Previous revision		Revision as of 19:40, 18 April 2025
Line 662:		Line 662:
	\| year = 2003}}		\| year = 2003}}
	* {{cite book \|last=Cohen \|first=H. \|author-link=Henri Cohen (number theorist) \|year=1993 \|title=A Course in Computational Algebraic Number Theory \|url=https://books.google.com/books?id=hXGr-9l1DXcC \|publisher=Springer-Verlag \|location=New York \|isbn=0-387-55640-0 }}		* {{cite book \|last=Cohen \|first=H. \|author-link=Henri Cohen (number theorist) \|year=1993 \|title=A Course in Computational Algebraic Number Theory \|url=https://books.google.com/books?id=hXGr-9l1DXcC \|publisher=Springer-Verlag \|location=New York \|isbn=0-387-55640-0 }}
	* {{cite book \|last=Cohn \|first=H. \|year=1980 \|title=Advanced Number Theory \|url=https://~~books~~.~~google.com~~/~~books?id=yMGeElJ8M0wC~~ \|publisher=Dover \|location=New York \|isbn=0-486-64023-X}}		* {{cite book \|last=Cohn \|first=H. \|year=1980 \|title=Advanced Number Theory \|url=https://archive.org/details/Cohn_Harvey_-_Advanced_Number_Theory/mode/2up \|publisher=Dover \|location=New York \|isbn=0-486-64023-X}}
	* {{cite book \|last1=Cox \|first1=D. \|author-link1=David A. Cox \|last2=Little \|first2=J. \|last3=O'Shea \|first3=D. \|author-link3=Donal O'Shea \|year=1997 \|title=Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra \|url=https://books.google.com/books?id=7eLkq0wQytAC \|edition=2nd \|publisher = Springer-Verlag \|isbn=0-387-94680-2 }}		* {{cite book \|last1=Cox \|first1=D. \|author-link1=David A. Cox \|last2=Little \|first2=J. \|last3=O'Shea \|first3=D. \|author-link3=Donal O'Shea \|year=1997 \|title=Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra \|url=https://books.google.com/books?id=7eLkq0wQytAC \|edition=2nd \|publisher = Springer-Verlag \|isbn=0-387-94680-2 }}
	* {{cite book \|last1=Crandall \|first1=R. \|author-link1=Richard Crandall \|last2=Pomerance \|first2=C. \|author-link2=Carl Pomerance \| year = 2001 \| title = Prime Numbers: A Computational Perspective \| edition = 1st \| publisher = Springer-Verlag \| location = New York \| isbn = 0-387-94777-9 }}		* {{cite book \|last1=Crandall \|first1=R. \|author-link1=Richard Crandall \|last2=Pomerance \|first2=C. \|author-link2=Carl Pomerance \| year = 2001 \| title = Prime Numbers: A Computational Perspective \| edition = 1st \| publisher = Springer-Verlag \| location = New York \| isbn = 0-387-94777-9 }}

← Previous revision		Revision as of 02:15, 18 April 2025
Line 662:		Line 662:
	\| year = 2003}}		\| year = 2003}}
	* {{cite book \|last=Cohen \|first=H. \|author-link=Henri Cohen (number theorist) \|year=1993 \|title=A Course in Computational Algebraic Number Theory \|url=https://books.google.com/books?id=hXGr-9l1DXcC \|publisher=Springer-Verlag \|location=New York \|isbn=0-387-55640-0 }}		* {{cite book \|last=Cohen \|first=H. \|author-link=Henri Cohen (number theorist) \|year=1993 \|title=A Course in Computational Algebraic Number Theory \|url=https://books.google.com/books?id=hXGr-9l1DXcC \|publisher=Springer-Verlag \|location=New York \|isbn=0-387-55640-0 }}
	* {{cite book \|last=Cohn \|first=H. \|year=~~1962~~ \|title=Advanced Number Theory \|url=https://books.google.com/books?id=yMGeElJ8M0wC \|publisher=Dover \|location = New York \|isbn=0-486-64023-X }}		* {{cite book \|last=Cohn \|first=H. \|year=1980 \|title=Advanced Number Theory \|url=https://books.google.com/books?id=yMGeElJ8M0wC \|publisher=Dover \|location=New York \|isbn=0-486-64023-X}}
	* {{cite book \|last1=Cox \|first1=D. \|author-link1=David A. Cox \|last2=Little \|first2=J. \|last3=O'Shea \|first3=D. \|author-link3=Donal O'Shea \|year=1997 \|title=Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra \|url=https://books.google.com/books?id=7eLkq0wQytAC \|edition=2nd \|publisher = Springer-Verlag \|isbn=0-387-94680-2 }}		* {{cite book \|last1=Cox \|first1=D. \|author-link1=David A. Cox \|last2=Little \|first2=J. \|last3=O'Shea \|first3=D. \|author-link3=Donal O'Shea \|year=1997 \|title=Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra \|url=https://books.google.com/books?id=7eLkq0wQytAC \|edition=2nd \|publisher = Springer-Verlag \|isbn=0-387-94680-2 }}
	* {{cite book \|last1=Crandall \|first1=R. \|author-link1=Richard Crandall \|last2=Pomerance \|first2=C. \|author-link2=Carl Pomerance \| year = 2001 \| title = Prime Numbers: A Computational Perspective \| edition = 1st \| publisher = Springer-Verlag \| location = New York \| isbn = 0-387-94777-9 }}		* {{cite book \|last1=Crandall \|first1=R. \|author-link1=Richard Crandall \|last2=Pomerance \|first2=C. \|author-link2=Carl Pomerance \| year = 2001 \| title = Prime Numbers: A Computational Perspective \| edition = 1st \| publisher = Springer-Verlag \| location = New York \| isbn = 0-387-94777-9 }}