# Euclidean algorithm

• Sep 25th 2012, 11:24 AM
Petrus
Euclidean algorithm
Determine https://webwork.math.su.se/webwork2_...01f0294161.png with Euclid's algorithm. State also the first two residues https://webwork.math.su.se/webwork2_...8bfc628b31.png and https://webwork.math.su.se/webwork2_...0e61a50821.png if we start with https://webwork.math.su.se/webwork2_...7c6a066da1.png.

(SGD means GCD)
i need the answer fast if any1 can plz i have solve it this far:
14400=14*1022+92 (r1=92)
1022=92*11+10 (r2=10)
92=9*10+2

backwards
2=9*10-92
10=92*11-1022
92=14*1022-14400

i cant finish this plz any1?
• Sep 25th 2012, 11:35 AM
emakarov
Re: Euclidean algorithm

• Sep 25th 2012, 11:50 AM
Petrus
Re: Euclidean algorithm
the qeustion is GCD(14400,1022)=?
the answe is 2 but i really did not get it how they did get it, did i calculate wrong?
if im honest i havent really understand this Euclidean algorithm
• Sep 25th 2012, 11:55 AM
Deveno
Re: Euclidean algorithm
you've almost finished. you found gcd(14400,1022) = 2 correctly.

now you just need to express 2 as an integral linear combination of 1022 and 14400.

2 = 92 - (9)(10) (we have 2 as a comb. of 10 and 92. we need to dig deeper. by the way, you had this BACKWARDS).

10 = 1022 - (92)(11)(something with 1022 in it! good, we need that! you also had this BACKWARDS, which would have led to the wrong SIGN).

so 2 = 92 - (9)(1022 - (92)(11)) = 92 - (9)(1022) + (99)(92) = (100)(92) - (9)(1022) (now we have 2 as a comb. of 92 and 1022. if only we had 92 as a comb. of 1022 and 14400. oh wait! we do!!!)

92 = 14400 - (14)(1022) (so NOW, we can replace all the 92's in our expression for 2 with 14400 - (14)(1022)). so:

2 = (100)(14400 - (14)(1022)) - (9)(1022) = (100)(14400) - (1400)(1022) - (9)(1022) = (100)(14400) - (1409)(1022).

can this really be true? it's easy enough to check:

(100)(14400) = 1440000
(1409)(1022) = 1439998

yep, the difference is 2.
• Sep 25th 2012, 11:59 AM
Petrus
Re: Euclidean algorithm
omgg now i get it so always the last one u backwards is the answer of the question :P?
• Sep 25th 2012, 12:00 PM
emakarov
Re: Euclidean algorithm
Quote:

Originally Posted by Petrus
the answe is 2 but i really did not get it how they did get it

The result of the Euclid's algorithm is the last nonzero remainder. In your case, the next line after 92 = 9 * 10 + 2 would be 10 = 5 * 2 + 0 with zero remainder.
• Sep 25th 2012, 12:02 PM
Petrus
Re: Euclidean algorithm
yeah thats what i mean :) ty alot emakarov!:) i really had a problem to understand this untill u did reply! ty alot!!!
• Sep 25th 2012, 12:19 PM
Deveno
Re: Euclidean algorithm
i will try to explain the LOGIC behind the euclidean algorithm. to do this, it's easier to work with smaller numbers.

ok, let's say we want to find gcd(14,90).

the first step is to divide 90 by 14, and "keep the quotient and remainder".

90 = (6)(14) + 6

now if something (call it d for now) divides 90 AND 14, then it surely also divides 6 = 90 - (6)(14), so we're looking for a number smaller than 6 (which is a LOT easier than looking for a number smaller than 14).

[EDIT: let me amplify this:

d|90 and d|14 means:

90 = md
14 = nd, for some positive integers m and n.

so 6 = 90 - (6)(14) = md - 6(nd) = (m - 6n)d. this shows that d also divides the DIFFERENCE of 90 and 84 = (6)(14). in this particular example, it turns out that d = 2, which means that m = 45, and n = 7.

indeed 2 divides 6 (90 - 84).

it turns out that another way of defining gcd(a,b) is the SMALLEST positive integer out of ALL possible integer combinations ma+nb, which is in some ways "easier to use" than "factoring" (especially with LARGE integers). this algorithm gives you a way to actually find m and n. ]

what we've done here, is established that gcd(90,14) = gcd(90-84,14) = gcd(6,14). so now we're looking for gcd(6,14). so we divide 14 by 6 (and keep the quotient and remainder, as before):

14 = (2)(6) + 2

again, if something divides 14, and it divides 6, it must surely also divide 14 - (2)(6) = 2. so now we're looking for gcd(2,6), which is even easier.

ok, so we divide 6 by 2:

6 = (3)(2) + 0 <--remainder of 0!!! yay!!! 2 divides 6 evenly. now, we stop, and "back up one step".

since 2 divides 6, gcd(2,6) = 2 (nothing smaller than 2 will ever divide 2, right?). so, "the next-to-last remainder" we get (before we got a remainder of 0) is our gcd.

so, to re-cap:

gcd(14,90) = gcd(6,14) = gcd(2,6) = 2.

check by factoring:

90 = 2*45 = 2*5*9 = 2*3*3*5
14 = 2*7

indeed, the only common factor is 2.

the "key step" in all of this is this simple one:

suppose b > a. then gcd(a,b) = gcd(a,a-b). if fact, if ka < b, then gcd(a,b) = gcd(a,b-ka).

so if we choose k to make b-ka as small as possible (hint: "divide"), by using b = qa + r, where r < a, then we turn a "hard problem" like finding gcd(a,b) into the "easier one" of finding gcd(r,a) = gcd(a,r) = gcd(a,r+qa) = gcd(a,b) (remember r = b - qa, so here our "k" is "q", the quotient, and we already KNOW that:

gcd(a,b) = gcd(a,b-qa) as long as qa < b).
• Sep 25th 2012, 02:30 PM
skeeter
Re: Euclidean algorithm
please post number theory problems in the correct forum.
• Sep 25th 2012, 08:44 PM
Petrus
Re: Euclidean algorithm
Quote:

Originally Posted by skeeter
please post number theory problems in the correct forum.

Sorry im just bad on that:P well im studdy algebra so i guess evrything fr.o.m. My algebra book can be poster here sorry