It seems no Carmichael number N below 10^21 has been found with integral [URL="http://www.chalcedon.demon.co.uk/rgep/cartable.html#Lehmeri"]Lehmer index (N-1)/phi(N)[/URL].

P.S.: See also: [URL="http://mathworld.wolfram.com/LehmersTotientProblem.html"]Lehmer's Totient Problem[/URL] and [URL="http://page.math.tu-berlin.de/~kant/ants/Poster/Pinch_Poster3.pdf"]some (apparent) update[/URL].

[QUOTE=ccorn;281156][URL="http://page.math.tu-berlin.de/~kant/ants/Poster/Pinch_Poster3.pdf"]some (apparent) update[/URL].[/QUOTE]

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 [TEX]N-1=2\varphi(N)[/TEX], [TEX]\omega(N)=\Omega(N)\ge15,[/TEX] [TEX]N>10^{30},[/TEX] and [TEX]3\not|N.[/TEX]

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 [TEX]5\not|N[/TEX] then [TEX]\omega(N)=\Omega(N)\ge26,[/TEX] but I was not able to push this far enough to remove 5 from the set above.

[TEX]N\equiv1\pmod{2^{17}};[/TEX] similarly more could be shown.

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):[LIST][*][TEX]\omega(N)=\Omega(N)\ge15[/TEX][*][TEX]N-1=2\varphi(N)[/TEX][*][TEX]N>10^{30}[/TEX][*][TEX]N\equiv1\ \pmod{2^{17}\cdot3}[/TEX][*][TEX]p|N[/TEX] with [TEX]p\in\{5,7,11,13,17\}[/TEX][/LIST]
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.

phi(n)
 

[QUOTE=Mr. P-1;281136]No, if [tex]a^{n-1} \equiv 1 ( mod n )[/tex] 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 [tex]a^{n-1} \equiv 1 (mod n)[/tex] for any a coprime to n. There are an infinite number of these too.



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

Many thanks Mr. P-1, problem solved.

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.

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.

[QUOTE=wblipp;282730]Obviously not - your own counter example proves it cannot be true.[/QUOTE]
in his [strike]counter[/strike]-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)))
[/CODE]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)))[/CODE]

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

[QUOTE=LaurV;282760]in his [strike]counter[/strike]-example 320 does NOT divide 560. [/QUOTE]

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

[QUOTE=LaurV;282760]in his [strike]counter[/strike]-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)))
[/CODE]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)))[/CODE]

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

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

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())))[/CODE]

first time something prints is 9 8 0

edit: doh forgot to use eulerphi.