Some questions about prime divisors and number of primes

Question

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?

Answer 1

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