Library / All-Soviet-Union Mathematical Olympiad /39 of 185

All-Soviet-Union Mathematical Olympiad

Number theory Difficulty 4.7 AIME Prove it Soviet Union

Problem:

Prove that we can find positive integers $x$ , $y$ satisfying $x^{2} + x + 1 = p y$ for an infinite number of primes $p$ .

Solution

Solution:

This is a trivial variant on the proof that there are an infinite number of primes. Suppose that we can only find $x$ , $y$ for a finite number of primes $p_1$ , $p_2$ , ..., $p_n$ . Set $x = p_1 p_2 \dots p_n$ . Then none of the $p_i$ can divide $x(x + 1) + 1$ . But it must have prime factors. Contradiction.

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

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