## Divide by 7

Posted by Chris on July 19, 2012 – 1:01 pm

Prove that 2222^{5555} + 5555^{2222} is divisible by 7.

I know, it’s boring

Obviously, no calculators or computers are allowed.

Posted by Chris on July 19, 2012 – 1:01 pm

Prove that 2222^{5555} + 5555^{2222} is divisible by 7.

I know, it’s boring

Obviously, no calculators or computers are allowed.

July 20th, 2012 at 7:52 pm

Mostly by inspection:

2222(mod 7) ≡ 3

5555(mod 7) ≡ 4

Powers of 2222(mod 7) have a period of 6 with the sequence 3,2,6,4,5,1

i.e.:

2222^1(mod 7) ≡ 3^1 ≡ 3

2222^2(mod 7) ≡ 3^2 ≡ 2

2222^3(mod 7) ≡ 3^3 ≡ 6

2222^4(mod 7) ≡ 3^4 ≡ 4

2222^5(mod 7) ≡ 3^5 ≡ 5

2222^6(mod 7) ≡ 3^6 ≡ 1

2222^7(mod 7) ≡ 3^7 ≡ 3 etc.

So (2222^5555)(mod 7) ≡ 2222(mod 7)^(5555(mod 6))

5555(mod 6) ≡ 5

therefore (2222^5555)(mod 7) ≡ 3^5(mod 7) ≡ 243(mod 7) ≡ 5

Similarly, powers of 4(mod 7) have a period of 3:

5555^1(mod 7) ≡ 4^1 ≡ 4

5555^2(mod 7) ≡ 4^2 ≡ 2

5555^3(mod 7) ≡ 4^3 ≡ 1

5555^4(mod 7) ≡ 4^4 ≡ 4

So (5555^2222)(mod 7) == 5555(mod 7)^(2222(mod 3))

And 2222(mod 3)≡2

Therefore (5555^2222)(mod 7) == 4^2(mod 7) == 16(mod 7) ≡ 2

5 + 2 = 7. QED

July 21st, 2012 at 4:14 am

Hi Mark. That’s pretty much how I would have done it a year or two ago – so it’s right It’s possible to do it more concisely by using Fermat’s little theorem.

You haven’t completely shown how to avoid a calculator, especially for

2222 = 3 (mod 7) and 5555 = 4 (mod 7)

A word on notation. The mathematical world uses e.g. “(mod 7)” to imply that the entire line to the left is to be considered in mod 7. I think that’s daft and it would have been better to put used e.g. “mod 7:” at the start of the line. But it’s too late to change the world.

I’d consider using e.g. 5555^2222 (mod 7)

= (5555 mod 7) ^ (2222 mod 6) (mod 7), yeuch

= 4^2 = 16 = 2 (mod 7)

The mathematical world’s mod notation conventions are pretty poor.

I’ll wait a while before publishing my “offical” solution(s).

July 22nd, 2012 at 11:25 am

Here’s two solutions.

1111 = 1010 + 101 = 11*101 = 11(2*50 + 1) = 4*3 = 5 (mod 7)

=> 2222 = 2*5 = 10 = 3 (mod 7) and 5555 = 5*5 = 25 = 4 (mod 7)

So 2222^5555 + 5555^2222 = 3^5555 + 4^2222 (mod 7)

= 3^5555 + (-3)^2222 = 3^5555 + 3^2222 (mod 7)

(the last is because (-1)^2222 = 1

Fermat’s little theorem => 3^6 = 1 (mod 7)

So consider 1111 = 1110 + 1 = 1 (mod 6), as 1110 is divisible by 2 and 3

So we can replace 2222 with (2222 mod 6) = 2

and 5555 with (5555 mod 6) = 5

=> 2222^5555 + 5555^2222 = 3^5 + 3^2 (mod 7)

=> 243 + 9 = 252 = 5*50 + 2 = 7 = 0 (mod 7) QED

The source used 3^5555 + 3^2222 = 3^2222(1 + 3^3333) (mod 7)

and 3333 = 3 (mod 6) => 1 + 3^3333 = 1 + 3^3 = 0 (mod 7) QED

July 24th, 2012 at 8:18 am

2222= 3 mod 7

5555 = 4 mod 7

2222^5555 + 5555^2222 = (3^5)^1111 + (4^2)^ 1111

as it is a^n + b^n and n is odd so it is divisible by

3^5 + 4^ 2 =

~~252~~259hence by 7 as 7 is a factor of

~~252~~259it does not require FLT

July 24th, 2012 at 11:43 am

Hi Kali. I see you found me Thanks for that alternative solution.

I didn’t know that, in general, that a + b divides a^n + b^n if n is odd. I did know that a – b divides a^n – b^n, but have almost never had need to recall it.

I found a Wiki on it: http://en.wikipedia.org/wiki/Factorization#Sum.2Fdifference_of_two_nth_powers

August 6th, 2014 at 9:36 pm

how is 3^5 + 4^2 = 252 ????? its 257 right

August 6th, 2014 at 9:37 pm

sorry its 259 ok got it

August 6th, 2014 at 9:51 pm

Thanks Sandesh. I’ve edited the erroneous post.

July 26th, 2016 at 8:52 am

Since sequence of 3,2,6,4,5,1 is repeating after 6 powers.

Divide 5555/6 remainder is 5 so after every 6 powers sequence is repeated so according to the sequence at 5 the power after sequence of 6 there would be a remainder in sequence is 5.so answer is 5 for problem