# Divisibility by 7

• Jun 3rd 2009, 12:51 AM
Showcase_22
Divisibility by 7
Prove that $\displaystyle 2222^{5555}+5555^{2222}$ is divisible by 7.

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

I have that:
$\displaystyle 2222=3 \mod7=2 \mod 6$
$\displaystyle 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?
• Jun 3rd 2009, 01:17 AM
Moo
Hello,

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

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

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

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

Why ? Because $\displaystyle 5555=6k+5$

And then $\displaystyle 3^{6k+5}=(3^6)^k\cdot 3^5 \dots$ :)
• Jun 3rd 2009, 01:30 AM
TheAbstractionist
Quote:

Originally Posted by Showcase_22
Prove that $\displaystyle 2222^{5555}+5555^{2222}$ is divisible by 7.

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

I have that:
$\displaystyle 2222=3 \mod7=2 \mod 6$
$\displaystyle 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.

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

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

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

The reason I prefer $\displaystyle 2222^3$ and $\displaystyle 5555^3$ rather than $\displaystyle 2222^6$ and $\displaystyle 5555^6$ is that their powers can be brought closer this way to 5555 and 2222 respectively.
• Jun 3rd 2009, 01:47 AM
Showcase_22
Quote:

Hello,
Hello! (Rofl)

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.
• Jun 3rd 2009, 02:08 AM
Showcase_22
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!):

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

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

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

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

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

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

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

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

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

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

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

(Rofl) **WIN** (Rofl)
• Jun 3rd 2009, 02:38 AM
Moo
Well, actually that was exactly the way I wanted you to do (Rofl)

Good job.

Though your notations are very strange...
Quote:

$\displaystyle =(1 \bmod 7)(3^2. 3^2.3 \bmod 7)$
Just write $\displaystyle 1\cdot 3^2 \cdot 3^2 \cdot 3 \bmod 7$

Quote:

$\displaystyle 5555^{2222}=(5 \bmod {\color{red}7})^{2222}$
Write $\displaystyle 5555^{2222}=5^{2222} \bmod 7$
• Jun 3rd 2009, 02:40 AM
Showcase_22
I didn't realise there was a command for $\displaystyle "\cdot"$. The more I know!