PrimeGrid
Please visit donation page to help the project cover running costs for this month

Toggle Menu

Join PrimeGrid

Returning Participants

Community

Leader Boards

Results

Other

drummers-lowrise

Advanced search

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

Author Message
Profile BurProject donor
Volunteer tester
Avatar
Send message
Joined: 25 Feb 20
Posts: 399
ID: 1241833
Credit: 156,998,093
RAC: 1,014,275
321 LLR Amethyst: Earned 1,000,000 credits (1,058,073)Cullen LLR Amethyst: Earned 1,000,000 credits (1,169,946)ESP LLR Amethyst: Earned 1,000,000 credits (1,093,381)Generalized Cullen/Woodall LLR Amethyst: Earned 1,000,000 credits (1,148,593)PPS LLR Amethyst: Earned 1,000,000 credits (1,225,852)PSP LLR Amethyst: Earned 1,000,000 credits (1,248,861)SoB LLR Amethyst: Earned 1,000,000 credits (1,669,219)SR5 LLR Amethyst: Earned 1,000,000 credits (1,060,324)SGS LLR Amethyst: Earned 1,000,000 credits (1,108,160)TRP LLR Amethyst: Earned 1,000,000 credits (1,039,866)Woodall LLR Amethyst: Earned 1,000,000 credits (1,129,385)321 Sieve (suspended) Ruby: Earned 2,000,000 credits (2,107,153)PPS Sieve Amethyst: Earned 1,000,000 credits (1,045,010)AP 26/27 Ruby: Earned 2,000,000 credits (2,470,273)WW Double Bronze: Earned 100,000,000 credits (130,620,000)GFN Turquoise: Earned 5,000,000 credits (7,149,778)PSA Gold: Earned 500,000 credits (678,219)
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)

Profile JeppeSNProject donor
Avatar
Send message
Joined: 5 Apr 14
Posts: 1501
ID: 306875
Credit: 33,882,700
RAC: 24,050
Found 1 prime in the 2020 Tour de Primes321 LLR Gold: Earned 500,000 credits (529,293)Cullen LLR Gold: Earned 500,000 credits (611,298)ESP LLR Silver: Earned 100,000 credits (139,922)Generalized Cullen/Woodall LLR Bronze: Earned 10,000 credits (35,236)PPS LLR Jade: Earned 10,000,000 credits (12,019,664)PSP LLR Silver: Earned 100,000 credits (212,242)SoB LLR Silver: Earned 100,000 credits (466,812)SR5 LLR Silver: Earned 100,000 credits (145,419)SGS LLR Silver: Earned 100,000 credits (112,277)TRP LLR Silver: Earned 100,000 credits (342,501)Woodall LLR Silver: Earned 100,000 credits (109,455)321 Sieve (suspended) Silver: Earned 100,000 credits (175,037)PPS Sieve Bronze: Earned 10,000 credits (10,113)AP 26/27 Bronze: Earned 10,000 credits (12,129)WW Turquoise: Earned 5,000,000 credits (9,640,000)GFN Amethyst: Earned 1,000,000 credits (1,707,013)PSA Turquoise: Earned 5,000,000 credits (7,614,290)
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

Profile BurProject donor
Volunteer tester
Avatar
Send message
Joined: 25 Feb 20
Posts: 399
ID: 1241833
Credit: 156,998,093
RAC: 1,014,275
321 LLR Amethyst: Earned 1,000,000 credits (1,058,073)Cullen LLR Amethyst: Earned 1,000,000 credits (1,169,946)ESP LLR Amethyst: Earned 1,000,000 credits (1,093,381)Generalized Cullen/Woodall LLR Amethyst: Earned 1,000,000 credits (1,148,593)PPS LLR Amethyst: Earned 1,000,000 credits (1,225,852)PSP LLR Amethyst: Earned 1,000,000 credits (1,248,861)SoB LLR Amethyst: Earned 1,000,000 credits (1,669,219)SR5 LLR Amethyst: Earned 1,000,000 credits (1,060,324)SGS LLR Amethyst: Earned 1,000,000 credits (1,108,160)TRP LLR Amethyst: Earned 1,000,000 credits (1,039,866)Woodall LLR Amethyst: Earned 1,000,000 credits (1,129,385)321 Sieve (suspended) Ruby: Earned 2,000,000 credits (2,107,153)PPS Sieve Amethyst: Earned 1,000,000 credits (1,045,010)AP 26/27 Ruby: Earned 2,000,000 credits (2,470,273)WW Double Bronze: Earned 100,000,000 credits (130,620,000)GFN Turquoise: Earned 5,000,000 credits (7,149,778)PSA Gold: Earned 500,000 credits (678,219)
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)

Profile JeppeSNProject donor
Avatar
Send message
Joined: 5 Apr 14
Posts: 1501
ID: 306875
Credit: 33,882,700
RAC: 24,050
Found 1 prime in the 2020 Tour de Primes321 LLR Gold: Earned 500,000 credits (529,293)Cullen LLR Gold: Earned 500,000 credits (611,298)ESP LLR Silver: Earned 100,000 credits (139,922)Generalized Cullen/Woodall LLR Bronze: Earned 10,000 credits (35,236)PPS LLR Jade: Earned 10,000,000 credits (12,019,664)PSP LLR Silver: Earned 100,000 credits (212,242)SoB LLR Silver: Earned 100,000 credits (466,812)SR5 LLR Silver: Earned 100,000 credits (145,419)SGS LLR Silver: Earned 100,000 credits (112,277)TRP LLR Silver: Earned 100,000 credits (342,501)Woodall LLR Silver: Earned 100,000 credits (109,455)321 Sieve (suspended) Silver: Earned 100,000 credits (175,037)PPS Sieve Bronze: Earned 10,000 credits (10,113)AP 26/27 Bronze: Earned 10,000 credits (12,129)WW Turquoise: Earned 5,000,000 credits (9,640,000)GFN Amethyst: Earned 1,000,000 credits (1,707,013)PSA Turquoise: Earned 5,000,000 credits (7,614,290)
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

Profile robishProject donor
Volunteer moderator
Volunteer tester
Avatar
Send message
Joined: 7 Jan 12
Posts: 1924
ID: 126266
Credit: 5,522,388,959
RAC: 2,954,432
Discovered the World's First AP27!!!Discovered 9 mega primesDiscovered 1 AP272018 Tour de Primes largest primeFound 4 primes in the 2018 Tour de PrimesFound 1 mega prime in the 2018 Tour de PrimesFound 1 prime in the 2019 Tour de PrimesFound 1 prime in the 2020 Tour de PrimesFound 1 prime in the 2021 Tour de Primes321 LLR Turquoise: Earned 5,000,000 credits (9,681,253)Cullen LLR Sapphire: Earned 20,000,000 credits (44,407,533)ESP LLR Turquoise: Earned 5,000,000 credits (6,404,450)Generalized Cullen/Woodall LLR Turquoise: Earned 5,000,000 credits (9,950,938)PPS LLR Emerald: Earned 50,000,000 credits (80,987,514)PSP LLR Turquoise: Earned 5,000,000 credits (7,863,505)SoB LLR Sapphire: Earned 20,000,000 credits (36,846,875)SR5 LLR Turquoise: Earned 5,000,000 credits (9,354,595)SGS LLR Turquoise: Earned 5,000,000 credits (5,642,496)TRP LLR Sapphire: Earned 20,000,000 credits (28,799,111)Woodall LLR Turquoise: Earned 5,000,000 credits (5,062,771)321 Sieve (suspended) Turquoise: Earned 5,000,000 credits (7,141,753)Cullen/Woodall Sieve (suspended) Turquoise: Earned 5,000,000 credits (7,892,369)Generalized Cullen/Woodall Sieve (suspended) Turquoise: Earned 5,000,000 credits (5,515,338)PPS Sieve Double Gold: Earned 500,000,000 credits (842,156,704)TRP Sieve (suspended) Silver: Earned 100,000 credits (121,416)AP 26/27 Emerald: Earned 50,000,000 credits (90,834,081)WW Emerald: Earned 50,000,000 credits (95,704,000)GFN Double Ruby: Earned 2,000,000,000 credits (4,228,019,895)
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
Send message
Joined: 19 Aug 12
Posts: 669
ID: 164101
Credit: 305,042,960
RAC: 0
GFN Double Silver: Earned 200,000,000 credits (305,042,960)
Message 147455 - Posted: 9 Jan 2021 | 11:38:47 UTC - in response to Message 147019.
Last modified: 9 Jan 2021 | 11:40:30 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.

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.

Post to thread

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

[Return to PrimeGrid main page]
DNS Powered by DNSEXIT.COM
Copyright © 2005 - 2021 Rytis Slatkevičius (contact) and PrimeGrid community. Server load 5.75, 5.59, 5.37
Generated 13 May 2021 | 21:47:26 UTC