- **Miscellaneous Math**
(*https://www.mersenneforum.org/forumdisplay.php?f=56*)

- - **I Think I Have A Primality test based on the Lehmer´s totient problem**
(*https://www.mersenneforum.org/showthread.php?t=24201*)

I Think I Have A Primality test based on the Lehmer´s totient problemIntroduction: 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 |

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! |

[QUOTE=CRGreathouse;511652]
Now all you have to do is find a way to compute f(x) quickly and you're done![/QUOTE] Much more is known. In fact if you know a "small" multiple of eulerphi(n) then you can factorize in polynomial time. |

[QUOTE=MathDoggy;511651]
Well this was what I wanted to share, thank you for reading[/QUOTE] 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. |

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 |

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 |

[QUOTE=MathDoggy;513609][STRIKE]Counterexample to Lehmer's totient problem[/STRIKE]
2^521-1 is prime and when you put in the Phi function it is not equal to (2^521-1)-1 [STRIKE]as Lehmer conjectured[/STRIKE][/QUOTE] "This is worse than a crime; this is a mistake." (Joseph Fouche) |

[QUOTE=MathDoggy;513609]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[/QUOTE] I see the mistake |

[QUOTE=MathDoggy;513609]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[/QUOTE] 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? |

All times are UTC. The time now is 04:16. |

Powered by vBulletin® Version 3.8.11

Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.