elementary number theory - Prove that if $7^n-3^n$ is divisible by $n>1$, then $n$ must be even.

I tried using factorization of $a^n-b^n$ for odd $n$ in an attempt to work through to a situation where the factors are such that they cannot have n as a factor. But I reached nowhere. Here's how I proceeded -

$$a^n-b^n=(a-b)\left(a^{n-1}+a^{n-2}b+a^{n-3}b^2+\dots+a^2b^{n-3}+ab^{n-2}+b^{n-1}\right)$$

a-b=4 and can be ignored.

The latter term is essentially odd and not divisible by any odd number till $9$ (easy to prove without getting into calculations).

However, for some arbitrary odd number $x=p^k$ where $p \ge 11$ is prime, I cannot say whether the sum of two terms is divisible by $x$ or not when the two terms are individually not divisible by $x$.

Answer

This is one of my favorite number theory problems because of the neat trick below :

Assume that $n$ is odd .
Let $p$ be the smallest prime factor of $n$ (it's obviously odd and can't be $3$ or $7$)

From Fermat's little theorem :

$$7^{p-1}-3^{p-1} \equiv 1-1 \equiv 0 \pmod{p}$$

Also you know that :

$$p \mid n \mid 7^n-3^n$$

Now I'll use a standard lemma easily provable by induction :

Lemma
If $a,b,n,m$ are positive integers and $(a,b)=1$ then :
$$(a^n-b^n,a^m-b^m)=a^{(n,m)}-b^{(n,m)}$$

Use this lemma here so :

$$p \mid (7^{p-1}-3^{p-1},7^n-3^n)=7^{(n,p-1)}-3^{(n,p-1)}$$

Here comes the awesome part :

Because $p$ is the smallest prime factor of $n$ we must have $(p-1,n)=1$ .
To see this assume that there is a prime $q$ such that $q \mid n$ and $q\mid p-1$ this means that $q

$(n,p-1)=1$ so we can simplify :

$$p \mid 4$$ which is a contradiction because $p$ is odd .