Revision #133 → #1194 · back to history
addedEuclidean algorithm1760d5a75257
addedSubtraction principle for GCD7b13211f7f7e
addedGCD of 252 and 10532c4e51cda60
addedBézout's identity (stated)43725183a253
addedGreatest common divisor60e29bfa0cd5
addedCoprime numbers1c26ab2ebee2
added6 and 35 are coprimed4f962f29d97
addedGCD divisible by every common divisord5fb60fc2092
addedGeometric visualization of GCDc659ce9116c6
addedGCD via shared prime factors21887e8cb49c
addedGCD of 1386 and 3213b22c19152064
addedGCD as smallest linear combinationab309a0bc388
addedGCD of three or more numbers5e9bdf2f10c2
addedAlgorithm as remainder sequence4d16dcc115f2
addedAlgorithm terminates8ef1e7e0f282
addedGCD of 1071 and 462 (procedure)2e67526bc344
addedDropping the ordering requirement1b74d7e704c6
addedTermination of the algorithm07767bf214c2
addedLast nonzero remainder is the GCDfcfb57189210
addedProperty 1: common divisors of a pair4f5e6e1a5c2c
addedProperty 2: invariance of common divisorsf587b46180d3
addedWorked example gcd(1071, 462)589a21bb6f05
addedTiling visualizationd575a04cd636
addedEuclidean division step4213d2bdb77b
addedExistence and uniqueness of quotient/remainderc9ec829ce7cc
addedLeast absolute remainder variant78fb3942bb56
addedRemainder halving boundc619af3116ac
addedKronecker: fewest stepse0b5d2a72edc
addedMinimal steps iff golden-ratio quotient77723fa4c15e
addedBézout's identity5eea2795d58d
addedComputing s and t by back-substitutionb36510844470
addedGeneralization to Euclidean domainscfd4f7714b30
addedGCD as ideal generator2ea94fdccebf
addedPrincipal ideal and PIDa8f4b701554e
addedMeasuring cups899c565593db
addedExtended Euclidean algorithm9150d68274b6
addedValidity by induction557b53abe43c
addedMatrix method1d4e0612fb6c
addedDeterminant of M5efea8c0b300
addedEuclid's lemmaa78e0dd931a3
addedCoprimality preserved by products1f5f768e6b62
addedUnique factorization into primes8effdab1b3c6
addedDiophantine equationf281e1c8622b
addedSolvability condition3c83597ec3bf
addedNumber of solutionsf9e09fc79db2
addedFinite field5b12991679ee
addedField of 13 numbers7306e8f61043
addedModular multiplicative inversef56986f790f3
addedChinese remainder theorem9a05a5e31c61
addedStern–Brocot tree32c9de2f4899
addedEach rational appears onced90c4d374d55
addedLocating 3/4 in the tree1c2404b2988a
addedCalkin–Wilf tree62338d6da98a
addedRelationship to continued fractions8ae4db043758
addedContinued fraction of 1071/4621b9cb4c5ab49
addedGCD in factorization algorithmsbf1c29c821db
addedReynaud bound5436067b4410
addedFinck bound7750888774e5
addedLamé's theorem1254dcb0e376
addedQuadratic time for large numbers42165466a2de
addedStep count invariant under scalinge6b64abe5598
addedRecursive step-count equation24d4fbf30ce5
addedFibonacci worst casecef3296fde16
addedFive times the digit count4978f5871877
addedFirst average T(a)ae0d48ade778
addedTau average over coprimesae216479baa8
addedPorter's constant917347e7b325
addedThird average Y(n)fc0039010546
addedCost of dividing h-bit numbersa193ddc98554
addedProbability of a given quotientbbbe5f48a1c9
addedQuadratic overall growth5e28729b2ab4
addedEnumerating common divisors is inefficientd62e5f87a2de
addedBinary GCD algorithmed8127070799
addedQuasilinear GCD algorithmsf3112f367da7
addedGeneralization of the algorithm6f9094e7f963
addedCommensurable lengths0d214c91a584
addedTermination iff ratio rational3ebf2ecf5360
addedConvergents are best approximations48405cb32a06
addedGCD of polynomials4f246d1c0a7f
addedLast nonzero remainder is polynomial GCD459541d5d4cb
addedGCD of two quartic polynomials4c584d53dd90
addedGaussian integers6c464b24092f
addedUnique factorization of Gaussian integersc16324626709
addedNorm function on Gaussian integersfb8b268525e7
addedEuclidean domaine0812a03f06f
addedEuclidean function484689d7dbe0
addedUnique factorization in Euclidean domainsb929f0cf05a0
addedEuclidean domain is a UFD34aeed783347
addedEuclidean domain is a PIDbc1e2224401e
addedQuadratic integers66da44e75287
addedNorm-Euclidean quadratic rings4150a92cd373
addedWeinberger's theorema29460a9d68e
addedCommon right divisorad17e2f404ad
addedTwo versions of the algorithmfc33b4210df7
addedBézout's identity (noncommutative)16c0bdb6825e
addedLagrange's four-square theorem8ca410f5fa8d