Is The Probability That N And Phi(n) (totient Function) Are Coprime One ...

1. 1. Home
   2. Questions
   3. Tags
   4. Users
   5. Unanswered

Is the probability that n and phi(n) (totient function) are coprime one for random squarefree n? Ask Question Asked 14 years, 3 months ago Modified 12 years, 7 months ago Viewed 3k times 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?

• nt.number-theory
• prime-numbers

Share Cite Improve this question Follow edited Aug 6, 2010 at 12:18 Derek Jennings asked Aug 6, 2010 at 9:15 Derek JenningsDerek Jennings 55933 silver badges1010 bronze badges $\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$ – Pete L. Clark Commented 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. Commented 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$ – Derek Jennings Commented Aug 6, 2010 at 11:35
• $\begingroup$ @Derek the question is not clear, please explain more about random integer $\endgroup$ – Hashem sazegar Commented 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 Commented Aug 6, 2010 at 11:44

| Show 1 more comment

4 Answers 4

Sorted by: Reset to default Highest score (default) Date modified (newest first) Date created (oldest first) 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.

Share Cite Improve this answer Follow edited Aug 6, 2010 at 15:08 answered Aug 6, 2010 at 13:06 David E SpeyerDavid E Speyer 156k1414 gold badges418418 silver badges761761 bronze badges $\endgroup$ 1

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

Add a comment | 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$.

Share Cite Improve this answer Follow edited Aug 6, 2010 at 12:44 answered Aug 6, 2010 at 9:21 Robin ChapmanRobin Chapman 20.8k22 gold badges6666 silver badges8181 bronze badges $\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$ – Pete L. Clark Commented 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$ – Derek Jennings Commented Aug 6, 2010 at 13:08

Add a comment | 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.

Share Cite Improve this answer Follow answered Apr 16, 2012 at 21:14 Ravi ShankarRavi Shankar 2111 bronze badge $\endgroup$ Add a comment | 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?

Share Cite Improve this answer Follow answered Aug 6, 2010 at 21:00 CharlesCharles 9,11411 gold badge3838 silver badges7676 bronze badges $\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$ – Pete L. Clark Commented 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 Commented Apr 16, 2012 at 22:23

Add a comment |

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged

• nt.number-theory
• prime-numbers

.

• Featured on Meta
• More network sites to see advertising test [updated with phase 2]
• We’re (finally!) going to the cloud!
• Upcoming election announcement (2025)

Related

13 Bound the error in estimating a relative totient function 8 Probability in the Primes 9 Distribution of moduli of quadratic residues 23 Lower bounding the probability that $\gcd(t,N)≤B$, for a random $t$ and fixed (large) $N$ 0 Results regarding the relative-totient function 4 Upper-bounding the min-distance between a circle and the set of coprime integer pairs 2 Euler's totient phi and a prime Question feed Subscribe to RSS Question feed

To subscribe to this RSS feed, copy and paste this URL into your RSS reader.