1
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Good Answer. I’m pretty sure you meant to multiply the two mod $N$ relations rather than add them. $\endgroup$ – Ryan Greyling Oct 16 '19 at 14:39
  • $\begingroup$ Yes,thank you for the correction $\endgroup$ – Teresa Lisbon Oct 16 '19 at 15:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.