Define the quasi-primes as follows. $\bullet$ The first quasi-prime is $q_1 = 2$ $\bullet$ For $n \ge 2$, the $n^{th}$ quasi-prime $q_n$ is the smallest integer greater than $q_{n_1}$ and not of the form $q_iq_j$ for some $1 \le i \le j \le n - 1$. Determine, with proof, whether or not $1000$ is a quasi-prime.
Problem
Source: 2019 Irish Mathematical Olympiad paper 1 p1
Tags: number theory
05.10.2020 17:03
Answer. $\boxed{\text{No}}$. $2$ is quasi-prime (it is given). $4$ is not a quasi-prime (since $2$ is quasi-prime and $4=2\cdot 2$). $8$ is quasi-prime (since $8=2\cdot 4$, where $4$ is not a quasi-prime, we get that $8$ can be quasi-prime). $5$ is quasi-prime (obviously, it is a quasi-prime after $3$). $25$ is not a quasi-prime (since $5$ is quasi-prime and $25=5\cdot 5$). $125$ is quasi-prime (since $125=5\cdot 25$, where $25$ is not a quasi-prime, we get that $125$ can be quasi-prime). Since $1000=125 \cdot 8$, and both $8$ and $125$ are quasi-primes, thus $1000$ is not a quasi-prime.
05.10.2020 18:54
In fact we can show the stronger fact that $n=\prod p_i^{\alpha_i}$ ($p_i$ all distinct primes) is good if and only if $\sum \alpha_i\equiv 1 \pmod{2}$. We can show this by strong induction. By induction hypothesis any quasi prime $<n$ has odd exponent sum, so if we multiply two of these numbers together we get an even exponent sum, so if $n$ has off exponent sum it is a quasi prime. Viceversa, if $n$ has even exponent sum and $p|n$, then $n=p\frac{n}{p}$ but both $p$ and $\frac{n}{p}$ have odd exponent sum, and so by induction hypothesis both are quasiprimes, so n isn't a quasiprime. Since $1000=2^35^3$ and $2|3+3$, it follows that $1000$ isn't a quasiprime