GCD of all $(n^{13}-n)$

We use the following classification without proof:

For all primes $p$ , the multiplicative group $( \mathbb{Z} / p \mathbb{Z} )^\times$ is the cyclic group of order $p-1$ .

Let $p$ be any prime. Suppose that $p^k \mid n(n^{12} - 1 )$ for all $n$ . Observe that for $n = p$ , we have $p^k \mid p(p^{12} - 1 )$ and thus $k \leq 1$ . Suppose that $k=1$ , then applying the above classification, there exists a non-zero primitive element $d$ such that the smallest solution to $d^{s} \equiv 1 \pmod{p}$ is $s = p-1$ . Since we have $d^{12} \equiv 1 \pmod{p}$ , let $12 = s q + r$ with $0 \leq r < s$ , then $1 \equiv d^{12} \equiv d^{sq +r} \equiv d^r \pmod{p}$ . Thus, $r = 0$ and so $s \mid 12$ . This implies that a necessary condition for $p^k \mid a$ is 1) $k = 1$ and 2) $p-1 \mid 12$ . Hence, $\displaystyle a\mid \prod_{p-1 \mid 12 } p$ .

Conversely, if $p$ is any prime such that $p - 1 \mid 12$ , then by Fermat's little theorem we know that $n^p \equiv n \pmod{p}$ for all $n$ . Hence, with $(p-1)q = 12$ , we get that $n^{(p-1)q +1 } \equiv n \pmod{p}$ for all $n$ . Thus, a sufficient condition for $p^k \mid a$ is 1) $k = 1$ and 2) $p-1 \mid 12$ . This tells us that $\displaystyle \prod_{p-1 \mid 12 } p \mid a$ .

Hence, we conclude that $\displaystyle a = \prod_{p-1 \mid 12 } p$ .

---

The above proof generalizes to showing that the largest positive integer $a$ such that for every positive integer $n$ , $a \mid n^t - n$ is given by $\displaystyle a = \prod_{p-1 \mid t-1 } p$ .

• Let's first see which prime $p$ divide $n^{13}-n$ for every $n$ . When for some $n$ , $p \mid n$ , then obviously $p$ divides $n^{13}-n$ . So, let's concentrate when $p \mid n^{13}-n$ for every $n$ with $p \not \mid n$ . That's where comes Fermat's Little Theorem .

• But $n^{13} \equiv n \pmod{p}$ for every $n$ with $p \not \mid a$ WHEN $13 \equiv 1 \pmod{(p-1)} \iff 12 \equiv 0 \pmod{(p-1)} \iff (p-1)\mid 12$ . The set of possible values of $(p-1)$ is $\{1,2,3,4,6,12\}$ , yielding the set of all such $p$ $\{2,3,5,7,13\}$ . Now we have, $2\times 3 \times 5 \times 7 \times 13= 2730$ . So, $2730 \mid n^{13}-n$ for every $n$ . So, is this the largest $a$ ?

• We see, $(p-1)\mid 12$ is a sufficient condition for $n^{13} \equiv n \pmod{p}$ for every $n$ with $p \not \mid a$ . But is it also a necessary condition? Yes, it's also a necessary condition. I refer to Primitive Roots wiki here. For every prime $p$ , there exists at least one number $n$ whose multiplicative order (or equivalently speaking, minimum exponent $e$ such that $n^e \equiv 1 \pmod{p}$ ) modulo $p$ is $\phi(p)=p-1$ . Thus, the condition $p-1 \mid 12$ is necessary such that $n^{13} \equiv n \pmod{p}$ works for EVERY $n$ with $p \not \mid a$ . Hence, $\{2,3,5,7,13\}$ is the complete set of such $p$ .

• Now we turn to numerical evidence. You can verify $\dfrac{2^{13}-2}{2730}=3$ and $\dfrac{3^{13}-3}{2730}=584$ . Since $gcd(3,584)=1$ , we can deduce that $\boxed{2730}$ is the largest $a$ . $\blacksquare$

---

Remark : If we did approach the problem with "Let's first see which prime power $p^e$ (with $e \geq 1$ ) divide $n^{13}-n$ for every $n$ " with the help of Euler's Theorem instead of "Let's first see which prime $p$ divide $n^{13}-n$ for every $n$ ", then we would not have to rely on Numerical Evidence.

By Euler's theorem, we have that each of the primes $2,3,5,7,13$ divides $12$ so for each prime $p$ stated before, we have $n^{13}-n\equiv 0 \pmod{p}$ . Furthermore, if $p$ is any prime, then $p^2$ does not divide $p^{13}-p$ in this case. Thus, the largest positive integer $a$ which divides all $n^{13}-n$ or, the GCD of all elements of form $n^{13}-n$ is $(2\cdot 3\cdot 5\cdot 7\cdot 13)=2730$