mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2008-05-25, 16:18   #1
boleg
 

7·13·83 Posts
Default a^x=x (mod p)

Are there any results concerning the following problem: given p - prime, 1<a<p find 0=<x<p such that a^x = x (mod p)?
  Reply With Quote
Old 2008-05-27, 02:42   #2
lavalamp
 
lavalamp's Avatar
 
Oct 2007
Manchester, UK

2·3·223 Posts
Default

There are 6 before you even enter double digits.
Code:
2^3 = 3 mod 5
3^2 = 2 mod 7
3^4 = 4 mod 7
3^5 = 5 mod 7
4^2 = 2 mod 7
4^4 = 4 mod 7
Generated in PARI/GP with:
Code:
c=0;

forprime(p=2,10, for(a=2,p, for(x=0,p, if(lift(Mod(a^x,p))==x, c++;print(a,"^",x," = ",x," mod ",p) ) )));

print(c);
There are 38 results for p<20, 969 for p<100 and 75434 for p<1000, but I won't list them here since you have the code now.

Edit: Limiting a and x to primes aswell produces 3 results with p<10, 12 with p<20, 101 with p<100 and 2750 with p<1000.

Edit2: The highest result for p<1000 is 995^803 = 803 mod 997.

Last fiddled with by lavalamp on 2008-05-27 at 03:02
lavalamp is offline   Reply With Quote
Reply

Thread Tools


All times are UTC. The time now is 06:47.

Tue Jan 26 06:47:01 UTC 2021 up 54 days, 2:58, 0 users, load averages: 2.54, 2.92, 2.78

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.