# Composite $n$ such that $3^{n-1}-2^{n-1}$ is divisible by $n$

I'm stuck with the following olympiad problem (the solution to which I unfortunately do not possess):

Show that there are infinitely many composite (i. e. nonprime) numbers $n$ such that $3^{n-1}-2^{n-1}$ is divisible by $n$.

Could anyone provide a hint how to tackle this exercise?

• Any Carmichael number coprime to both $2$ and $3$ satisfies this, but the fact that there are infinitely many such numbers is not trivial... – Milo Brandt Feb 22 '15 at 17:54

## 1 Answer

Hint: $n=3^8+2^8 = 6817 = 17\cdot 401$ is a non-prime number $\equiv 1\pmod{32}$, hence for sure $n\mid\left(3^{n-1}-2^{n-1}\right)$, since:

$$3^{32k}-2^{32k} = \left(3^{16k}+2^{16k}\right)\color{red}{\left(3^{8k}+2^{8k}\right)}\left(3^{4k}+2^{4k}\right)\left(3^{2k}+2^{2k}\right)\left(3^{k}+2^{k}\right)\left(3^{k}-2^{k}\right)$$ and $3^8+2^8$ divides $3^{8k}+2^{8k}$ if $k$ is odd.

Now prove that for an infinite number of $m$s we have that: $$n = 3^{2^m}+2^{2^m}$$ is non-prime and $n\mid\left(3^{n-1}-2^{n-1}\right)$.