Join PrimeGrid
Returning Participants
Community
Leader Boards
Results
Other
drummerslowrise

Message boards :
General discussion :
Why does p divide 2^(p1)1?
Author 
Message 
BurVolunteer tester
Send message
Joined: 25 Feb 20 Posts: 399 ID: 1241833 Credit: 156,998,093 RAC: 1,014,275

This might sound like a strange question and I am not looking for a mathmatical proof. But maybe there is some more accessible way to show why there is a relation at all? It seems so arbitrary to me, which, of course, it actually isn't.
____________
Primes: 1281979 & 12+8+1979 & 1+2+8+1+9+7+9 & 1^2+2^2+8^2+1^2+9^2+7^2+9^2 & 12*8+19*79 & 12^81979 & 1281979 + 4 (cousin prime)  


This might sound like a strange question and I am not looking for a mathmatical proof. But maybe there is some more accessible way to show why there is a relation at all? It seems so arbitrary to me, which, of course, it actually isn't.
Not sure what kind of answer you are after, when not a proof.
This result is known as Fermat's little theorem (Wikipedia). I suggest you read about it. What they call a, is 2 in your example, so the result is valid if 2 does not divide the prime p.
A modern way of understanding the result, is that the (nonzero) integers modulo p form a group with multiplication, and in that group, 2 is a member; and the order of a member divides the order of the group which is p1 (Lagrange's theorem).
/JeppeSN  

BurVolunteer tester
Send message
Joined: 25 Feb 20 Posts: 399 ID: 1241833 Credit: 156,998,093 RAC: 1,014,275

Ok, thanks. I thought there might be an intuitive way to see why it is true.
____________
Primes: 1281979 & 12+8+1979 & 1+2+8+1+9+7+9 & 1^2+2^2+8^2+1^2+9^2+7^2+9^2 & 12*8+19*79 & 12^81979 & 1281979 + 4 (cousin prime)  


Ok, thanks. I thought there might be an intuitive way to see why it is true.
My intuition might be different than yours because of my educational background (which is why I wrote that the group gives the intuition). /JeppeSN  

robishVolunteer moderator Volunteer tester
Send message
Joined: 7 Jan 12 Posts: 1924 ID: 126266 Credit: 5,522,388,959 RAC: 2,954,432

Mother of God Jeppe the group is Cool, that's going to take me weeks to assimilate!
Well Done You!!
____________
My lucky numbers 1059094^{1048576}+1 and 224584605939537911+81292139*23#*n for n=0..26  

Yves GallotVolunteer developer Project scientist Send message
Joined: 19 Aug 12 Posts: 669 ID: 164101 Credit: 305,042,960 RAC: 0

This might sound like a strange question and I am not looking for a mathmatical proof. But maybe there is some more accessible way to show why there is a relation at all? It seems so arbitrary to me, which, of course, it actually isn't.
With a = 2 the proof is simpler and I think that the reason is "accessible".
Let n be an odd integer, the set {a: 0 < a < n} and the function x > 2x mod n.
The function transforms the lower part of the set into the even numbers of the set and the high part into the odd numbers:
1, 2, ..., (n1)/2 > 2, 4, ..., n1
(n+1)/2, (n+3)/2, ..., n1 > 1, 3, ..., n2
Then x > 2x mod n is bijective, hence
prod_a{2a} = prod_a{a} (mod n)
(the products are identical, there are just ordered differently).
Since prod_a{2a} = prod_a{2} prod_a{a} = 2^{n1} prod_a{a}, we have
2^{n1} prod_a{a} = prod_a{a} (mod n).
If n is prime then prod_a{a} (mod n) != 0 and 2^{n1} = 1 (mod n).
Otherwise prod_a{a} (mod n) = 0 and 2^{n1} (mod n) is any number.
We see that the reasons are:
 the property of the function x > 2x mod n in {a: 0 < a < n} which is bijective.
 the fact that if n is prime then prod_{0 < a < n}{a} is not divisible by n.  

Post to thread
Message boards :
General discussion :
Why does p divide 2^(p1)1? 