phi(n)

Stan · 2011-12-05, 14:45

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

science_man_88 · 2011-12-05, 15:32

Quote:

Originally Posted by Stan

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

using PARI/GP:

Code:

(11:30)>for(x=1,1000000,if(!isprime(x) && (x-1)%eulerphi(x)==0,print(x)))
1

Stan · 2011-12-05, 16:18

Quote:

Originally Posted by science_man_88

using PARI/GP:

Code:

(11:30)>for(x=1,1000000,if(!isprime(x) && (x-1)%eulerphi(x)==0,print(x)))
1

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?

science_man_88 · 2011-12-05, 16:22

Quote:

Originally Posted by Stan

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?

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

Mr. P-1 · 2011-12-05, 21:05

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

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

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

(1) and (2) are Korselt's criterion for a Carmichael number. These aren't particularly rare, but $\prod{(p_k-1)} | n-1$ 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 10000 Carmichael numbers.

Mr. P-1 · 2011-12-05, 21:17

Quote:

Originally Posted by Stan

If this is true, is it possible to prove phi(n) divides (n- 1) implies n is prime?

We already have $\phi(n)=n-1$ 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 $\phi(n)$ .

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

Stan · 2011-12-05, 21:29

Quote:

Originally Posted by Mr. P-1

We already have $\phi(n)=n-1$ 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 $\phi(n)$ .

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

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).

Mr. P-1 · 2011-12-05, 22:10

Quote:

Originally Posted by Stan

My problem is that I have an n such that a^(n-1) = 1 mod.n.
Does this imply n is prime?

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.

Quote:

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

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

CRGreathouse · 2011-12-05, 22:28

Quote:

Originally Posted by Mr. P-1

Perhaps SM88 could modify his script to test the first 10000 Carmichael numbers.

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])))

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.

science_man_88 · 2011-12-05, 23:07

Quote:

Originally Posted by CRGreathouse

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])))

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.

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.

Mr. P-1 · 2011-12-05, 23:08

Quote:

Originally Posted by CRGreathouse

...I'm not running the same test to 2^64...

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

2011-12-05, 14:45	#1
Stan Dec 2011 2²·3² Posts	phi(n) Is it possible to find a positive composite integer n such that phi(n) divides (n - 1)?

2011-12-05, 21:05	#5
Mr. P-1 Jun 2003 7·167 Posts	$\phi(n)=n{{\prod{(p_k-1)}}\over{\prod{p_k}}}$ , where the products range over the distinct prime factors of n. if $\phi(n) \| n-1$ then $\phi(n)$ is coprime to n. Consequently n is square-free (otherwise by the above formula, n and $\phi(n)$ would have a common factor). (1) For square-free n, the above formula reduces to $\phi(n)=\prod{(p_k-1)}$ . Therefore, $\phi(n) \| (n-1)$ iff $\prod{(p_k-1)} \| n-1$ . This further implies that each $p_k-1 \| n-1$ . (2) (1) and (2) are Korselt's criterion for a Carmichael number. These aren't particularly rare, but $\prod{(p_k-1)} \| n-1$ 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 10000 Carmichael numbers. Last fiddled with by Mr. P-1 on 2011-12-05 at 21:19