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

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

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

$\text{GCD}[100!+99,100!-99] = 99$

$\text{GCD}\left[2^{2012}-1,2^{1776}-1\right] = 15$

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

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

Originally Posted by MaxJasper
$\text{GCD}[100!+99,100!-99] = 99$

$\text{GCD}\left[2^{2012}-1,2^{1776}-1\right] = 15$
$2012=2^2*503$
$1776=2^4*3*37$

$2^{2012}=2^{2+2010}=4*2^{2010}=1 \bmod 3$
$2^{1776}=2^{2+1774}=4*2^{1774}= 1 \bmod 3$

$2^{2012}=2^{4+2008}=16*2^{2008}= 1 \bmod 5$
$2^{1776}=2^{4+1772}=16*2^{1772}=1 \bmod 5$

$2^{2012}-1=0 \bmod 3 = 0 \bmod 5 = 0 \bmod 15$
$2^{1776}-1 = 0 \bmod 3 = 0 \bmod 5 = 0 \bmod 15$

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

6. ## 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 $gcd(2^{2012} - 1, 2^{1776} - 1)$.
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
$(b^x-1)$ and d divides $(b^y-1)$, with x<y. Then d divides $(b^y-1)-b^{y-x}(b^x-1) = b^{y-x}-1$.
Now d divides $(b^x-1)$ and d divides $(b^{y-x}-1)$, 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 $(b^r-1)$ and d divides $(b^x-1)$. 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 $(b^x-1)$ and d divides $(b^y-1)$, then d divides $(b^{gcd(x,y)}-1)$.
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 $gcd(2^{2012} - 1, 2^{1776} - 1)$, then d divides $2^{gcd(2012, 1776)} - 1= 2^4 - 1= 16 -1 = 15$.
From that and the already shown fact that 15 divides $gcd(2^{2012} - 1, 2^{1776} - 1)$, it follows (reason it out, via primes!) that the gcd = 15.

Here goes: Let d divide both $2^{2012} - 1$ and $2^{1776} - 1$.
Then d divides $(2^{2012} - 1) - (2^{236}) (2^{1776} - 1) = 2^{236} - 1$.
Since d divides both $2^{236} - 1$ and $2^{1776} - 1$, d divides $(2^{1776} - 1) - (2^{1540})(2^{236} - 1) = 2^{1540} - 1$.
Since d divides both $2^{236} - 1$ and $2^{1540} - 1$, d divides $(2^{1540} - 1) - (2^{1304})(2^{236} - 1) = 2^{1304} - 1$.
Since d divides both $2^{236} - 1$ and $2^{1304} - 1$, d divides $(2^{1304} - 1) - (2^{1068})(2^{236} - 1) = 2^{1068} - 1$.
Since d divides both $2^{236} - 1$ and $2^{1068} - 1$, d divides $(2^{1068} - 1) - (2^{832})(2^{236} - 1) = 2^{832} - 1$.
Since d divides both $2^{236} - 1$ and $2^{832} - 1$, d divides $(2^{832} - 1) - (2^{596})(2^{236} - 1) = 2^{596} - 1$.
Since d divides both $2^{236} - 1$ and $2^{596} - 1$, d divides $(2^{596} - 1) - (2^{360})(2^{236} - 1) = 2^{360} - 1$.
Since d divides both $2^{236} - 1$ and $2^{360} - 1$, d divides $(2^{360} - 1) - (2^{124})(2^{236} - 1) = 2^{123} - 1$.
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 $2^{124} - 1$ and $2^{236} - 1$, d divides $(2^{236} - 1) - (2^{112})(2^{124} - 1) = 2^{112} - 1$.
A new lower value of 112. Keep going:
Since d divides both $2^{112} - 1$ and 2^{124} - 1[/tex], d divides $(2^{124} - 1) - (2^{12})(2^{112} - 1) = 2^{12} - 1$.
A new lower value of 12. Keep going:
Since d divides both $2^{12} - 1$ and $2^{112} - 1$, d divides $(2^{112} - 1) - (2^{100})(2^{12} - 1) = 2^{100} - 1$.
Since d divides both $2^{12} - 1$ and $2^{100} - 1$, d divides $(2^{100} - 1) - (2^{88})(2^{12} - 1) = 2^{88} - 1$.
Since d divides both $2^{12} - 1$ and $2^{88} - 1$, d divides $(2^{88} - 1) - (2^{76})(2^{12} - 1) = 2^{76} - 1$.
Since d divides both $2^{12} - 1$ and $2^{76} - 1$, d divides $(2^{76} - 1) - (2^{64})(2^{12} - 1) = 2^{64} - 1$.
Since d divides both $2^{12} - 1$ and $2^{64} - 1$, d divides $(2^{64} - 1) - (2^{52})(2^{12} - 1) = 2^{52} - 1$.
Since d divides both $2^{12} - 1$ and $2^{52} - 1$, d divides $(2^{52} - 1) - (2^{40})(2^{12} - 1) = 2^{40} - 1$.
Since d divides both $2^{12} - 1$ and $2^{40} - 1$, d divides $(2^{40} - 1) - (2^{28})(2^{12} - 1) = 2^{28} - 1$.
Since d divides both $2^{12} - 1$ and $2^{28} - 1$, d divides $(2^{28} - 1) - (2^{16})(2^{12} - 1) = 2^{16} - 1$.
Since d divides both $2^{12} - 1$ and $2^{16} - 1$, d divides $(2^{16} - 1) - (2^{4})(2^{12} - 1) = 2^{4} - 1 = 16 - 1 = 15$.
(You see why the proposition is nice? What a pain!)
Thus if d divides both $2^{2012} - 1$ and $2^{1776} - 1$, then d divides 15.
Since MaxJasper showed that 15 divides the gcd, together these facts prove that the gcd =15.

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

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