For an integer $n \ge 2$, let $\omega (n)$ denote the number of distinct prime divisors of $n$ and $\pi (n) $ be number of primes not exceeding $n$.

Let $a_1, \ldots, a_k$ be integers greater than $1$ and less than $n$ such that they are mutually relatively prime i.e. $\gcd(a_i, a_j) = 1$ for $i \ne j$ and $\gcd(a_i, n) = 1, \forall i = 1(1)k$; then of course any prime $p$ dividing one of the $a_i $'s cannot divide any other $a_j$ and not also $n$ and any such prime divisor of course does not exceed $n$ ; hence we can write $\omega(n) + \sum\omega(a_i)\le\pi(n)$.

It is also clear that $k \le \phi(n) - 1$; what can be the maximum possible value of $k$ depending on each $n$ i.e. what is the maximum number of integers greater than $1$ and less than a given $n$ that are relatively prime to $n$ and are also mutually co-prime? Can it ever reach $\phi(n) - 1$? When does the equality hold in $\omega(n) + \sum\omega(a_i)\le\pi(n)$?

In particular, when do we have $\omega(n-1) + \omega(n) = \pi(n)$ that is when does $p$ a prime $p \le n , \implies p|n$ , or $p|n-1 $? Is there anything about this in the known literature?


Let $n>2$. Then clearly the number of primes which divide $n$ plus the number of primes less than $n$ which do not divide $n$ are equal to $\pi(n)$.
$$\Rightarrow\omega(n)+\Sigma\omega(a_i)=\pi(n)$$ if we choose the $a_i$'s to be all the primes which don't divide $n$.

Now if we wish to find $\phi(n)-1$ numbers pairwise relatively prime and relatively prime to $n$ we will fail after a certain point.

We know that $\phi(n)\geq \pi(n)+1$ if $n\geq 91$ so, $$\phi(n)-1\geq \pi(n)$$ Suppose that $\phi(n)-1$ numbers are pairwise relatively prime and relatively prime to $n$.
This means we have $\phi(n)-1+\omega(n)\geq \phi(n)-1+1\geq \pi(n)+1$ numbers less than $n$ pairwise relatively prime.
But this is impossible since each number has a prime divisor and this would give $\pi(n)+1$ prime divisors -and generally primes- less than $n$(a contradiction)

(If you wish to include the number $1$ in your list of the $a_i$ you could just delay the impossibility:Sooner or later $\phi(n)$ will be much greater than $\pi(n)$ by any constant.You speak about numbers greater than $1$ but just to give you a hint)

So, you have to check the numbers not greater than $91$.
Always, the maximum number of terms relatively prime to $n$ which are also pairwise relatively prime is $$\pi(n)-\omega(n)+1$$
(if you include $1$)

For your last question

If $\omega(n-1)+\omega(n)=\pi(n)$ then $$2\cdot 3\cdot 5\cdots p_k\leq n^2-n$$ which is going to fail again after a certain point.
Note that $$\ln(2\cdot 3\cdot 5\cdots p_k)\sim p_{k+1}$$
Check the Prime Number Theorem


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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