For relatively prime positive integers $a$ and $b$ and a natural number $n$, if a prime $p$ divides $a^n-b^n$ then either $p$ divides $a^d-b^d$ for some divisor $d$ of $n$ such that $d<n$, or $p\equiv 1 \mod{n}$.
Here's what I have so far. I know $\text{gcd}(n,p-1)\leq n$ and if $\text{gcd}(n,p-1)=n$ then $n$ divides $p-1$ so $$p\equiv 1\mod{n}$$ Otherwise choose $d=\text{gcd}(n,p-1)<n$ as a divisor of $n$. Then for $a,b>1$ I must show that $p$ divides $$a^{\text{gcd}(n,p-1)}-b^{\text{gcd}(n,p-1)}$$ $$=(a^{\text{gcd}(n,p-1)}-1)-(b^{\text{gcd}(n,p-1)}-1)$$ $$*=\text{gcd}(a^n-1,a^{p-1}-1)-\text{gcd}(b^n-1,b^{p-1}-1)$$ The case where $a=1$ or $b=1$ is already proven in my textbook. And I also know that $p$ divides $a^{p-1}-1$ and $b^{p-1}-1$ by Fermat's Little Theorem, but I don't know where to go from here.
*This is the step that requires $a,b>1$.
Best Answer
All you need to show is that for relatively prime $a,b$ and positive integers $m,n$, we have $\gcd(a^m - b^m , a^n - b^n) = a^{\gcd(m,n)} - b^{\gcd(m,n)}$.
Clearly the RHS divides the LHS From the popular $c| d \implies a^c - b^c | a^d - b^d$. For the reverse, let integers $x,y$ satisfy $mx+ny = \gcd(m,n)$ . Note that $a,b$ are both coprime and hence both are coprime to $N := \gcd(a^m - b^m , a^n - b^n)$ and have inverses mod this number(So even if $x,y$ are negative we are ok). then $a^{m} \equiv b^{m}\mod N $ and $a^n \equiv b^n \mod N$. Now take power $x$ on the first, power $y$ on the second(which you can do even though $x,y$ may be negative by relative primality) and multiply to get $a^{\gcd (m,n)} \equiv b^{\gcd(m,n)} \mod N$. Hence $N$ divides the RHS, so equality is obtained.
From here, if a prime $p$ divides $a^n - b^n$ then we know that neither $a$ nor $b$ is a multiple of $p$ (otherwise both will have to be multiples of $p$, contradicting relative primality) therefore $a^{p-1} - b^{p-1}$ is a multiple of $p$. It follows that if $k = \gcd(n,p-1)$ then $a^k-b^k$ is a multiple of $p$. If $n$ doesn't divide $p-1$ then the first case arises, else $p \equiv 1 \mod n$.