1. ## Euclidean algorithm

Determine with Euclid's algorithm. State also the first two residues and if we start with .

(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?

3. ## 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

4. ## 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.

5. ## Re: Euclidean algorithm

omgg now i get it so always the last one u backwards is the answer of the question :P?

6. ## Re: Euclidean algorithm

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.

7. ## 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!!!

8. ## 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).

9. ## Re: Euclidean algorithm

please post number theory problems in the correct forum.

10. ## Re: Euclidean algorithm

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