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

Re: need help with an Eucledian algorthim and gcd involving factorials and large expo

Re: need help with an Eucledian algorthim and gcd involving factorials and large expo

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

Re: need help with an Eucledian algorthim and gcd involving factorials and large expo

Re: need help with an Eucledian algorthim and gcd involving factorials and large expo

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.

Re: need help with an Eucledian algorthim and gcd involving factorials and large expo

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.

Re: need help with an Eucledian algorthim and gcd involving factorials and large expo

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