Computing $\gcd\{n^k - n^\ell : n \in \mathbb Z\}$

Question

Computationally, it is possible verify that $n^8 - n^2$ is divisible by $252\ (= 2^2\cdot3^2\cdot7)$ for every $n \in \mathbb Z$. One crude way of doing so is by looking at the sequence $$ (\underbrace{0^8-0^2}_0, \underbrace{1^8-1^2}_0, \underbrace{2^8-2^2}_{252}, \dots, 251^8-251^2) $$ and checking that $252$ divides each term in the sequence (it does).

However, is there a simpler way to tell that $n^8-n^2$ is divisible by $252$?

Moreover, given some polynomial $p(n) = n^k - n^\ell$ (or better yet, given an arbitrary polynomial $p$ with coefficients in $\{1,0,-1\}$), is there a way to immediately see the largest $N$ such that $N$ divides $p(n)$ for all $n \in \mathbb Z$?

Answer 1

Let $r$ be a positive integer, and let $S_r$ be the set of positive integers $d$ such that the Euler's function $\phi(d)$ divides $r$. Let $M$ be the least common multiple of the numbers in $S_r$. If $a$ is the exponent of the highest power of a prime in the factorization of $M$ then, by Euler's theorem, $$\text{$n^{a+r}-n^a=n^a(n^r-1)$ is divisible by $M$.}$$

In your case: $r=6$, $S_r=\{2,3,4,6,7,9,14,18\}$, $M=252=2^2\cdot 3^2\cdot 7$ and $a=2$ which the statement above implies that $$\text{$n^{8}-n^2$ is divisible by $252$.}$$

Another example: if $r=12$ then $M=32760$, $a=3$ and $$\text{$n^{15}-n^3$ is divisible by $32760$.}$$

Answer 2

The Euler-Fermat generalization below $\Rightarrow 2^2\cdot 3^2\cdot 7 = 252\mid a^2(a^6-1)\,$ with $\,e,f = 2,6.$

Theorem $\ \ $ Suppose that $\ m\in \mathbb N\ $ has the prime factorization $\:m = p_1^{e_{1}}\cdots\:p_k^{e_k},\, $ and suppose that for all $\,i\!:\,$ $\, e_i\le e\ $ and $\ \phi(p_i^{e_{i}})\mid f.\ $ Then $\ m\mid a^e(a^f-1)\ $ for all $\: a\in \mathbb Z.$

Proof $\ $ Notice that if $\ p_i\mid a\ $ then $\:p_i^{e_{i}}\mid a^e\ $ by $\ e_i \le e.\: $ Else $\:a\:$ is coprime to $\: p_i\:$ so by Euler's phi theorem, $\!\bmod q = p_i^{e_{i}}:\, \ a^{\phi(q)}\equiv 1 \Rightarrow\ a^f\equiv 1\, $ by $\: \phi(q)\mid f\, $ and modular Order Reduction. Hence, since all $\ p_i^{e_{i}}\ |\ a^e (a^f - 1)\ $ so too does their lcm = product = $m$.

Examples $\ $ You can find many illuminating examples in prior questions, e.g. below

$\qquad\qquad\quad$ $24\mid a^3(a^2-1)$

$\qquad\qquad\quad$ $40\mid a^3(a^4-1)$

$\qquad\qquad\quad$ $88\mid a^5(a^{20}\!-1)$

$\qquad\qquad\quad$ $6p\mid a\,b^p - b\,a^p$