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