Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

The probability that a prime p does not divide a random integer n is (1-1/p), so for random n we could argue that the probability that n and φ(n) are coprime is

$\prod_{p|n} \left(1-1/p \right) = \phi(n)/n.$

The average order of φ(n)/n is given by

${ 1 \over N } \sum_{n=1}^N {\phi(n) / n} = 6/\pi^2 + O(\log N/N).$

Now the probability that a random integer is squarefree is $6/\pi^2$.

So my question is: does gcd(n,φ(n))=1 for almost all squarefree n? Or to put it another way, for random squarefree n is the probability that n and φ(n) are coprime one? (Of course we have gcd(55,φ(55))=5, etc.)

I have not been able to find anything about this on the internet and so would like to know if this has been considered before. Thanks.

EDIT: Take integer N and let f(N) = number of squarefree n<=N such that gcd(n,φ(n))>1 (e.g. 21 or 55). Does f(N)/q(N) tend to zero as N tends to infinity, where q(N) is the number of squarefree numbers <= N?

share|improve this question
1  
Maybe the question can be salvaged by asking "What is the density of the set of squarefree integers $n$ such that $\operatorname{gcd}(n,\varphi(n)) = 1$?" –  Pete L. Clark Aug 6 '10 at 10:15
1  
Does your definition of $n$ require that $n$ is odd? Or am I missing something here? –  j.p. Aug 6 '10 at 11:08
    
What I'm asking is does the proportion of squarefree integers <= N, say, for which gcd(n,phi(n))>1 (1<=n<=N) tend to zero as N tends to infinity? Sorry if this was not clear. –  Derek Jennings Aug 6 '10 at 11:35
    
@Derek the question is not clear, please explain more about random integer –  Hashem sazegar Aug 6 '10 at 11:44
3  
Just to give some additional interest to this question: $n$ is square free and coprime with $\phi(n)$ exactly when all groups of order $n$ are cyclic. See mathoverflow.net/questions/11001/… –  lhf Aug 6 '10 at 11:44
show 1 more comment

4 Answers 4

Quite the reverse is true: The probability that $n$ and $\phi(n)$ are relatively prime is zero! More precisely, the ratio $$\frac{1}{N} \cdot \# \{ n : \ n \leq N \ (n, \phi(n))=1 \}$$ goes to $0$ as $N$ goes to $\infty$.

Proof: Fix a positive real number $\epsilon$, we will prove that this ratio is less than $\epsilon$ for $N$ sufficiently large. The product $(1-1/2)(1-1/3)(1-1/5)(1-1/7)(1-1/11) \cdots$ is zero (because $\sum 1/p$ diverges); choose $P$ such that $\prod_{p < P} (1-1/p) < \epsilon/2$.

We claim that, for $N$ sufficiently large:

  • The proportion of $n$ which are not divisible by some prime less than $P$ is $< \epsilon/2$.

  • The proportion of $n$ for which $\prod_{p < P} p$ does not divide $\phi(n)$ is $< \epsilon /2$.

So, with probability $> 1-\epsilon$, the GCD of $n$ and $\phi(n)$ is divisible by some prime less than $P$.

The first bullet point is easy: The density of primes not divisible by some prime less than $P$ is $\prod_{p < P} (1-1/p) + O(1/N) < \epsilon/2 + O(1/N)$.

For the second part, fix a prime $p$ less than $P$. The sum $$\sum_{\begin{smallmatrix} q \equiv 1 \mod p \\ q \ \mbox{prime} \end{smallmatrix}} \frac{1}{q}$$ diverges, by a quantitative version of Dirichlet's theorem. So we can find $Q$ such that $$\prod_{\begin{smallmatrix} q \equiv 1 \mod p \\ q \ \mbox{prime} \\ q \leq Q \end{smallmatrix}} (1- 1/q)$$ is arbitrarily small. Letting $K$ be the number of primes less than $P$, choose $Q$ such that this product is less than $\epsilon/(2K)$.

The probability that $p$ does not divide $\phi(n)$ is bounded above by the probability that $n$ is divisible by none of the primes in the above product. We constructed that probability to be less than $\epsilon/(2K)$.

So, for each of the $K$ primes $p$ less than $P$, the probability that $p$ does not divide $\phi(n)$ is less than $\epsilon/(2K)$. This establishes the second bullet point.

share|improve this answer
1  
Shouldn't the last formula be a product and not a sum? –  Victor Miller Aug 6 '10 at 13:56
    
Thanks for the correction! –  David Speyer Aug 6 '10 at 15:09
add comment

I'm not sure what you mean by a random integer $n$, but would you agree that the probability that a random squarefree integer be divisible by $55$ is nonzero? For if $55\mid n$ then $5\mid\gcd(n,\phi(n))$.

Added In Derek's new notation it's well-known that $q(N)\sim 6N/\pi^2$. This constant arises via $$\frac6{\pi^2}=\prod_p \left(1-\frac1{p^2}\right).$$ Sticking to the example of the number $55$, if $g_{55}(n)$ is the number of squarefree numbers up to $n$ that are divisible by $55$ then $g_{55}(n)=h_{55}(n/55)$ where $h_{55}(n)$ is the number of squarefree numbers up to $n$ that are not divisible by $55$. But $h_{55}(n)\sim\alpha n$ where $\alpha$ is the same Euler product with the $p=5$ and $p=11$ terms dropped: $$\alpha=\frac6{\pi^2}\frac{5^2\times 11^2}{24\times 120}.$$ Thus $$\frac{g_{55}(n)}{q(n)}\to\frac{55}{24\times 120}=\frac{11}{576}$$ as $n\to\infty$, but of course $f(n)/q(n)\ge g_{55}(n)/q(n)$.

Of course one can perform this argument with other numbers in place of $55$.

share|improve this answer
2  
I was really burning some brain cells wondering why you picked $55$ (why not $2$??) until I looked back at the question and saw that you were responding to the OP's use of $55$. Anyway, I think you have understood the question properly and answered it. ("No.") –  Pete L. Clark Aug 6 '10 at 10:13
    
Thanks. I should have thought about it a little longer. It was the presence of the term 6/&pi;^2 in the average order of &phi;(n)/n that caused a some overly hasty excitement :-) –  Derek Jennings Aug 6 '10 at 13:08
add comment

The asymptotics of the "cyclic numbers", i.e., numbers 'n' such that gcd(n,phi(n)) = 1 was worked out by Erdos in 1948. If I recall the numbers of such numbers less than n is asymptotically n*e^{-\gamma}/(log(log(n))).

The asymptotics of abelian and nilpotent numbers is not known. By the way, the term cyclic numbers was coined in our paper (Shankar and Pakianathan) although the problem of determining such numbers itself goes back to Burnside.

share|improve this answer
add comment

Also relevant is Sloane's A060679, orders of non-cyclic groups, which is $n$ such that $\gcd(n,\phi(n))>1$, and its complement A003277. Although the asymptotic density of the latter tends to zero, as David Speyer showed in one of the answers, they're not rare: one in 3 at 30,000, as the b-file shows. This is denser than the primes at that point. I wonder what asymptotic order they have?

share|improve this answer
    
Via the connection to "cyclic numbers" (see lhf's comment to the question itself), this is something that Carl Pomerance was thinking about when he visited UGA a couple of years ago. He indicated that this and analogous issues (e.g. with abelian numbers, nilpotent numbers...) might make interesting problems for a student. I'm sure he would not mind if you contacted him about it. –  Pete L. Clark Aug 7 '10 at 1:10
    
I see now that Erdos proved that they vary as n log log log n times a constant. –  Charles Apr 16 '12 at 22:23
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.