wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Divisible by 42
        
(Message started by: PeterR on May 26th, 2013, 1:10pm)
Title: Divisible by 42
Post by PeterR on May 26th, 2013, 1:10pm
Why is (x^7 - x) always divisible by 42?
Title: Re: Divisible by 42
Post by Grimbal on May 26th, 2013, 2:17pm
Because it is always divisible by 2, 3 and 7.

xp = x (mod p) for p prime.

x7 = x (mod 7)
x7 = x5 = x3 = x (mod 3)
x7 = x6 = ... = x2 = x (mod 2)

Therefore x7-x is a multiple of 7, 3 and 2, and therefore also of their product, 42.
Title: Re: Divisible by 42
Post by whize on May 29th, 2013, 2:36pm
I didn't quite understand the divisibility by 3 and 2 proofs in Grimbal's reply. I have just been too lazy to find out, but not lazy enough to not work it out another way.

x7 - x = 0 (mod 7)
Hence, the original equation is divisible by 7


x7 - x = x ( x6 - 1)
x ( x3 - 1 )( x3 + 1 )
x ( x - 1 ) ( x2 + x + 1 ) ( x3 + 1 )

x ( x - 1 ) is divisible by 2
(x3 + 1) = (x + 1) mod 3...
hence ( x ( x - 1 ) (x3 + 1) ) {three consecutive numbers (mod 3)} is divisible by 3

Together, the product is divisible by 2*3*7 = 42

I would be delighted to know how Grimbal's divisibility tests by 2 & 3 work.
Title: Re: Divisible by 42
Post by towr on May 29th, 2013, 10:16pm

on 05/29/13 at 14:36:20, whize wrote:
I would be delighted to know how Grimbal's divisibility tests by 2 & 3 work.
It follows the general rule he stated before, that for prime p: xp = x (mod p)
3 and 2 are primes.

So x7 = x3*x4, and then we can simplify the first factor x3*x4 = x*x4 (mod 3)
repeat a couple of times (for each = he wrote)
x*x4 = x3*x2 = x * x2 (mod 3)
x*x2 = x3 = x (mod 3)
Similar for 2.


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board