mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2019-03-24, 13:01   #1
MathDoggy
 
Mar 2019

5×11 Posts
Default 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
MathDoggy is offline   Reply With Quote
Old 2019-03-24, 13:13   #2
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

2×2,969 Posts
Default

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!
CRGreathouse is offline   Reply With Quote
Old 2019-03-24, 13:26   #3
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

3·11·43 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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.
R. Gerbicz is offline   Reply With Quote
Old 2019-03-24, 13:35   #4
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

3·11·59 Posts
Default

Quote:
Originally Posted by MathDoggy View Post

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
a1call is offline   Reply With Quote
Old 2019-03-24, 23:27   #5
MathDoggy
 
Mar 2019

5×11 Posts
Default

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
MathDoggy is offline   Reply With Quote
Old 2019-04-13, 15:53   #6
MathDoggy
 
Mar 2019

5×11 Posts
Default

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
MathDoggy is offline   Reply With Quote
Old 2019-04-13, 16:01   #7
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

2×4,591 Posts
Default

Quote:
Originally Posted by MathDoggy View Post
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)
Batalov is offline   Reply With Quote
Old 2019-04-15, 13:11   #8
MathDoggy
 
Mar 2019

5×11 Posts
Default

Quote:
Originally Posted by MathDoggy View Post
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
MathDoggy is offline   Reply With Quote
Old 2019-04-17, 03:04   #9
dcheuk
 
dcheuk's Avatar
 
Jan 2019
Pittsburgh, PA

3548 Posts
Default

Quote:
Originally Posted by MathDoggy View Post
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?
dcheuk is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Primality based on digital root neskis Miscellaneous Math 1 2019-02-16 20:01
my own Integer-based LL-test not pass 3 Mprimes!? ktpn2011 Software 56 2019-01-17 06:11
Modifying the Lucas Lehmer Primality Test into a fast test of nothing Trilo Miscellaneous Math 25 2018-03-11 23:20
Primality test based on factorization of n^2+n+1 carpetpool Miscellaneous Math 5 2018-02-05 05:20
A primality test for Fermat numbers faster than Pépin's test ? T.Rex Math 0 2004-10-26 21:37

All times are UTC. The time now is 13:50.

Thu Dec 3 13:50:55 UTC 2020 up 10:02, 0 users, load averages: 1.80, 1.50, 1.35

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.