## Other

drummers-lowrise

Message boards : General discussion : Why does p divide 2^(p-1)-1?

Author Message
Bur
Volunteer tester

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

Message 147019 - Posted: 24 Dec 2020 | 7:17:02 UTC

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^8-1979 & 1281979 + 4 (cousin prime)

JeppeSN

Joined: 5 Apr 14
Posts: 1501
ID: 306875
Credit: 33,882,700
RAC: 24,050

Message 147024 - Posted: 24 Dec 2020 | 10:25:03 UTC - in response to Message 147019.

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 p-1 (Lagrange's theorem).

/JeppeSN

Bur
Volunteer tester

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

Message 147376 - Posted: 5 Jan 2021 | 10:26:46 UTC - in response to Message 147024.

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^8-1979 & 1281979 + 4 (cousin prime)

JeppeSN

Joined: 5 Apr 14
Posts: 1501
ID: 306875
Credit: 33,882,700
RAC: 24,050

Message 147382 - Posted: 5 Jan 2021 | 14:48:13 UTC - in response to Message 147376.

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

robish
Volunteer moderator
Volunteer tester

Joined: 7 Jan 12
Posts: 1924
ID: 126266
Credit: 5,522,388,959
RAC: 2,954,432

Message 147393 - Posted: 5 Jan 2021 | 23:06:12 UTC

Mother of God Jeppe the group is Cool, that's going to take me weeks to assimilate!

Well Done You!!
____________
My lucky numbers 10590941048576+1 and 224584605939537911+81292139*23#*n for n=0..26

Yves Gallot
Volunteer developer
Project scientist

Joined: 19 Aug 12
Posts: 669
ID: 164101
Credit: 305,042,960
RAC: 0

Message 147455 - Posted: 9 Jan 2021 | 11:38:47 UTC - in response to Message 147019.

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, ..., (n-1)/2 |-> 2, 4, ..., n-1 (n+1)/2, (n+3)/2, ..., n-1 |-> 1, 3, ..., n-2

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^{n-1} prod_a{a}, we have
2^{n-1} prod_a{a} = prod_a{a} (mod n).

If n is prime then prod_a{a} (mod n) != 0 and 2^{n-1} = 1 (mod n).
Otherwise prod_a{a} (mod n) = 0 and 2^{n-1} (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.

Message boards : General discussion : Why does p divide 2^(p-1)-1?