Competition problem — Number theory

Library / /2 of 16

Number theory Difficulty 4.9 AIME Prove it Romania

Let $n$ be an integer greater than $2$ and consider the set $A = \{2^n - 1, 3^n - 1, \dots, (n-1)^n - 1\}$ . Given that $n$ does not divide any element of $A$ , prove that $n$ is a square-free number. Does it necessarily follow that $n$ is a prime number?

Marius Bocanu

Solution

Suppose not and write $n = p a$ for a prime $p$ and a number $a > 1$ with $p \mid a$ . Notice that $(a+1)^n - 1 = a((a+1)^{n-1} + (a+1)^{n-2} + \dots + 1)$ and $a+1 \equiv 1 \pmod{p}$ to infer that $n$ divides $(a+1)^n - 1$ , a contradiction.

Further, $n$ needs not be a prime number; take for example $n = 15 = 3 \cdot 5$ .

Looking for a route rather than 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 and solution reproduced as published; topic and difficulty added by this site.