For every positive integer $a$, find a composite number $n$ such that $n|a^n -a$.

Question

For every positive integer $a$, find a composite number $n$ such that $n|a^n -a$.

Solution:

We have

$ a^n - a$

$ = a[a^{(n-1)}-1]$

If a=n, then $n|a^n -a$

Is this the way to do it or do I need to do it in another way?

Answer 1

You're done when $a$ is composite itself. When $a=1$, just pick any composite $n$. When $a$ is an odd prime, let $n=2a$, then clearly $a^n-a$ is even i.e. $2\mid a^n-a$, and obviously $a\mid a^n-a$, as $\gcd(2,a)=1$, we have $2a\mid a^n-a$.

$a=2$ is tricky. I did a computer search, and $n = 341 = 11 \cdot 31$ is the minimal solution.

As commented below, this is the smallest Fermat psuedoprime to base $2$. Wikipedia mentioned a method to construct them by Cipolla, with $341$ given as an example.