Rollover and division Encyclopedia card Euclidean rollover and division, also known as the Euclidean algorithm, is an algorithm for finding the greatest common divisor of two positive integers. It is the oldest known algorithm, dating back 3000 years. Simple idea Let two numbers be a and b (b < a), and find their greatest common divisor (a, b) as follows: Divide a by b to get a = bq ..... .r 1 (0 ≤ r). If r1 = 0, then (a, b) = b. If r1 ≠ 0, then divide b by r1 again to get b = r1q..... .r2 (0 ≤ r2). If r2 = 0, then (a, b) = r1; if r2 ≠ 0, then continue to divide r1 by r2,...... and so on until it is divisible. Its last non-zero remainder is (a, b). Principle and its Detailed Proof Before introducing this method, some characteristics of integer divisibility are stated (all numbers below are positive integers and will not be repeated), and we can give the definition of integer divisibility in this way: For two natural numbers a and b, if there exists a positive integer q such that a = bq, then a is divisible by b, b is a factor of a, and a is a multiple of b. If a is a factor of a, then a is a multiple of b. If a is a multiple of b, then a is a multiple of b.　If a is divisible by c and b is also divisible by c, then c is a common factor of a and b (common factorization).　This leads to the following corollary: Corollary 1: If a is divisible by b (a=qb), and if k is a positive integer, then ka is also divisible by b (ka=kqb) Corollary 2: If a is divisible by c (a=hc), and b is also divisible by c (b=tc), then (a±b) is also divisible by c Because: add the two equations: a+b=hc+tc=(h+t)c Similarly the two equations Subtract: a-b = hc-tc = (h-t)c So: (a±b) is also divisible by c Corollary 3. If a is divisible by b (a=qb) and b is also divisible by a (b=ta), then a=b Since: a=qb b=ta a=qta qt=1 Since q, t are positive integers, so t=q=1 Therefore: a=b Euclidean division is used to compute the greatest common factor of two numbers, and is especially useful when the values are large, and is easy to apply on a computer program. The theory is as follows: if q and r are the quotient and remainder of m divided by n, i.e. m=nq+r, then gcd(m,n)=gcd(n,r).　The proof goes like this: Let a=gcd(m,n) and b=gcd(n,r) Proof: ∵ a is the greatest common divisor of m,n, ∴ m is divisible by a and n is also divisible by a, ∴ From Corollary 1: qn is also divisible by a, ∴ From Corollary 2: m-qn is also divisible by a, and ∵ m-qn=r, ∴ r is also divisible by a, i.e., a is a common divisor of n and r (note: not yet). ∵ b is the greatest common divisor of n and r, and a is the common divisor of n and r ∴ a ≤ b, and similarly ∵ b is the greatest common divisor of n, r, ∴ n is divisible by b, and r is also divisible by b, ∴ from Corollary 1: qn is also divisible by b, ∴ from Corollary 2: qn + r is also divisible by b, and ∵ m = qn + r, ∴ m is also divisible by b, i.e., b is a common divisor of m and n. (Note: not yet a greatest common divisor.) (Note: not yet the greatest common divisor) ∵ a is the greatest common divisor of m, n, b is the common divisor of m and n, ∴ b ≤ a, from the above: a ≤ b and b ≤ a at the same time, so we can get a = b, the certificate.　For example, gcd(546, 429) gcd(546, 429) 546=1*429+117 = gcd(429, 117) 429=3*117+78 = gcd(117, 78) 117=1*78+39 = gcd(78, 39) 78=2*39 =39 [edit]Computer algorithms Natural language descriptions Echopping Division determines the greatest common divisor of two positive integers a and b using the following properties: 1. if r is the remainder of a ÷ b, then gcd(a,b) = gcd(b,r) 2. the greatest common divisor of a and a multiple of a is a. Alternatively, this is written as follows: 1. a ÷ b, so that r is the resulting remainder (0 ≤ r < b) If r = 0, the algorithm ends; b is the answer. 2. Reciprocal: set a ← b, so that r is the remainder.　2. Swap: a ← b, b ← r, and return to the first step. Flowchart Flowchart (when type) Pseudo-code This algorithm can be written recursively as follows: function gcd(a, b) { if b<>0 return gcd(b, a mod b); else return a; } c implementation /* Echo-Division (recursive)*/ #include <stdio.h> int Gcd(int a,int b); int main(void ) { int m,n,t; printf("Enter the two figures:"); scanf("%d %d",&m,&n); printf("Gcd:%d\n",Gcd(m,n)); } return 0; } int Gcd(int m,int n)//maximum common divisor { int t; if(m<n) {t = n,n = m,m = t;} if(n == 0) return m; else return Gcd(n,m%n); } pascal implementation function gcd(a,b. integer):integer; begin if b=0 then gcd:=a else gcd:=gcd (b,a mod b); end ; data example where "a mod b" means the remainder of a ÷ b. For example, 123456 and 7890 are the same as 123456 and 7890.　For example, the greatest common divisor of 123456 and 7890 is 6, which can be seen in the following steps: a b a mod b 123456 7890 5106 7890 5106 2784 5106 2784 2322 2784 2322 462 2322 462 12 462 12 6 6 6 6 0 Time Complexity Echo-Division operates at a speed of O(n2) where n is the number of input digits. where n is the number of digits of the input value. Echoing division for special solutions of indeterminate equations Echoing division can be used to find a set of integer solutions to indeterminate equations.　Let the indeterminate equation be a x+b y=c, where a,b,c are integers and lcm(a,b)|c a,b The formula for commutative division is b=q(1) a+r(2) a=q(2) r(2)+r(3) r(2)=q(3) r(3)+r(4) ...　r(n-2)=q(n-1)r(n-1)+r(n) r(n-1)=q(n)r(n) where r(n) is lcm(a,b), and one might as well make b=r(0), a=r(1), and r(n+1)=0 The ith equation is r(i-1)=q(i)r(i)+r(i+1) so r(i+1)=r(i-1)-q(i) ( ri) (*) Using equation (*) we can get r(n)=lcm(a,b) Linear combination of sa+tb=lcm(a,b) about a,b So a set of special solutions of the indeterminate equation a x+b y=c is x=sc/lcm(a,b) y=tc/lcm(a,b) For example: The indeterminate equation is 326x+78y=4 The arithmetic of finding (163,39) is 326=4*78+14 14=326-4*78 78=5*14+8 8=78-5*14 14=1*8+6 6=14-1*8 8=1*6+2 2=8-1*6 6=3*2 so 2 =8-6=8-(14-8) =2*8-14=2*(78-5*14)-14 =2*78-11*14=2*78- 11*(326-4*78) =46*78-11*326 i.e. 2=(-11)*326+46*78 so 4=(-22)*326+72*78 so x=-22,y=72 is a set of special solutions to the indeterminate equation 326x+78y=4 Note: q(i), r(i), subscripts in parentheses, lcm is the method to find the greatest common divisor. 6497 3869 2628 3869 2628 1241 2628 1241 1387 1387 1241 146 1241 146 1095 1241 1095 146 1095 146 949 949 146 803 803 146 657 657 146 511 511 146 365 ~~~~~~~~~~~~146 73 73 The greatest common divisor is 73 3869=73*53 6497=89*73 The least common multiple 73*53*89=344341