Author |
Topic: Divisible by 42 (Read 2739 times) |
|
PeterR
Newbie
Posts: 1
|
 |
Divisible by 42
« on: May 26th, 2013, 1:10pm » |
 Quote  Modify
|
Why is (x^7 - x) always divisible by 42?
|
|
 IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender: 
Posts: 7527
|
|
Re: Divisible by 42
« Reply #1 on: May 26th, 2013, 2:17pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
whizen
Newbie
hidden:
Gender:
Posts: 13
|
|
Re: Divisible by 42
« Reply #2 on: May 29th, 2013, 2:36pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Divisible by 42
« Reply #3 on: May 29th, 2013, 10:16pm » |
Quote Modify
|
on May 29th, 2013, 2:36pm, 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.
|
| « Last Edit: May 29th, 2013, 10:19pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print