Find the gcd of $n^{17}-n$ for $n$ an integer.
We already see that this $PGCD$ divides $2^{17}-2=2(2^{8}-1)(2^{8}+1)=2 \cdot 255 \cdot 257=2 \cdot 3 \cdot 5 \cdot 17 \cdot 257$ (prime factorization). But since for any integer $n$, by Fermat's little theorem:

- $n^{2} \equiv n[2]$ so $n^{17} \equiv n[2]$
- $n^{3} \equiv n[3]$ so $n^{17} \equiv n[3]$ because $2 \mid 17-1$
- $n^{5} \equiv n[5]$ so $n^{17} \equiv n[3]$ because $4 \mid 17-1$
- $n^{17} \equiv n[17]$

this $PGCD$ is already divisible by $2 \cdot 3 \cdot 5 \cdot 17=510$.

However, it is not divisible by 257 because $3^{16} \equiv (81 \cdot 9 \cdot 9)^{2} \equiv (-42 \cdot 9)^{2} \equiv -378 \neq 1[257]$.

Therefore, this $PGCD$ is 510.

## 2 Midway Training

## Statements