Subscribe via feed.

## Divide by 7

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

Prove that 22225555 + 55552222 is divisible by 7.

I know, it’s boring
Obviously, no calculators or computers are allowed.

This post is under “MathsChallenge” and has 9 respond so far.

### 9 Responds so far- Add one»

1. 1. Mark Sicking Said：

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

2. 2. Chris Said：

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).

3. 3. Chris Said：

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

4. 4. Kali Prasad Tripathy Said：

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 259

hence by 7 as 7 is a factor of 252 259

it does not require FLT

5. 5. Chris Said：

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

6. 6. sandesh Said：

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

7. 7. sandesh Said：

sorry its 259 ok got it

8. 8. Chris Said：

Thanks Sandesh. I’ve edited the erroneous post.

9. 9. Sarthak Said：

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

PHP Warning: PHP Startup: Unable to load dynamic library 'C:\Program Files (x86)\Parallels\Plesk\Additional\PleskPHP5\ext\php_mssql.dll' - The specified module could not be found. in Unknown on line 0 PHP Warning: PHP Startup: Unable to load dynamic library 'C:\Program Files (x86)\Parallels\Plesk\Additional\PleskPHP5\ext\php_pdo_mssql.dll' - The specified module could not be found. in Unknown on line 0