Exercise 4.1.25* (If $n \mid a^n - b^n$, then $n \mid (a^n-b^n)/(a-b)$)

Question

For any positive integers $a, b, n$, prove that if $n$ is a divisor of $a^n - b^n$, then $n$ is a divisor of $(a^n - b^n)/(a-b)$.

\bigskip
Hint. Denote $a-b$ by $c$. For any prime $p$ dividing both $c$ and $n$, if $p^k$ is the highest power of $p$ dividing $n$, prove that $p^k$ divides every term in the expansion of ${\{(b+c)^n - b^n\}/c}$.

Richard Ganaye · Accepted Answer

ewcommand{\Z}{\mathbb{Z}}

ewcommand{\N}{\mathbb{N}}

\begin{proof} 
Suppose that $n$ is a divisor of $a^n - b^n$.
Put $c = a-b$, and let $p$ be a prime divisor of $n$. We define $k = 
u_p(n)$, so that $p^k 
mid n$, $p^{k+1} 
mid n$.  Then $p^k \mid a^n - b^n$.

If $p 
mid c = a-b$, then $p^k \wedge c = 1$, and $p^k \mid c [(a^n - b^n)/c]$, thus $p^k \mid (a^n - b^n)/c = (a^n - b^n)/(a-b)$.

Suppose now that $p \mid c$ and $p \mid n$. By definition of $k$, $p^k \mid n$. Moreover,
\begin{align*}
\frac{a^n - b^n}{a-b} &= \frac{(b+c)^n - b^n}{c}\
&= \frac{1}{c} \sum_{j=1}^n \binom{n}{j} b^{n-j} c^j\
&= \sum_{j=1}^n \binom{n}{j} b^{n-j} c^{j-1},
\end{align*}
so
\begin{align}
\frac{a^n - b^n}{a-b}&= \binom{n}{1} b^{n-1} + \binom{n}{2} b^{n-2}c + \cdots + \binom{n}{j} b^{n-j} c^{j-1} + \cdots + \binom{n}{n} c^{n-1}.
\end{align}
We want to prove that $p^k \mid \binom{n}{j} b^{n-j} c^{j-1}$. Since $p^{j-1} \mid c^{j-1}$, it is sufficient to prove that $p^{k-j+1} \mid \binom{n}{j}$, that is $
u_p \binom{n}{j} \geq k-j+1$.

If $j \geq k +1$, then $k - j + 1 < 0$, thus $
u_p \binom{n}{j} \geq k-j+1$. We can assume from now on that $1 \leq j \leq k$.

We prove by induction that for any integer $j$ such that $1 \leq j \leq k$, then $
u_p \binom{n}{j} =
u_p(n) - 
u_p(j)$. Put
$$\mathscr{P}(j) \iff 
u_p \binom{n}{j} =
u_p(n) - 
u_p(j).$$
\begin{itemize}
\item If $j = 1$, then $
u_p \binom{n}{1} = 
u_p(n) = 
u_p(n) - 
u_p(1)$, so $\mathscr{P}(1)$ is true.
\item Suppose that $\mathscr{P}(j)$ is true for some $j$ such that $1 \leq j < k$. A fortiori, $j<n$, because $j <2^j \leq p^j  < p^k \leq n$.

Since
$$\binom{n}{j+1} = \frac{n!}{(n-j-1)!(j+1)!}  = \frac{n-j}{j+1} \, \frac{n!}{(n-j)! j!}= \frac{n-j}{j+1} \binom{n}{j},$$
we obtain
\begin{align*}

u_p \binom{n}{j+1} &= 
u_p \binom{n}{j} + 
u_p(n-j) - 
u_p(j+1),\
\end{align*}
and by using the induction hypothesis $\mathscr{P}(j)$,
\begin{align}

u_p \binom{n}{j+1} &= 
u_p(n) - 
u_p(j) + 
u_p(n -j) - 
u_p(j+1).
\end{align}
Put $\alpha = 
u_p(j)$. Then $j = p^\alpha \lambda$, where $\lambda \wedge p = 1$, and $\alpha < 2^\alpha \leq p^\alpha \leq j$, so $\alpha < j < k$. Similarly $n = p^k \mu$, where $\mu \wedge p = 1$. Then
\begin{align*}
n-j &=p^k \mu - p^\alpha \lambda\
&= p^\alpha(\mu p^{k-\alpha} - \lambda),
\end{align*}
where $(\mu p^{k-\alpha} - \lambda) \wedge p = 1$, since $k - \alpha \geq 1$. Therefore $
u_p(n-j) = \alpha = 
u_p(j)$, thus equation (2) becomes
$$
u_p \binom{n}{j+1}  = 
u_p(n) - 
u_p(j+1),$$
so $\mathscr{P}(j+1)$ is true.

\item The induction is done, so 
 \begin{align}

u_p \binom{n}{j} =
u_p(n) - 
u_p(j), \qquad(1 \leq j \leq k).
\end{align}
Since $
u_p(j) < j$, then $
u_p(j) \leq j-1$, so for any $j \in [\![1, k ]\!]$, equation (3) shows that
$$
u_p \binom{n}{j} \geq k - j + 1.$$
We know that this is also true if $j>k$, so we have proved that 
\begin{align}
\forall k \in [\![1, n]\!],\ 
u_p \binom{n}{j} \geq k - j + 1.
\end{align}
\end{itemize}
Therefore
$$
u_p\left( \binom{n}{j} b^{n-j} c^{j-1} ight) \geq 
u_p \binom{n}{j} + 
u_p(c^{j-1})\geq k,$$
so $p^k$ is a divisor of every term in the sum (1), thus $p^k \mid (a^n - b^n)/(a-b)$, where $k =
u_p(n)$. Since this is true for every prime divisor $p$ of $n$,
$$n \mid \frac{a^n-b^n}{a-b}.$$
If $n$ is a divisor of $a^n - b^n$, then $n$ is a divisor of $(a^n - b^n)/(a-b)$.
\end{proof}

Exercise 4.1.25* (If $n \mid a^n - b^n$, then $n \mid (a^n-b^n)/(a-b)$)

Answers

Comments

Exercise 4.1.25* (If $n \mid a^n - b^n$, then $n \mid (a^n-b^n)/(a-b)$)

Answers

Comments

Add answer