mersenneforum.org I Think I Have A Primality test based on the Lehmer´s totient problem
 Register FAQ Search Today's Posts Mark Forums Read

 2019-03-24, 13:01 #1 MathDoggy   Mar 2019 5·11 Posts I Think I Have A Primality test based on the Lehmer´s totient problem Introduction: Lehmer´s totient problem is a mathematical assertion which states that there does not exist a composite positive integer x that satisfies the following: Let f(x) be Euler´s phi function Property that composite numbers do not satisfy: f(x) divides x-1 If this conjecture was proved I could formulate a primality test based on Lehmer´s problem,the primality test would be as follows: Let x be a positive integer If f(x) divides x-1 return PRIME If f(x) does not divide x-1 return COMPOSITE Well this was what I wanted to share, thank you for reading
 2019-03-24, 13:13 #2 CRGreathouse     Aug 2006 22×1,483 Posts I can improve your test. This works without assuming Lehmer's conjecture: Let x be a positive integer. If f(x) = x-1 return PRIME If f(x) < x-1 return COMPOSITE If f(x) > x-1 return UNIT Now all you have to do is find a way to compute f(x) quickly and you're done!
2019-03-24, 13:26   #3
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

17×83 Posts

Quote:
 Originally Posted by CRGreathouse Now all you have to do is find a way to compute f(x) quickly and you're done!
Much more is known. In fact if you know a "small" multiple of eulerphi(n) then you can factorize in polynomial time.

2019-03-24, 13:35   #4
a1call

"Rashid Naimi"
Oct 2015
Remote to Here/There

192910 Posts

Quote:
 Originally Posted by MathDoggy Well this was what I wanted to share, thank you for reading

Thank you very much for sharing that. I was not aware of that open problem. Quite an interesting subject.

ETA it is interesting how different
f(x) | x+1
Relates.

Last fiddled with by a1call on 2019-03-24 at 13:55

 2019-03-24, 23:27 #5 MathDoggy   Mar 2019 5·11 Posts I found an algorithm to find the values of the phi function. Algorithm: 1-gc <- function (m, n) { 2- while (1) { 3- rem <- m %% n # getting the remainder here 4- ifelse (rem == 0, break, { m = n; n = rem; }) 5- } 6- n 7-} 8- 9-# eulers phi function 10-phi <- function (n) { 11- if (n < 0) { -1 } # function's domain are positive integers only 12- sum = 0 13- for (k in 1:n) { 14- if (gc(n, k) == 1) { sum = sum + 1 } 15- } # k is a totient of n. 16-} 17- 18-value <- NULL 19-for (i in 1:1000) { 20-value <- c(val This can be programmed in C++, I don´t know if the algorithm is fast Last fiddled with by MathDoggy on 2019-03-24 at 23:27
 2019-04-13, 15:53 #6 MathDoggy   Mar 2019 5×11 Posts Counterexample to Lehmer's totient problem 2^521-1 is prime and when you put in the Phi function it is not equal to (2^521-1)-1 as Lehmer conjectured
2019-04-13, 16:01   #7
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

23·7·163 Posts

Quote:
 Originally Posted by MathDoggy Counterexample to Lehmer's totient problem 2^521-1 is prime and when you put in the Phi function it is not equal to (2^521-1)-1 as Lehmer conjectured
"This is worse than a crime; this is a mistake." (Joseph Fouche)

2019-04-15, 13:11   #8
MathDoggy

Mar 2019

5·11 Posts

Quote:
 Originally Posted by MathDoggy Counterexample to Lehmer's totient problem 2^521-1 is prime and when you put in the Phi function it is not equal to (2^521-1)-1 as Lehmer conjectured
I see the mistake

2019-04-17, 03:04   #9
dcheuk

Jan 2019
Pittsburgh, PA

3·7·11 Posts

Quote:
 Originally Posted by MathDoggy Counterexample to Lehmer's totient problem 2^521-1 is prime and when you put in the Phi function it is not equal to (2^521-1)-1 as Lehmer conjectured
I am confounded. We all know that $$p\in\text{prime}\implies\phi(p)=p-1$$, recall that the group of units for any prime number p has order (p-1).

How so that $$\phi\big(2^{521}-1\big)\neq(2^{521}-1)-1$$ but $$2^{521}-1$$ is a prime?

 Similar Threads Thread Thread Starter Forum Replies Last Post neskis Miscellaneous Math 1 2019-02-16 20:01 ktpn2011 Software 56 2019-01-17 06:11 Trilo Miscellaneous Math 25 2018-03-11 23:20 carpetpool Miscellaneous Math 5 2018-02-05 05:20 T.Rex Math 0 2004-10-26 21:37

All times are UTC. The time now is 00:26.

Wed Oct 28 00:26:15 UTC 2020 up 47 days, 21:37, 2 users, load averages: 1.56, 1.81, 1.88