Results 1 to 5 of 5

Math Help - Proving divisibility

  1. #1
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1

    Proving divisibility

    Quote Originally Posted by the undertaker View Post
    Prove that 20^22 - 17^22 + 4^33 - 1 is divisible by 174.
    First of all, these numbers are really small for computers to handle, so a direct calculation isn't hard.

    If you need to make the numbers smaller, you can use the Chinese remainder theorem and the fact that 174 = 2*3*29. (Although that might be more work in the end than just using 174.) You can also factor 20 = 2*10, and 4 = 2*2. Shouldn't be all that hard...

    By the way, if you really have to do everything on paper, you can see this thread (post #7) for a description of fast modular exponentiation.

    Edit: Upon further reflection, using the Chinese remainder theorem definitely results in less work. Mod 2, we see that from left to right we have an even minus an odd plus an even minus an odd, resulting in an even, so it is congruent to 0 (mod 2). Mod 3, the first two terms are both 2^22 (mod 3) and so together are 0 (mod 3), and the next term is simply 1^33 (mod 3) which is 1 (mod 3), so we see that the expression is congruent to 0 (mod 3). Now all we have to do is show that the expression is congruent to 0 (mod 29) and we are done. Working mod 29 should be more manageable on paper than 174. For 4^33 you can use Fermat's little theorem to get that 4^33 = 4^28*4^5 is congruent to 4^5 (mod 29).



    Moderator edit: This post was moved from a thread created by a duplicate post. Unfortunately I misread the time stamps on both threads, which is why this post preceeds the original post (which is post #2 below). Apologies for any confusion.
    Last edited by mr fantastic; May 11th 2010 at 03:45 AM. Reason: Moved from thread created by duplicate post.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    Joined
    May 2009
    Posts
    29

    Proving divisibility

    Prove that 20^22 - 17^22 + 4^33 - 1 is divisible by 174.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Jan 2009
    Posts
    715
    Quote Originally Posted by the undertaker View Post
    Prove that 20^22 - 17^22 + 4^33 - 1 is divisible by 174.
    Note that 174 = 2\cdot 3 \cdot 29 we need to prove it is the multiple of 2 , 3 and 29 separately .

    It is easy to prove it is divisible by 2 and 3 , i give them yo you .

    I will prove it is divisible by 29 .

     20^{22} - 17^{22} + 4^{33} - 1

     = (4^{22}5^{22}) +4^{33} - (17^{22} + 1)

     = (4^{22}5^{22}) + (4^{22}4^{11}) - ((17^2)^{11} + 1)

     = 4^{22} ( 5^{22} + 4^{11} ) - (289^{11} + 1)

     \equiv 4^{22} ( 5^{22} + (-25)^{11}) - ( (289-290)^{11} + 1) \bmod{29}

     \equiv 4^{22} ( 25^{11} - 25^{11}) - ( -1 + 1) \bmod{29} \equiv 0 \bmod{29}


    EDIT :

    Is it a odd or an even number ?

    And note that

     20 \equiv -1 \bmod{3}
     17 \equiv -1 \bmod{3}
     4  \equiv 1 \bmod{3}
    Last edited by simplependulum; May 11th 2010 at 05:01 AM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    May 2009
    Posts
    29
    Thanks simplependulum,
    but could you also prove it divisble by 2 and 3?
    cheers.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by the undertaker View Post
    Thanks simplependulum,
    but could you also prove it divisble by 2 and 3?
    cheers.
    I already did this in my post.. was it not clear?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Divisibility
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: July 6th 2010, 02:39 PM
  2. Proving an identity that's proving to be complex
    Posted in the Trigonometry Forum
    Replies: 1
    Last Post: July 21st 2009, 02:30 PM
  3. Proving divisibility question using contradiction
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: March 28th 2009, 12:00 AM
  4. Divisibility
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 14th 2008, 10:24 AM
  5. Divisibility
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: September 30th 2008, 03:19 PM

Search Tags


/mathhelpforum @mathhelpforum