TAOCP 4.5.4 Exercise 3
Let P=\prod_{p\le 1000} p, where the product extends over all prime numbers not exceeding $1000$.
Section 4.5.4: Factoring into Primes
Exercise 3. [M20] Show that there is a number $P$ with the following property: If $1000 \le n \le 1000000$, then $n$ is prime if and only if $\gcd(n, P) = 1$.
Verified: yes
Solve time: 7m54s
Solution
Let
$$ P=\prod_{p\le 1000} p, $$
where the product extends over all prime numbers not exceeding $1000$.
We shall prove that for every integer $n$ with
$$ 1000\le n\le 10^6, $$
$$ n \text{ is prime } \Longleftrightarrow \gcd(n,P)=1. $$
If $n$ is prime, then $\gcd(n,P)=1$
Assume that $n$ is prime and $1000\le n\le 10^6$.
Every prime divisor of $P$ is at most $1000$. Since $n$ is prime and $n\ge 1000$, the only way $n$ could divide $P$ would be if $n\le1000$. The only prime equal to $1000$ does not exist, so in fact $n>1000$.
Hence $n$ is not among the prime factors occurring in $P$. Therefore $n$ and $P$ have no common prime factor, and
$$ \gcd(n,P)=1. $$
If $\gcd(n,P)=1$, then $n$ is prime
Assume that
$$ 1000\le n\le 10^6 $$
and
$$ \gcd(n,P)=1. $$
Suppose, for contradiction, that $n$ is composite.
Then $n$ has a prime divisor $q$ with
$$ q\le \sqrt n. $$
Since $n\le 10^6$,
$$ q\le \sqrt{10^6}=1000. $$
Thus $q$ is a prime not exceeding $1000$. By the definition of $P$, every such prime divides $P$, so
$$ q\mid P. $$
Also $q\mid n$. Hence $q$ is a common divisor of $n$ and $P$, which implies
$$ \gcd(n,P)\ge q>1. $$
This contradicts the assumption $\gcd(n,P)=1$.
Therefore $n$ cannot be composite. Hence $n$ is prime.
Conclusion
For every integer $n$ with $1000\le n\le 10^6$,
$$ n \text{ is prime} \quad\Longleftrightarrow\quad \gcd(n,P)=1, $$
where
$$ P=\prod_{p\le1000} p. $$
Therefore such a number $P$ exists. ∎