Track / Stage 6 / 327 of 400 #1807 of 2444

Problem 1807

National Olympiad, first round

Number theory Difficulty 6.7 Prove it NMO Selection Tests For The Junior Balkan Mathematical Olympiad · Romania

It is said that a positive integer $n > 1$ has the property ( $p$ ) if in its prime factorization
$n = p_1^{\alpha_1} \cdots p_j^{\alpha_j}$
at least one of the prime factors $p_1, \dots, p_j$ has the exponent equal to 2.

a) Find the largest number $k$ for which there exist $k$ consecutive positive integers that do not have the property ( $p$ ).
b) Prove that there is an infinite number of positive integers $n$ such that $n, n + 1$ and $n + 2$ have the property ( $p$ ).

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

a) Among any 8 consecutive integers there exists one of the form $8j + 4$ . This number has the property ( $p$ ) because the factor 2 from its prime factorization has the exponent 2. Therefore there can be at most 7 consecutive positive integers that do not have the property ( $p$ ). Since none of the numbers 29, 30, 31, 32, 33, 34, 35 has the property ( $p$ ), the largest $k$ is $k = 7$ .

b) Since the numbers $98 = 2 \cdot 7^2$ , $99 = 3^2 \cdot 11$ , and $100 = 2^2 \cdot 5^2$ have the property ( $p$ ), so will the numbers $98 + (7 \cdot 3 \cdot 2)^3 \cdot k$ , $99 + (7 \cdot 3 \cdot 2)^3 \cdot k$ , and $100 + (7 \cdot 3 \cdot 2)^3 \cdot k$ .

Alternative solution.

By the Chinese remainder theorem, there exist an infinite number of solutions for the system of simultaneous congruences: $n \equiv 4 \pmod{8}$ , $n \equiv 8 \pmod{27}$ , $n \equiv 23 \pmod{125}$ . Then $n, n + 1$ , and $n + 2$ all have the property ( $p$ ) because the factor 2, 3, and 5, respectively, has the exponent 2 in their prime factorizations.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.