Track / Stage 6 / 166 of 400 #1166 of 1964

Problem 1166

National olympiad, first round

Number theory Difficulty 6.2 Prove it

Example 26 (18th Korean Mathematical Olympiad) Let $p$ be a prime, and
$f_{p}(x)=x^{p-1}+x^{p-2}+\cdots+x+1 \text {. }$
(1) For any integer $m$ divisible by $p$ , does there exist a prime $q$ such that $q$ divides $f_{p}(m)$ , and $q$ is coprime with $m(m-1)$ ?
(2) Prove that there are infinitely many positive integers $n$ , such that $p n+1$ is a prime.

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

$\begin{array}{l} Solution (1) Let q be any prime that divides f_{p}(m). Since f_{p}(m) \equiv 1(\bmod m), we have \\ (m, q)=1. \\ If m \equiv 1(\bmod q), then f_{p}(m) \equiv p(\bmod q), which implies q \mid p. But this leads to a contradiction (since m can be \\ divided by p), so any prime factor of f_{p}(m) satisfies the condition. \\ (2) Proof by contradiction. \\ Suppose p_{1}, p_{2}, \cdots, p_{N} are the only N primes of the form p n+1. Let m=p_{1} p_{2} \cdots p_{N} p, \\ and let q be any prime that divides f_{p}(m). By (1), we know m \neq 0,1(\bmod q). By Euler's theorem, we have \\ m^{q-1} \equiv 1(\bmod q), and m^{p} \equiv 1(\bmod q). It is easy to prove that q-1 is divisible by p, leading to a contradiction. Therefore, \\ \hline the conclusion holds. \end{array}$

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