Competition problem — Number theory

Library / /43 of 196

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,000 problems in a working order, from AMC 10 level to the IMO shortlist.

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