# 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?

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.

• Nice +1, The $p$-adic order function usually uses $\nu_p()$, \nu. You use language to imply that there is only one "troubleshooting prime" per $a_i$, what you actually show is that any prime is a troubleshooter for only one $a_i$, which gets the result. Mar 16, 2021 at 15:53
• Yes that's a much better way to say it. Thanks! Mar 16, 2021 at 15:57
• What does the notation $V_p(.)$ mean? Mar 16, 2021 at 16:15
• $V_p(n)$ means the exponent of the prime number $p$ in the prime factorization of $n$. Mar 16, 2021 at 16:24
• @Martund p-adic order (which I sometimes called the multiplicity of a given prime in an integer) Mar 16, 2021 at 16:30

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.