Results 1 to 5 of 5

Thread: 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,115
    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) $\displaystyle 2^3 \equiv 1 \pmod{7}$

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

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

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

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

    2) $\displaystyle 41 \equiv 6 \pmod{7}$

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

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

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

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

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

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

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

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

    $\displaystyle 7^5 \equiv 0 \pmod{7}$

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

    $\displaystyle 8 \equiv 1 \pmod{7}$

    $\displaystyle 8 \equiv 2 \pmod{7}$

    and so on.

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

    $\displaystyle 99 \equiv 1 \pmod{7}$

    $\displaystyle 100 \equiv 2 \pmod{7}$

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

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

    So, the remainder when the sum $\displaystyle 1^5+2^5+3^5+....+99^5+100^5$ is divided by $\displaystyle 7$ is $\displaystyle 5$.
    Last edited by alexmahone; Jan 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
    12,028
    Thanks
    848
    Hello, guidol92!

    Here's another approach to #3 . . .


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

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


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


    $\displaystyle S \;\equiv\;\underbrace{\bigg[1^5+2^5+3^5+4^5+5^7 + 6^5 +7^5\bigg]}_{\text{This is 0}} + \hdots + $ $\displaystyle \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: .$\displaystyle 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
    12,028
    Thanks
    848
    Hello again, guidol92![

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

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

    Therefore: .$\displaystyle 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: Mar 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: Mar 18th 2009, 05:12 AM
  4. More congruences
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Mar 17th 2009, 10:40 PM
  5. Congruences
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Sep 29th 2008, 09:49 AM

Search Tags


/mathhelpforum @mathhelpforum