Thread: need help with an Eucledian algorthim and gcd involving factorials and large exponets

I have not seen a problem like this before so I would be very grateful for some for some guidance. the problem is to find the gcd(100! + 99, 100! - 99). I know that both numbers are odd and that they can be rewritten as 99(100(98!) +1) and 99(100(98!) - 1) but I can't find my way from here.

the other problem is similar; find the gcd(2^2012 -1, 2^1776 -1)

Thanks for any help!!

thank you for the help! how did you arrive at the answer for the second problem?

Originally Posted by MaxJasper

Part 1:
Almost there - just a bit more and you're done.
First, gcd ( ( 99( 100(98!) + 1) ), ( 99( 100(98!) - 1 ) ) ) = 99 gcd ( (100(98!) +1), (100(98!) - 1) ).
Now look at how close those two numbers are. They're huge yet they differ by 2. Thus only 2 has a prayer to be a common prime divisor. More precisely:
Suppose p is a positive integer that divides both (100(98!) +1) and (100(98!) - 1). Then p divides their difference also, hence p divides 2. Since 100(98!) +1 is odd, p can't be 2. Thus p=1.
Thus gcd ( (100(98!) +1), (100(98!) - 1) ) = 1, and so gcd(100! + 99, 100! - 99) = 99(1) = 99.

Part 2:
MaxJasper has proven that 15 divides both, thus that 15 divides the .
It's still possible that the gcd is larger - some multiple of 15.

Here's a trick: Let b, d >1, everything in sight an integer:
Suppose that d divides
and d divides , with x<y. Then d divides .
Now d divides and d divides , and can repeat the same action again. Notice how the exponets have decreased.
From the Euclidean Algorithm, have y = kx+r, where 0 <= r <= (x-1) and k>0 (since y>x).
From there, you can exploiting this trick to repeatedly subtract off all those x's (do it k times). If x doesn't divide y, you'll then have r not zero, so:
d divides and d divides . But now r<x, so continue the same trick.
Repeating this over and over eventually terminates with either a division, like if x had divided y (or at the next step, if r divides x), or a "remainder 1".
What this allows you to prove, when worked out, is:
Proposition: If d divides and d divides , then d divides .
Rather than work out a proof, I'll run through it step by step for this problem. However, you can see now that gcd(2012, 1776) = gcd(503*4, 16*3*37) = 4.
Thus that proposition says that if d divides , then d divides .
From that and the already shown fact that 15 divides , it follows (reason it out, via primes!) that the gcd = 15.

Here goes: Let d divide both and .
Then d divides .
Since d divides both and , d divides .
Since d divides both and , d divides .
Since d divides both and , d divides .
Since d divides both and , d divides .
Since d divides both and , d divides .
Since d divides both and , d divides .
Since d divides both and , d divides .
Now finally it's subtracted off enough to drop down to 123, under the 236. But still repeat the process with the new lower 123 value:
Since d divides both and , d divides .
A new lower value of 112. Keep going:
Since d divides both and 2^{124} - 1[/tex], d divides .
A new lower value of 12. Keep going:
Since d divides both and , d divides .
Since d divides both and , d divides .
Since d divides both and , d divides .
Since d divides both and , d divides .
Since d divides both and , d divides .
Since d divides both and , d divides .
Since d divides both and , d divides .
Since d divides both and , d divides .
Since d divides both and , d divides .
(You see why the proposition is nice? What a pain!)
Thus if d divides both and , then d divides 15.
Since MaxJasper showed that 15 divides the gcd, together these facts prove that the gcd =15.

I can not thank you enough for the detailed explanation!!