Determinewith 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?
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
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.
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).
  |
LinkBack URL
About LinkBacks
Originally Posted by Petrus 
ty alot emakarov!