Results 1 to 7 of 7

Math Help - need help with an Eucledian algorthim and gcd involving factorials and large exponets

  1. #1
    Newbie
    Joined
    Sep 2012
    From
    MD
    Posts
    14

    Post 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!!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member MaxJasper's Avatar
    Joined
    Aug 2012
    From
    Canada
    Posts
    482
    Thanks
    55

    Lightbulb 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
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Sep 2012
    From
    MD
    Posts
    14

    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?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member MaxJasper's Avatar
    Joined
    Aug 2012
    From
    Canada
    Posts
    482
    Thanks
    55

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

    Quote Originally Posted by MaxJasper View Post
    \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
    Last edited by MaxJasper; September 9th 2012 at 08:48 PM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member
    Joined
    Sep 2012
    From
    Washington DC USA
    Posts
    525
    Thanks
    147

    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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member
    Joined
    Sep 2012
    From
    Washington DC USA
    Posts
    525
    Thanks
    147

    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.
    Last edited by johnsomeone; September 11th 2012 at 01:28 AM.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Sep 2012
    From
    MD
    Posts
    14

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

    I can not thank you enough for the detailed explanation!!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 4
    Last Post: October 12th 2012, 10:29 PM
  2. Replies: 6
    Last Post: November 14th 2010, 01:51 PM
  3. Replies: 2
    Last Post: September 24th 2010, 12:43 PM
  4. How do I solve a limit involving factorials?
    Posted in the Calculus Forum
    Replies: 1
    Last Post: April 14th 2010, 05:12 PM
  5. Finding derivative involving large powers.
    Posted in the Calculus Forum
    Replies: 7
    Last Post: January 15th 2010, 08:16 PM

Search Tags


/mathhelpforum @mathhelpforum