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. 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!
2 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. 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.
3 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. 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.
4 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. 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. Continue this processsuccessively, replacingrj 2, rj 3.
5 , 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. We ll do the Euclidean Algorithm in the leftcolumn.
6 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!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.)
7 Hint: First find the gcd.
