Results 1 to 5 of 5

Math Help - Some congruences

  1. #1
    Newbie
    Joined
    Jan 2010
    Posts
    11

    Some congruences

    Hi, im quite new to the number theory topic, and i am self studying congruences right now.
    some exercises are these, and im not quite sure how to solve them

    1) find the remainder when 2^50 is divided by 7
    2) fin the remainder when 41^65 is divided by 7
    3) find the remainder when the sum (1^5)+(2^5)+(3^5)+....+(99^5)+(100^5) is divided by 7.

    i know they might be easy, but im just looking for exercises by internet, and if someone can recomend me a good book for learning this, i will thank that.
    thank you!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor alexmahone's Avatar
    Joined
    Oct 2008
    Posts
    1,074
    Thanks
    7
    Quote Originally Posted by guidol92 View Post
    Hi, im quite new to the number theory topic, and i am self studying congruences right now.
    some exercises are these, and im not quite sure how to solve them

    1) find the remainder when 2^50 is divided by 7
    2) fin the remainder when 41^65 is divided by 7
    3) find the remainder when the sum (1^5)+(2^5)+(3^5)+....+(99^5)+(100^5) is divided by 7.

    i know they might be easy, but im just looking for exercises by internet, and if someone can recomend me a good book for learning this, i will thank that.
    thank you!
    1) 2^3 \equiv 1 \pmod{7}

    (2^3)^{16} \equiv 1 \pmod{7}

    2^{48} \equiv 1 \pmod{7}

    2^{50} \equiv 4 \pmod{7}

    So, the remainder when 2^{50} is divided by 7 is 4.

    2) 41 \equiv 6 \pmod{7}

    41^2 \equiv 36 \equiv 1 \pmod{7}

    (41^2)^{32} \equiv 1 \pmod{7}

    41^{64} \equiv 1 \pmod{7}

    41^{65} \equiv 6 \pmod{7}

    So, the remainder when 41^{65} is divided by 7 is 6.

    1^5+6^5 \equiv 1+6 \equiv 7 \equiv 0 \pmod{7}

    2^5+5^5 \equiv 2+5 \equiv 7 \equiv 0 \pmod{7}

    3^5+4^5 \equiv 3+4 \equiv 7 \equiv 0 \pmod{7}

    7^5 \equiv 0 \pmod{7}

    Thus, 1^5+2^5+3^5+4^5+5^5+6^5+7^5 \equiv 0 \pmod{7}

    8 \equiv 1 \pmod{7}

    8 \equiv 2 \pmod{7}

    and so on.

    Thus, 1^5+2^5+3^5+....+97^5+98^5 \equiv 0 \pmod{7}

    99 \equiv 1 \pmod{7}

    100 \equiv 2 \pmod{7}

    99^5+100^5 \equiv 1^5+2^5 \equiv 33 \equiv 5 \pmod{7}

    Thus, 1^5+2^5+3^5+....+99^5+100^5 \equiv 5 \pmod{7}

    So, the remainder when the sum 1^5+2^5+3^5+....+99^5+100^5 is divided by 7 is 5.
    Last edited by alexmahone; January 3rd 2010 at 04:32 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,802
    Thanks
    692
    Hello, guidol92!

    Here's another approach to #3 . . .


    3) Find the remainder when the sum: . S \;=\; 1^5+2^5+3^5+ \hdots + 100^5 .is divided by 7.
    We note that:

    . . \begin{array}{cccc}1^5 & \equiv & 1^5 & \text{(mod 7)} \\<br />
2^5 & \equiv & 2^5 & \text{(mod 7)} \\<br />
3^5 & \equiv & 3^5 & \text{(mod 7)} \\ <br />
4^5 & \equiv &(\text{-}3)^5 & \text{(mod 7)} \\<br />
5^5 & \equiv & (\text{-}2)^5 & \text{(mod 7}) \\<br />
6^5 & \equiv & (\text{-}1)^5 & \text{(mod 7)} \\<br />
7^5 & \equiv & 0^5 & \text{(mod 7)}<br />
\end{array}


    The sum of these seven consecutive fifth powers is:
    . . 1^5 + 2^5 + 3^5 + (\text{-}3)^5 + (\text{-}2)^5 + (\text{-}1)^5 + 0^5 \;=\;0


    S \;\equiv\;\underbrace{\bigg[1^5+2^5+3^5+4^5+5^7 + 6^5 +7^5\bigg]}_{\text{This is 0}} + \hdots + \underbrace{\bigg[92^5 + 93^5 + 94^5 + 95^5 + 96^5 + 97^5+ 98^5\bigg]}_{\text{This is 0}} + 99^5 + 100^5 \;\text{(mod 7)}


    Hence: . S \;\;\equiv\;\;99^5+100^5 \;\;\equiv\;\;1^5 + 2^5 \;\;\equiv\;\;33 \;\;\equiv\;\;4\text{ (mod 7)}

    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,802
    Thanks
    692
    Hello again, guidol92![

    2) Find the remainder when . 41^{65} .is divided by 7

    We find that: . 41^2 \;=\;1681 \;\equiv 1\text{ (mod 7)}

    Therefore: . 41^{65} \;\;=\;\;41^{2(32)+1} \;\;=\;\;(41^2)^{32}\cdot41  \;\;\equiv\;\;1^{32}\cdot41 \;\;\equiv\;\;41 \;\;\equiv\;\;6\text{ (mod 7)}

    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Jan 2010
    Posts
    11
    Thanks for the help! really apreciate it.

    If there is no problem, can someone tell me a good link or source where i can cover extensively this nomber theory stuff?
    thank you again poeple.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Congruences
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: March 11th 2010, 12:52 PM
  2. Congruences
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: May 7th 2009, 02:26 PM
  3. Congruences
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 18th 2009, 05:12 AM
  4. More congruences
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: March 17th 2009, 10:40 PM
  5. Congruences
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: September 29th 2008, 09:49 AM

Search Tags


/mathhelpforum @mathhelpforum