# For relatively prime $a$ and $b$, if a prime $p$ divides $a^n-b^n$ then we one of two cases

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, 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) 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$$.

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$$.
• Good Answer. I’m pretty sure you meant to multiply the two mod $N$ relations rather than add them. – Ryan Greyling Oct 16 '19 at 14:39