phi(n) - Page 2

ccorn · 2011-12-06, 00:38

It seems no Carmichael number N below 10^21 has been found with integral Lehmer index (N-1)/phi(N).

P.S.: See also: Lehmer's Totient Problem and some (apparent) update.

CRGreathouse · 2011-12-06, 01:58

Quote:

Originally Posted by ccorn

some (apparent) update.

I had similar ideas about restricting the index to 2 (else the number is huge) and studying the prime factorization but Pinch, as usual, does a better job of it.

So if you're searching for an example below 1.24 * 10^518, you can assume $N-1=2\varphi(N)$ , $\omega(N)=\Omega(N)\ge15,$ $N>10^{30},$ and $3\not|N.$

CRGreathouse · 2011-12-06, 02:54

For the above range you can also assume that at least one prime in {5, 7, 11, 13, 17, 19} divides N. (The method can be pushed further but as I haven't automated it this is the furthest I could reasonably prove; ruling out 19 would take a large number of case arguments.)

Also if $5\not|N$ then $\omega(N)=\Omega(N)\ge26,$ but I was not able to push this far enough to remove 5 from the set above.

$N\equiv1\pmod{2^{17}};$ similarly more could be shown.

CRGreathouse · 2011-12-06, 08:43

Ignore my second paragraph above; it's based on ccorn's second link, but that page's author (Weisstein) seems to have something confused and I can't find the original.

I did show that a prime < 19 must divide N, so (again all for the case N < 1.24e518):

$\omega(N)=\Omega(N)\ge15$
$N-1=2\varphi(N)$
$N>10^{30}$
$N\equiv1\ \pmod{2^{17}\cdot3}$
$p|N$ with $p\in\{5,7,11,13,17\}$

It would be helpful to know what Wall 1980 actually said, because if it helped rule out 5 | N that would go a long way toward improving the other bounds.

Stan · 2011-12-06, 09:10

Quote:

Originally Posted by Mr. P-1

No, if $a^{n-1} \equiv 1 ( mod n )$ then we call n a Fermat probable prime to base a. An infinite number of them are composite. These are called "pseudoprimes".

The Carmichael numbers are composite numbers n such that $a^{n-1} \equiv 1 (mod n)$ for any a coprime to n. There are an infinite number of these too.

Not true. For example $2^{560} = 1 ({mod 561})$ but $\phi(561) = 320$ which neither divides nor is divisable by 560.

Many thanks Mr. P-1, problem solved.

Stan · 2011-12-18, 20:45

I am still having a problem getting to grips with the following:
Let a, n be positive integers such that (a , n) = 1.
If a^(n - 1) = 1 (mod. n) and phi(n) divides (n - 1), is n prime?

For example 2^(560) = 1 (mod 561) but phi(561) = 320 which neither divides nor is divisable by 560.
But 561 = 3.11.17 is not prime.

wblipp · 2011-12-18, 21:55

Obviously not - your own counter example proves it cannot be true.

561 is the smallest Carmichael number.

The true argument goes the other way - if p is prime, then the equivalence holds. If p is not prime, the equivalence might hold or it might not. Carmichael numbers are composite numbers for which the equivalence always holds. This happens because for every p that divides the Carmichael number, N-1 is divisible by p-1. Hence a^(N-1) = (a^(p-1))^M. Thus a^(N-1) = 1 mod p for every p dividing N, and hence for the product of those p's.

LaurV · 2011-12-19, 04:52

Quote:

Originally Posted by wblipp

Obviously not - your own counter example proves it cannot be true.

in his ~~counter~~-example 320 does NOT divide 560. Therefore is not a "counter" example.
What he said is most probably true (see Lehmer's conjecture**), phi(n) divides n-1 only for primes, always. With or without the first (Fermat) part being true or not. You maybe confused the eulerphi(n) function with the znorder(a,n) function.

Next line will print all primes up to a million.

Code:

for(n=2,10^6,a=eulerphi(n);if((c=(n-1)%a)==0, print(n"\t"a"\t"c)))

If you add a primality test, it will print nothing.

Code:

for(n=2,10^6,a=eulerphi(n);if((c=(n-1)%a)==0 && !isprime(n), print(n"\t"a"\t"c)))

** there is not any number known which is composite and phi(n) divides n-1.

wblipp · 2011-12-19, 15:31

Quote:

Originally Posted by LaurV

in his ~~counter~~-example 320 does NOT divide 560.

Hmm. I think it got fiddled with after I read it and before I responded.

science_man_88 · 2011-12-19, 15:39

Quote:

Originally Posted by LaurV

in his ~~counter~~-example 320 does NOT divide 560. Therefore is not a "counter" example.
What he said is most probably true (see Lehmer's conjecture**), phi(n) divides n-1 only for primes, always. With or without the first (Fermat) part being true or not. You maybe confused the eulerphi(n) function with the znorder(a,n) function.

Next line will print all primes up to a million.

Code:

for(n=2,10^6,a=eulerphi(n);if((c=(n-1)%a)==0, print(n"\t"a"\t"c)))

If you add a primality test, it will print nothing.

Code:

for(n=2,10^6,a=eulerphi(n);if((c=(n-1)%a)==0 && !isprime(n), print(n"\t"a"\t"c)))

** there is not any number known which is composite and phi(n) divides n-1.

couldn't a lot of the work be shortened by using the gcd(a,n)==1 check that he said ?

science_man_88 · 2011-12-19, 16:06

never mind I realized that the code didn't have everything the OP talked about in the latest question:

Code:

for(n=2,10^2,for(a=2,n,if(gcd(a,n)==1 && (a^(n-1))%n==1  && (c=(n-1)%a)==0 && !isprime(n), print(n"\t"a"\t"c);break())))

first time something prints is 9 8 0

edit: doh forgot to use eulerphi.

2011-12-06, 00:38	#12
ccorn Apr 2010 226₈ Posts	It seems no Carmichael number N below 10^21 has been found with integral Lehmer index (N-1)/phi(N). P.S.: See also: Lehmer's Totient Problem and some (apparent) update. Last fiddled with by ccorn on 2011-12-06 at 01:36

2011-12-06, 02:54	#14
CRGreathouse Aug 2006 3·1,993 Posts	For the above range you can also assume that at least one prime in {5, 7, 11, 13, 17, 19} divides N. (The method can be pushed further but as I haven't automated it this is the furthest I could reasonably prove; ruling out 19 would take a large number of case arguments.) Also if $5\not\|N$ then $\omega(N)=\Omega(N)\ge26,$ but I was not able to push this far enough to remove 5 from the set above. $N\equiv1\pmod{2^{17}};$ similarly more could be shown. Last fiddled with by CRGreathouse on 2011-12-06 at 03:02

2011-12-06, 08:43	#15
CRGreathouse Aug 2006 3·1,993 Posts	Ignore my second paragraph above; it's based on ccorn's second link, but that page's author (Weisstein) seems to have something confused and I can't find the original. I did show that a prime < 19 must divide N, so (again all for the case N < 1.24e518): $\omega(N)=\Omega(N)\ge15$ $N-1=2\varphi(N)$ $N>10^{30}$ $N\equiv1\ \pmod{2^{17}\cdot3}$ $p\|N$ with $p\in\{5,7,11,13,17\}$ It would be helpful to know what Wall 1980 actually said, because if it helped rule out 5 \| N that would go a long way toward improving the other bounds.

2011-12-18, 20:45	#17
Stan Dec 2011 44₈ Posts	phi(n) I am still having a problem getting to grips with the following: Let a, n be positive integers such that (a , n) = 1. If a^(n - 1) = 1 (mod. n) and phi(n) divides (n - 1), is n prime? For example 2^(560) = 1 (mod 561) but phi(561) = 320 which neither divides nor is divisable by 560. But 561 = 3.11.17 is not prime. Last fiddled with by Stan on 2011-12-18 at 20:49

2011-12-19, 16:06	#22
science_man_88 "Forget I exist" Jul 2009 Dumbassville 2⁶×131 Posts	never mind I realized that the code didn't have everything the OP talked about in the latest question: Code: for(n=2,10^2,for(a=2,n,if(gcd(a,n)==1 && (a^(n-1))%n==1 && (c=(n-1)%a)==0 && !isprime(n), print(n"\t"a"\t"c);break()))) first time something prints is 9 8 0 edit: doh forgot to use eulerphi. Last fiddled with by science_man_88 on 2011-12-19 at 16:09

2011-12-18, 21:55	#18
wblipp "William" May 2003 New Haven 2×7×13² Posts	Obviously not - your own counter example proves it cannot be true. 561 is the smallest Carmichael number. The true argument goes the other way - if p is prime, then the equivalence holds. If p is not prime, the equivalence might hold or it might not. Carmichael numbers are composite numbers for which the equivalence always holds. This happens because for every p that divides the Carmichael number, N-1 is divisible by p-1. Hence a^(N-1) = (a^(p-1))^M. Thus a^(N-1) = 1 mod p for every p dividing N, and hence for the product of those p's.