phi(n)
 

Is it possible to find a positive composite integer n such that phi(n) divides (n - 1)?

[QUOTE=Stan;281093]Is it possible to find a positive composite integer n such that phi(n) divides (n - 1)?[/QUOTE]
using PARI/GP:
[CODE](11:30)>for(x=1,1000000,if(!isprime(x) && (x-1)%eulerphi(x)==0,print(x)))
1[/CODE]

phi(n)
 

[QUOTE=science_man_88;281098]using PARI/GP:
[CODE](11:30)>for(x=1,1000000,if(!isprime(x) && (x-1)%eulerphi(x)==0,print(x)))
1[/CODE][/QUOTE]
I have entered the above code in PARI/GP but received no output. Does this mean there is no composite integer 0< x <1000000 for which phi(x) divides (x - 1)?
If this is true, is it possible to prove phi(n) divides (n- 1) implies n is prime?

[QUOTE=Stan;281101]I have entered the above code in PARI/GP but received no output. Does this mean there is no composite integer 0< x <1000000 for which phi(x) divides (x - 1)?
If this is true, is it possible to prove phi(n) divides (n- 1) implies n is prime?[/QUOTE]

I received that output immediately but using [url]https://oeis.org/A000010[/url] you can see a(1)=1 leading to 1|0 which is true as x*0=0 for all positive numbers at very least.

[tex]\phi(n)=n{{\prod{(p_k-1)}}\over{\prod{p_k}}}[/tex], where the products range over the distinct prime factors of n.

if [tex]\phi(n) | n-1[/tex] then [tex]\phi(n)[/tex] is coprime to n. Consequently n is square-free (otherwise by the above formula, n and [tex]\phi(n)[/tex] would have a common factor). (1)

For square-free n, the above formula reduces to [tex]\phi(n)=\prod{(p_k-1)}[/tex]. Therefore, [tex]\phi(n) | (n-1)[/tex] iff [tex]\prod{(p_k-1)} | n-1[/tex]. This further implies that each [tex]p_k-1 | n-1 [/tex]. (2)

(1) and (2) are [url=http://en.wikipedia.org/wiki/Carmichael_number#Korselt.27s_criterion]Korselt's criterion for a Carmichael number[/url]. These [url=http://oeis.org/A002997]aren't particularly rare[/url], but [tex]\prod{(p_k-1)} | n-1[/tex] is a much stronger condition, so I would expect such numbers to be rare, though I can't say for certain that none exist.

Perhaps SM88 could modify his script to test the first [url=http://oeis.org/A002997/b002997.txt]10000 Carmichael numbers[/url].

[QUOTE=Stan;281101]If this is true, is it possible to prove phi(n) divides (n- 1) implies n is prime?[/QUOTE]

We already have [tex]\phi(n)=n-1[/tex] iff n is prime, so if you're looking for a practical primality test, or even a probable primality test, then this isn't it. We already need the factors of n to be able to calculate [tex]\phi(n)[/tex].

Still I find your question interesting. Perhaps someone more knowledgeable than I can answer it.

phi(n)
 

[QUOTE=Mr. P-1;281124]We already have [tex]\phi(n)=n-1[/tex] iff n is prime, so if you're looking for a practical primality test, or even a probable primality test, then this isn't it. We already need the factors of n to be able to calculate [tex]\phi(n)[/tex].

Still I find your question interesting. Perhaps someone more knowledgeable than I can answer it.[/QUOTE]
My problem is that I have an n such that a^(n-1) = 1 mod.n.
Does this imply n is prime? Or am I chasing moonbeams?
Clearly, either (n-1) divides phi(n), in which case n is prime, or phi(n) divides (n-1).

[QUOTE=Stan;281129]My problem is that I have an n such that a^(n-1) = 1 mod.n.
Does this imply n is prime?[/QUOTE]

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.

[QUOTE]Clearly, either (n-1) divides phi(n), in which case n is prime, or phi(n) divides (n-1).[/QUOTE]

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=Mr. P-1;281123]Perhaps SM88 could modify his script to test the first [url=http://oeis.org/A002997/b002997.txt]10000 Carmichael numbers[/url].[/QUOTE]

Easier for me to do -- I have a function bfile which lets me do
[code]v=bfile(2997);
for(i=1,#v,if((v[i]-1)%eulerphi(v[i])==0,return(v[i])))[/code]

I didn't find any in that search, which goes through 1.7e12. I'm not running the same test to 2^64, but this is harder since all I have is a list of 2-pseudoprimes, which casts my net rather wider than I would have liked.

[QUOTE=CRGreathouse;281137]Easier for me to do -- I have a function bfile which lets me do
[code]v=bfile(2997);
for(i=1,#v,if((v[i]-1)%eulerphi(v[i])==0,return(v[i])))[/code]

I didn't find any in that search, which goes through 1.7e12. I'm not running the same test to 2^64, but this is harder since all I have is a list of 2-pseudoprimes, which casts my net rather wider than I would have liked.[/QUOTE]

thanks I was away for a while and hadn't been on this forum (rare) in awhile my sister was down to scan photos for a Christmas gift to someone, we went out to eat me my mom and her and then we drove her home.

[QUOTE=CRGreathouse;281137]...I'm not running the same test to 2^64...[/QUOTE]

I presume you mean "now", otherwise why tell us what you're not doing!?

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.

Mersenne Primes
 

Can anyone shed light on whether the attached theorem is true?
If it is not true, could you indicate where the problem is.[ATTACH]7576[/ATTACH]

[QUOTE=Stan;286783]Can anyone shed light on whether the attached theorem is true?
If it is not true, could you indicate where the problem is.[/QUOTE]


looks to me it assumes it's true the only proof type I know of that does that is a proof by contradiction. I also see a referral to proposition 4.1 which I don't see.

Mersenne Primes
 

Can anyone shed light on whether the attached theorem is true?
If it is not true, could you indicate where the problem is[ATTACH]7578[/ATTACH]

[QUOTE=Stan;286807]Can anyone shed light on whether the attached theorem is true?
If it is not true, could you indicate where the problem is[ATTACH]7578[/ATTACH][/QUOTE]
Check the part beginning at the fifth line from the bottom of the page.

[QUOTE=Stan;286807]Can anyone shed light on whether the attached theorem is true?
If it is not true, could you indicate where the problem is[ATTACH]7578[/ATTACH][/QUOTE]

[QUOTE][TEX]2^{n_3}= 1 (\text{ mod } n_4), ..., 2^{n_o}= 1 (\text { mod } n_1) \text { since each } n_i ,1 =< i =< 4[/TEX], is a distinct prime.[/QUOTE]

I don't see how this only applies to primes [TEX]2^{x_y}-1 = x_{y+1}[/TEX] implies [TEX]2^{x_y} = 1 \text { mod x_{y+1}}[/TEX] regardless if the sequence they are in are all prime.

[QUOTE=ccorn;286808]Check the part beginning at the fifth line from the bottom of the page.[/QUOTE]
And, regarding the fourth line from the bottom, note that
5*phi(5) | phi(33), but 25 does not divide 33.

[QUOTE=ccorn;286812]And, regarding the fourth line from the bottom, note that
5*phi(5) | phi(33), but 25 does not divide 33.[/QUOTE]
Your note is correct, but my statement says 5 has to divide 32, which it does not.