Divisibility by 7

**Showcase_22** · June 3rd 2009, 12:51 AM

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?

**Moo** · June 3rd 2009, 01:17 AM

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$

**TheAbstractionist** · June 3rd 2009, 01:30 AM

Originally Posted by Showcase_22

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.

**Showcase_22** · June 3rd 2009, 01:47 AM

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.

**Showcase_22** · June 3rd 2009, 02:08 AM

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**

**Moo** · June 3rd 2009, 02:38 AM

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$

**Showcase_22** · June 3rd 2009, 02:40 AM

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:

Thread: Divisibility by 7

LinkBack

Thread Tools

Display

Divisibility by 7

Similar Math Help Forum Discussions

Divisibility 11

Divisibility (gcd) 10

Divisibility (gcd) 9

Divisibility (gcd) 8

Divisibility

Search Tags