Competition problem — Number theory

Library / /251 of 520

Number theory Difficulty 6.1 National olympiad Prove it

1 Prove that for any integer $a \geqslant 3$ , there are infinitely many positive integers $n$ such that $a^{n}-1$ is divisible by $n$ . (Please compare Example 2 of Unit 8.)

Solution

1. Since $a \geqslant 3$ , it follows that $a-1$ has a prime factor $p$ . By Fermat's Little Theorem, we know that $a^{p} \equiv a \equiv 1(\bmod p)$ . Using induction, it is easy to prove that $n=p^{k}(k=1,2, \cdots)$ all meet the requirements.

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.