Maths Olympiad Prep

Library / /234 of 520

Number theory Difficulty 6.0 National olympiad Prove it

Example 1 Proof: For any positive integer nn, there exist nn consecutive positive integers, none of which is a power of a prime (and thus, none of them is a prime).

Solution

Proof:
A basic idea is: to find nn consecutive positive integers, each of which has two distinct prime factors. For this, for any nNn \in \mathbf{N}^{*}, take 2n2n different primes p1,p2,,pn;q1,q2,,qnp_{1}, p_{2}, \cdots, p_{n}; q_{1}, q_{2}, \cdots, q_{n}. By the Chinese Remainder Theorem, there exists mNm \in \mathbf{N}^{*}, such that
mk(modpkqk),k=1,2,,nm \equiv -k \left(\bmod p_{k} q_{k}\right), k=1,2, \cdots, n

hold simultaneously. Then in the nn consecutive positive integers: m+1,m+2,,m+nm+1, m+2, \cdots, m+n, each number has two distinct prime factors, and the proposition is proved.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.