# $n \mid (a^{n}-b^{n}) \ \Longrightarrow$ $n \mid \frac{a^{n}-b^{n}}{a-b}$

How does one prove that if $n \mid (a^{n}-b^{n}) \ \Longrightarrow$ $\displaystyle n \mid \frac{a^{n}-b^{n}}{a-b}$ where $a,b, n \in \mathbb{N}$.

What i thought of is to consider $$(a-b)^{n} \equiv a^{n} + (-1)^{n}b^{n} \ (\text{mod} \ n)$$ and if we suppose that $n$ is odd then we have, $$(a-b)^{n} \equiv a^{n} -b^{n} \ (\text{mod} \ n)$$ and since $n \mid (a^{n} - b^{n})$ we have $$(a-b)^{n} \equiv 0 \ (\text{mod} \ n)$$

I think i am far away from the conclusion of the problem, but this is what i could work on regarding the problem.

-
The last line of your work is incorrect. (a-b)^{n} \equiv 0 (mod n) does not imply n \mid (a-b). Take a = 6, b = 4, n = 4 for a counterexample. – Brandon Carter Oct 8 '10 at 5:36
@Brandon: Thanks – anonymous Oct 8 '10 at 5:39

Use the fact that $x \equiv y \pmod{p^{\ell}}$ (with $\ell > 0$) implies $x^p \equiv y^p \pmod{p^{\ell+1}}$ to treat the case where $n$ is a prime power. But note that to prove the statement for $n$, it suffices to prove the statement separately for each prime power dividing $n$. [I am of course leaving out details, but perhaps the OP might enjoy trying to fill in the sketch.]

-

At the heart this is really trivial, a consequence of $\rm\ f(x) = x^n\, \Rightarrow\ f{\:'}(x)\ =\ n\, x^{n-1}\ \equiv\ 0\:\ (mod\ n).\,$ First I give the simple proof, then I explain the viewpoint in terms of derivatives.

$\rm\ \ n\:|\:(a-b)\frac{a^n-b^n}{a-b}\ \Rightarrow\,\ n = m\:k,\ \ m\:|\:a-b,\ \ k\:\big|\frac{a^n-b^n}{a-b}\$ by unique factorization. Thus it suffices

to show $\rm\ \ m\:|\:n,\:a-b\ \Rightarrow\ m\ \,\Big|\frac{a^n-b^n}{a-b}\: =\ a^{n-1}+a^{n-2}\:b+\:\cdots\:+a\:b^{n-2}+b^{n-1}$

But, $\rm\,\ mod\ \:m:\:\, \ a\equiv b\ \ \ \Rightarrow\, \ \ \frac{a^n-b^n}{a-b}\ \equiv\ a^{n-1}+\cdots+a^{n-1} \equiv\, n\, a^{n-1}\equiv\, 0\$ via $\rm\ m\:|\:n\quad\$ QED

The prior line is the special case $\rm\ f = x^n,\ x = b\$ of this polynomial Taylor series approximant:

$\rm\displaystyle\quad\quad\quad\quad\quad \frac{f(x)-f(a)}{x-a} \: \equiv\ f\:'(a)\ \ \ (mod\ \:x-a)\quad$ for $\rm\ f(x)\in \mathbb Z[x]$

$\qquad$ i.e. $\rm\quad\ f(x)\ =\ f(a) +\: f\:'(a)\ (x-a) \:+\: (x-a)^2\: g(x)\quad$ for some $\rm\ g(x) \in \mathbb Z[x]$

Therefore this result about numbers is just a special case of the following well-known result about functions (here polynomials):  a root $\rm\ x = a\$ of $\rm\ f(x)\$ has multiplicity $\rm > 1\ \iff\ f\:'(a) \:=\: 0.\:$ In fact, like above, many results about numbers are actually specializations of results about functions. Moreover, because functions have richer structure than numbers - e.g. having derivatives available - we can exploit this structure in the function realm before specializing to numbers. A powerful example of this is Mason's ABC theorem - which has a trivial high-school level proof for polynomials, but is an unproven conjecture for numbers. It yields, as a consequence, a trivial proof of FLT for polynomials. The moral is: to prove a result about numbers, try to interpret it as special case of a result about functions.

-