Transcription of The Euclidean Algorithm and Multiplicative Inverses
1 1 The Euclidean Algorithm and Multiplicative InversesLecture notes for Access 2011 The Euclidean Algorithm is a set of instructions for finding the greatest common divisorof any two positive integers. Its original importance was probably as a tool in constructionand measurement; the algebraic problem of findinggcd(a, b) is equivalent to the followinggeometric measuring problem: Given two different rulers, say of lengthsaandb, find athird ruler which is as long as possible, but so that you can still use it as a scale on bothof the longer rulers.
2 There s a neat movie demonstration of how the Algorithm worksgeometrically, on theWikipediapage for Euclidean Algorithm . Euclid probably wasn tthinking about finding Multiplicative Inverses in modular arithmetic, but it turns out thatif you look at his Algorithm in reverse, that s exactly what it does!The Euclidean Algorithm makes repeated used of integer division ideas: We know that ifaandbare positive integers, then we may writeab=q+rbwhereqis the quotient, and the remainderrsatisfies 0 r < b. If we clear fractions, thisis the equationa=bq+ really do know that this last equation is possible: starting with (b)(0), then (b)(1)etc.
3 We may subtract increasing multiples ofbfromauntil what remains is a non-negativenumber less thanb. And that s actually the mathematical reason that the integer divisionfact we started with is true. (This procedure is called the division Algorithm .)Here is the algebraic formulation of Euclid s Algorithm ; ituses the division algorithmsuccessively untilgcd(a, b) pops out: theorem 1(The Euclidean Algorithm ).Given two integers 0< b < a, we make a re-peated application of the division Algorithm to obtain a series of division equations, whicheventually terminate with a zero remainder:a=bq1+r1,0< r1< b,b=r1q2+r2,0< r2< r1,r1=r2q3+r3,0< r3< r2, rj 2=rj 1qj+rj,0< rj< rj 1rj 1=rjqj+ greatest common divisorgcd(a, b) ofaandbisrj, the last nonzero remainder inthe division s look at an example of the Euclidean Algorithm in action- it s really quick at findinggcd s when your two integers are large.
4 We should be able to verify these steps with ourscientific calculators:Example the gcd of 42823 and (6) +43696409=4369(1) +20404369=2040(2) +2892040=289(7) +17289=17(17)Thereforegcd(42823,6409) = does the Euclidean Algorithm actually give the gcd? It seems kind of strangethat we can get the gcd of two numbersaandbby looking at the gcd s of the subsequentremainder values. Let s look at successive equations in this process: From the first equationa=bq1+r1, we deduce that since the gcd dividesaandbit must divider1. Similarly inthe next equationb=r1q2+r2, the gcd dividesbandr1, so it must also divider2.
5 Thusthegcd(a, b) divides all the remainders, including the final non-zero one,rj. On the otherhand, by working up from the last equationrj 1=rjqj+1we deduce thatrjdividesrj the second to last equationrjalso dividesrj 2, and working all the way back to thetop we see thatrjdivides bothaandb, so is a divisor. Putting our reasoning together,rjmust be the greatest common divisor! But enough of these explanations, let s try someexercises!Exercise the gcd s of the following pairs of numbers. Save your work becauseyou ll need it 7469 and 24642.
6 2689 and 40013. 2947 and 39974. 1109 and 49993 The fact that we can use the Euclidean Algorithm work in orderto find multiplicativeinverses follows from the following Algorithm : theorem 2( Multiplicative Inverse Algorithm ).Given two integers 0< b < a, consider theEuclidean Algorithm equations which yieldgcd(a, b) =rj. Rewrite all of these equationsexcept the last one, by solving for the remainders:r1=a bq1,r2=b r1q2,r3=r1 r2q3, rj 1=rj 3 rj 2qj 1rj=rj 2 rj , in the last of these equations,rj=rj 2 rj 1qj, replacerj 1with its expressionin terms ofrj 3andrj 2from the equation immediately above it.
7 Continue this processsuccessively, replacingrj 2, rj 3, .., until you obtain the final equationrj=ax+by,withxandyintegers. In the special case thatgcd(a, b) = 1, the integer equation reads1 =ax+ we deduce1 bymodaso that (the residue of)yis the Multiplicative inverse ofb, !Example integersxandyto satisfy42823x+ 6409y= begin by solving our previous equations for the remainders. We have:4369 = 42823 6409(6)2040 = 6409 4369289 = 4369 2040(2)17 = 2040 289(7)Now we do the substitutions starting with that last equationand working backwards andcombining like terms along the way:17 = 2040 289(7) = 2040 (4369 2040(2))(7) = 2040(15) 4369(7)17 = (6409 4369)(15) 4369(7) = 6409(15) 4369(22)17 = 6409(15) (42823 6409(6))(22) = 6409(147) 42823(22)Thereforex= 22, y= the Multiplicative inverse of 8 mod 11, using the Euclidean ll organize our work carefully.
8 We ll do the Euclidean Algorithm in the leftcolumn. It will verify thatgcd(8,11) = 1. Then we ll solve for the remainders in the rightcolumn, before backsolving:11=8(1) +33 = 11 8(1)8=3(2) +22 = 8 3(2)3=2(1) +11 = 3 2(1)2=1(2)Now reverse the process using the equations on the = 3 2(1)1 = 3 (8 3(2))(1) = 3 (8 (3(2)) = 3(3) 81 = (11 8(1))(3) 8 = 11(3) 8(4) = 11(3) + 8( 4)Therefore 1 8( 4) mod 11, or if we prefer a residue value for the multiplicativeinverse,1 8(7) mod careful about the order of the numbers. We do not want to accidentally switch thebolded numbers with the non-bolded numbers!)
9 Exercise the greatest common divisorgof the numbers 1819 and 3587, and thenfind integersxandyto satisfy1819x+ 3587y=gExercise the Multiplicative Inverses of the following:1. 50 mod 7152. 43 mod 64 Exercise the information from the previous exercise, solve thefollowing equationforxand check your 63 mod 12345x 6 mod 54321. Hint: First find the gcd.
