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

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

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

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

Quote:

Originally Posted by

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

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

$\displaystyle 2012=2^2*503$

$\displaystyle 1776=2^4*3*37$

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

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

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

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

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

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

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 $\displaystyle 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

$\displaystyle (b^x-1)$ and d divides $\displaystyle (b^y-1)$, with x<y. Then d divides $\displaystyle (b^y-1)-b^{y-x}(b^x-1) = b^{y-x}-1$.

Now d divides $\displaystyle (b^x-1)$ and d divides $\displaystyle (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 $\displaystyle (b^r-1)$ and d divides $\displaystyle (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 $\displaystyle (b^x-1)$ and d divides $\displaystyle (b^y-1)$, then d divides $\displaystyle (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 $\displaystyle gcd(2^{2012} - 1, 2^{1776} - 1)$, then d divides $\displaystyle 2^{gcd(2012, 1776)} - 1= 2^4 - 1= 16 -1 = 15$.

From that and the already shown fact that 15 divides $\displaystyle gcd(2^{2012} - 1, 2^{1776} - 1)$, it follows (reason it out, via primes!) that the gcd = 15.

Here goes: Let d divide both $\displaystyle 2^{2012} - 1$ and $\displaystyle 2^{1776} - 1$.

Then d divides $\displaystyle (2^{2012} - 1) - (2^{236}) (2^{1776} - 1) = 2^{236} - 1$.

Since d divides both $\displaystyle 2^{236} - 1$ and $\displaystyle 2^{1776} - 1$, d divides $\displaystyle (2^{1776} - 1) - (2^{1540})(2^{236} - 1) = 2^{1540} - 1$.

Since d divides both $\displaystyle 2^{236} - 1$ and $\displaystyle 2^{1540} - 1$, d divides $\displaystyle (2^{1540} - 1) - (2^{1304})(2^{236} - 1) = 2^{1304} - 1$.

Since d divides both $\displaystyle 2^{236} - 1$ and $\displaystyle 2^{1304} - 1$, d divides $\displaystyle (2^{1304} - 1) - (2^{1068})(2^{236} - 1) = 2^{1068} - 1$.

Since d divides both $\displaystyle 2^{236} - 1$ and $\displaystyle 2^{1068} - 1$, d divides $\displaystyle (2^{1068} - 1) - (2^{832})(2^{236} - 1) = 2^{832} - 1$.

Since d divides both $\displaystyle 2^{236} - 1$ and $\displaystyle 2^{832} - 1$, d divides $\displaystyle (2^{832} - 1) - (2^{596})(2^{236} - 1) = 2^{596} - 1$.

Since d divides both $\displaystyle 2^{236} - 1$ and $\displaystyle 2^{596} - 1$, d divides $\displaystyle (2^{596} - 1) - (2^{360})(2^{236} - 1) = 2^{360} - 1$.

Since d divides both $\displaystyle 2^{236} - 1$ and $\displaystyle 2^{360} - 1$, d divides $\displaystyle (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 $\displaystyle 2^{124} - 1$ and $\displaystyle 2^{236} - 1$, d divides $\displaystyle (2^{236} - 1) - (2^{112})(2^{124} - 1) = 2^{112} - 1$.

A new lower value of 112. Keep going:

Since d divides both $\displaystyle 2^{112} - 1$ and 2^{124} - 1[/tex], d divides $\displaystyle (2^{124} - 1) - (2^{12})(2^{112} - 1) = 2^{12} - 1$.

A new lower value of 12. Keep going:

Since d divides both $\displaystyle 2^{12} - 1$ and $\displaystyle 2^{112} - 1$, d divides $\displaystyle (2^{112} - 1) - (2^{100})(2^{12} - 1) = 2^{100} - 1$.

Since d divides both $\displaystyle 2^{12} - 1$ and $\displaystyle 2^{100} - 1$, d divides $\displaystyle (2^{100} - 1) - (2^{88})(2^{12} - 1) = 2^{88} - 1$.

Since d divides both $\displaystyle 2^{12} - 1$ and $\displaystyle 2^{88} - 1$, d divides $\displaystyle (2^{88} - 1) - (2^{76})(2^{12} - 1) = 2^{76} - 1$.

Since d divides both $\displaystyle 2^{12} - 1$ and $\displaystyle 2^{76} - 1$, d divides $\displaystyle (2^{76} - 1) - (2^{64})(2^{12} - 1) = 2^{64} - 1$.

Since d divides both $\displaystyle 2^{12} - 1$ and $\displaystyle 2^{64} - 1$, d divides $\displaystyle (2^{64} - 1) - (2^{52})(2^{12} - 1) = 2^{52} - 1$.

Since d divides both $\displaystyle 2^{12} - 1$ and $\displaystyle 2^{52} - 1$, d divides $\displaystyle (2^{52} - 1) - (2^{40})(2^{12} - 1) = 2^{40} - 1$.

Since d divides both $\displaystyle 2^{12} - 1$ and $\displaystyle 2^{40} - 1$, d divides $\displaystyle (2^{40} - 1) - (2^{28})(2^{12} - 1) = 2^{28} - 1$.

Since d divides both $\displaystyle 2^{12} - 1$ and $\displaystyle 2^{28} - 1$, d divides $\displaystyle (2^{28} - 1) - (2^{16})(2^{12} - 1) = 2^{16} - 1$.

Since d divides both $\displaystyle 2^{12} - 1$ and $\displaystyle 2^{16} - 1$, d divides $\displaystyle (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 $\displaystyle 2^{2012} - 1$ and $\displaystyle 2^{1776} - 1$, 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!!