We have $n$ numbers less than a given number $k$ such that none of the numbers divides the product of other $n-1$ numbers. How do you prove that $n$ can't be more than the number of primes below $k$?
My try
Suppose not. Then $n$ is more than the number of primes below $k$, so one of the given numbers has to be composite. But then how would I get a contradiction?
 A: The condition can be rewritten as $a_i^2\not|\displaystyle\prod_{j=1}^n{a_j}$ where $a_i$'s are our $n$ chosen numbers.
Then for each $a_i$ there exists a prime number $p_i$ such that $$V_{p_i}(a_i^2)>V_{p_i}(\displaystyle\prod_{j=1}^n{a_j})$$ Otherwise $a_i^2|\displaystyle\prod_{j=1}^n{a_j}$
Name $p_i$ as the troubleshooting prime of $a_i$. Then if some prime number $p$ is the troubleshooting prime of both $a_s$ and $a_t$, then we'll have :
$$V_{p}(a_s^2)=2V_{p}(a_s)>V_{p}(\displaystyle\prod_{j=1}^n{a_j})=\displaystyle\sum_{j=1}^n{V_p(a_j)}$$
$$V_{p}(a_t^2)=2V_{p}(a_t)>V_{p}(\displaystyle\prod_{j=1}^n{a_j})=\displaystyle\sum_{j=1}^n{V_p(a_j)}$$
Now WLOG assume that $V_p(a_s)\geqslant V_p(a_t)$. Then :
$$2V_p(a_t)\leqslant V_p(a_s)+V_p(a_t)\leqslant\displaystyle\sum_{j=1}^n{V_p(a_j)}$$
And this contradicts the second result. So we conclude that each prime number can be the troubleshooting prime of at most one of the $a_i$ and therefore there can at most be $\pi(k)$ different numbers.
A: This is actually quite simple. Suppose there exists some $m$ in the group such that it has prime decomposition $p_1^{m_1}p_2^{m_2}\ldots p_d^{m_d}$, and for each $p_i$, there exists another number in the group with prime factorization including $p_i$ to a power at least as high as $m_i$. Then, $m$ clearly divides the product of the other numbers. So this is a contradiction.
This shows that each number $m$ in the group is associated with a prime $p$ such that there exists some $k\in\mathbb N$ such that $p^k\mid m$, and for any $j\neq m$ in the group, $p^k\not\mid j$. Thus, we have an injection from the group of numbers into the prime numbers.
