20190324, 13:01  #1 
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 x1 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 x1 return PRIME If f(x) does not divide x1 return COMPOSITE Well this was what I wanted to share, thank you for reading 
20190324, 13:13  #2 
Aug 2006
2×2,969 Posts 
I can improve your test. This works without assuming Lehmer's conjecture:
Let x be a positive integer. If f(x) = x1 return PRIME If f(x) < x1 return COMPOSITE If f(x) > x1 return UNIT Now all you have to do is find a way to compute f(x) quickly and you're done! 
20190324, 13:26  #3 
"Robert Gerbicz"
Oct 2005
Hungary
2×709 Posts 

20190324, 13:35  #4 
"Rashid Naimi"
Oct 2015
Remote to Here/There
2·7·139 Posts 
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 20190324 at 13:55 
20190324, 23:27  #5 
Mar 2019
5·11 Posts 
I found an algorithm to find the values of the phi function.
Algorithm: 1gc < 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 10phi < 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 18value < NULL 19for (i in 1:1000) { 20value < c(val This can be programmed in C++, I don´t know if the algorithm is fast Last fiddled with by MathDoggy on 20190324 at 23:27 
20190413, 15:53  #6 
Mar 2019
5·11 Posts 
Counterexample to Lehmer's totient problem
2^5211 is prime and when you put in the Phi function it is not equal to (2^5211)1 as Lehmer conjectured 
20190413, 16:01  #7 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
9,161 Posts 

20190415, 13:11  #8 
Mar 2019
5×11 Posts 

20190417, 03:04  #9  
Jan 2019
Pittsburgh, PA
236_{10} Posts 
Quote:
How so that \(\phi\big(2^{521}1\big)\neq(2^{521}1)1\) but \(2^{521}1\) is a prime? 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Primality based on digital root  neskis  Miscellaneous Math  1  20190216 20:01 
my own Integerbased LLtest not pass 3 Mprimes!?  ktpn2011  Software  56  20190117 06:11 
Modifying the Lucas Lehmer Primality Test into a fast test of nothing  Trilo  Miscellaneous Math  25  20180311 23:20 
Primality test based on factorization of n^2+n+1  carpetpool  Miscellaneous Math  5  20180205 05:20 
A primality test for Fermat numbers faster than Pépin's test ?  T.Rex  Math  0  20041026 21:37 