Results 1 to 7 of 7

Math Help - Divisibility by 7

  1. #1
    Super Member Showcase_22's Avatar
    Joined
    Sep 2006
    From
    The raggedy edge.
    Posts
    782

    Divisibility by 7

    Prove that 2222^{5555}+5555^{2222} is divisible by 7.

    I set about trying to show that this expression is equal to 0 \mod 7.

    I have that:
    2222=3 \mod7=2 \mod 6
    5555=4 \mod 7=5 \mod 6

    The question also has Fermat's little theorem above it so I think I should be using that somewhere.

    Anyone have any ideas?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Hello,

    Let's take for example 2222^{5555}
    It's congruent to 3^{5555}(\bmod 7)

    Now, you know by Fermat's little theorem, that 3^{6}\equiv 1(\bmod 7)

    As you noticed, 5555\equiv 5(\bmod 6)

    It can be proved that hence 2222^{5555}\equiv 3^5 (\bmod 7)

    Why ? Because 5555=6k+5

    And then 3^{6k+5}=(3^6)^k\cdot 3^5 \dots
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member TheAbstractionist's Avatar
    Joined
    Apr 2009
    Posts
    328
    Thanks
    1
    Quote Originally Posted by Showcase_22 View Post
    Prove that 2222^{5555}+5555^{2222} is divisible by 7.

    I set about trying to show that this expression is equal to 0 \mod 7.

    I have that:
    2222=3 \mod7=2 \mod 6
    5555=4 \mod 7=5 \mod 6

    The question also has Fermat's little theorem above it so I think I should be using that somewhere.

    Anyone have any ideas?
    Hi Showcase_22.

    Fermat’s little theorem is a little cumbersome for this problem. Here is a shorter way.

    2222\equiv3\,\bmod7\ \implies\ 2222^3\equiv-1\,\bmod7 \implies\ 2222^{5555}=2222^{3\cdot1851+2}\equiv-3^2\,\bmod7\equiv5\,\bmod7

    5555\equiv4\,\bmod7\ \implies\ 5555^3\equiv1\,\bmod7 \implies\ 5555^{2222}=5555^{3\cdot740+2}\equiv4^2\,\bmod7\eq  uiv2\,\bmod7

    Hence 2222^{5555}+5555^{2222}\equiv7\,\bmod7\equiv0\,\bm  od7.

    The reason I prefer 2222^3 and 5555^3 rather than 2222^6 and 5555^6 is that their powers can be brought closer this way to 5555 and 2222 respectively.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member Showcase_22's Avatar
    Joined
    Sep 2006
    From
    The raggedy edge.
    Posts
    782
    Hello,
    Hello!

    I finally got it to work out using TheAbstractionist's method (I looked at what you did, did it for 2222 whilst looking at yours and then did it for 5555 separately).

    I'll have a go using your method now Moo since it seems to be the one in the mark scheme.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member Showcase_22's Avatar
    Joined
    Sep 2006
    From
    The raggedy edge.
    Posts
    782
    Okay, here's my way of doing it. I think it's both of your methods combined (or I may just be copying one of your methods, i'm not that good at number theory!):

    2222^{5555}=3^{5555} \bmod 7

    3^6=1 \bmod 7 by Fermat's little theorem

    3^{5555} \bmod 7=3^{6(925)+5}=3^{6(925)}3^5 \bmod 7

    =(1 \bmod 7)(3^2. 3^2.3 \bmod 7)=(1 \bmod 7 )(5 \bmod 7)=5 \bmod 7

    \Rightarrow 2222^{5555}=5 \bmod 7

    5555^{2222}=(5 \bmod 6)^{2222}

    4^6=1 \bmod 7 by Fermat's little theorem.

    5555^{2222}=(4 \bmod 7)^{2222}

    =4^{370(6)+2} \bmod 7=4^{370(6)}.4^2 \bmod 7=(1 \bmod 7)(2 \bmod 7)=2 \bmod 7

    \Rightarrow 5555^{2222}=2 \bmod 7

    \Rightarrow 2222^{5555}+5555^{2222}=2 \bmod 7+5 \mod 7=7 \bmod 7= 0 \bmod 7

    **WIN**
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Well, actually that was exactly the way I wanted you to do

    Good job.

    Though your notations are very strange...
    =(1 \bmod 7)(3^2. 3^2.3 \bmod 7)
    Just write 1\cdot 3^2 \cdot 3^2 \cdot 3 \bmod 7

    5555^{2222}=(5 \bmod {\color{red}7})^{2222}<br />
    Write 5555^{2222}=5^{2222} \bmod 7
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Super Member Showcase_22's Avatar
    Joined
    Sep 2006
    From
    The raggedy edge.
    Posts
    782
    Ah, sorry about my notations!

    I didn't realise there was a command for "\cdot". The more I know!

    That second one was just plain wrong, sorry I wrote it!

    On the plus side:

    Spoiler:
    At least I know how to use these spoiler boxes now!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Divisibility 11
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: December 20th 2008, 03:41 AM
  2. Divisibility (gcd) 10
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 19th 2008, 05:44 PM
  3. Divisibility (gcd) 9
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 19th 2008, 02:12 PM
  4. Divisibility (gcd) 8
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: December 19th 2008, 04:53 AM
  5. Divisibility
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 14th 2008, 10:24 AM

Search Tags


/mathhelpforum @mathhelpforum