4
$\begingroup$

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?

$\endgroup$
6
  • 1
    $\begingroup$ 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$?" $\endgroup$ Aug 6, 2010 at 10:15
  • 1
    $\begingroup$ Does your definition of $n$ require that $n$ is odd? Or am I missing something here? $\endgroup$
    – j.p.
    Aug 6, 2010 at 11:08
  • $\begingroup$ 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. $\endgroup$ Aug 6, 2010 at 11:35
  • $\begingroup$ @Derek the question is not clear, please explain more about random integer $\endgroup$ Aug 6, 2010 at 11:44
  • 3
    $\begingroup$ 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/… $\endgroup$
    – lhf
    Aug 6, 2010 at 11:44

4 Answers 4

8
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ Shouldn't the last formula be a product and not a sum? $\endgroup$ Aug 6, 2010 at 13:56
6
$\begingroup$

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

$\endgroup$
2
  • 2
    $\begingroup$ 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.") $\endgroup$ Aug 6, 2010 at 10:13
  • $\begingroup$ 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 :-) $\endgroup$ Aug 6, 2010 at 13:08
2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ Aug 7, 2010 at 1:10
  • $\begingroup$ I see now that Erdos proved that they vary as n log log log n times a constant. $\endgroup$
    – Charles
    Apr 16, 2012 at 22:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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