Zsigmondy's Theorem for Sums

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $a > b > 0$ be coprime positive integers.

Let $n \ge 1$ be a (strictly) positive integer.


Then there is a prime number $p$ such that

$p$ divides $a^n + b^n$
$p$ does not divide $a^k + b^k$ for all $k < n$

with the following exception:

$n = 3$, $a = 2$, $b = 1$


Outline of Proof

We apply Zsigmondy's Theorem to $a^{2n}-b^{2n}$.


Proof

By Zsigmondy's Theorem, there exists a prime divisor $p$ of $a^{2n}-b^{2n}$ which does not divide $a^k-b^k$ for all $k<2n$ unless:

$n=1$ and $a+b$ is a power of $2$
$n=3$, $a=2$, $b=1$

In particular, $p$ does not divide $a^{2k}-b^{2k}=(a^k-b^k)(a^k+b^k)$ for $k<n$.

It remains to check the case $n=1$ and $a+b$ a power of $2$.

Then $a$ and $b$ are odd.

We have to show that $a^2+b^2$ has an odd prime divisor.

By Square Modulo 4, $a^2+b^2\equiv2\pmod4$.

Because $a>b>0$, $a^2+b^2>2$.

Thus $a^2+b^2$ is not a power of $2$.

Thus $a^2+b^2$ has an odd prime divisor.

$\blacksquare$


Source of Name

This entry was named for Karl Zsigmondy.