Solution March 27a, 2007

Problem

Prove that for each $a\in\mathbb N$ , there are infinitely many natural $n\,$ , such that

$n|a^{n-a+1}-1\qquad\qquad(1)$

Solution

Fix $a\,$ and let $p > a$ be a prime. Let $n=(a-1)p\,$ . We will show that $n\,$ satisfies (1).

Let $x=a^{n-a+1}-1\,$ . Because $\gcd(a-1,p)=1\,$ , we just need to show that $a-1|x\,$ and $p|x\,$ .

Modulo $a-1\,$ we have $x \equiv 1^{n-a+1}-1 \equiv 0\pmod{a-1}$ , while modulo $p\,$ , $x = a^{(p-1)(a-1)}-1 \equiv 1^{a-1}-1 \equiv 0 \pmod p$ , using Fermat's little Theorem (http://en.wikipedia.org/wiki/Fermat's_little_theorem).

Because there are infinitely many primes, we can construct infinitely many solutions to (1) for a given $a\,$ this way, completing the proof.

Retrieved from "http://www.efnet-math.org/w/Solution_March_27a%2C_2007"