Zsigmondy’s Theorem and its Applications

Theorem 

Zsigmondy’s Theorem states that if $a > b ≥ 1$ are coprime integers and $n ≥ 2$, then there exists a prime divisor of $a^ n − b^ n$ that does not divide $a^ k − b^ k$ for all $1 ≤ k < n$, except in the following cases: 

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

• $(a, b, n) = (2, 1, 6)$. 

Example

Consider $(a, b, n) = (4, 2, 3)$. Then 

$4^ 3 − 2 ^3 = 56$, 

$4 ^2 − 2^ 2 = 12$, 

$4^ 1 − 2^ 1 = 2$. 

So one such nice prime would be $7$.

Read more »