3
$\begingroup$

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?

$\endgroup$

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
5
  • 1
    $\begingroup$ 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. $\endgroup$
    – Joffan
    Mar 16, 2021 at 15:53
  • 1
    $\begingroup$ Yes that's a much better way to say it. Thanks! $\endgroup$
    – Aryan
    Mar 16, 2021 at 15:57
  • $\begingroup$ What does the notation $V_p(.)$ mean? $\endgroup$
    – Martund
    Mar 16, 2021 at 16:15
  • 1
    $\begingroup$ $V_p(n)$ means the exponent of the prime number $p$ in the prime factorization of $n$. $\endgroup$
    – Aryan
    Mar 16, 2021 at 16:24
  • $\begingroup$ @Martund p-adic order (which I sometimes called the multiplicity of a given prime in an integer) $\endgroup$
    – Joffan
    Mar 16, 2021 at 16:30
1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

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