# Some congruences

• Jan 3rd 2010, 05:46 AM
guidol92
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!
• Jan 3rd 2010, 06:45 AM
alexmahone
Quote:

Originally Posted by guidol92
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$.
• Jan 3rd 2010, 10:42 AM
Soroban
Hello, guidol92!

Here's another approach to #3 . . .

Quote:

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)} \\
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:
. . $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)}$

• Jan 3rd 2010, 10:52 AM
Soroban
Hello again, guidol92![

Quote:

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)}$

• Jan 3rd 2010, 03:42 PM
guidol92
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.