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.
If you enjoy this article, make sure you subscribe to my RSS Feed.

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

Post a reply




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