Number theory high school math competition question $\gcd(2^{71} - 2, 3^{71} - 3, ..., 100^{71} - 100)$
I got $2 \cdot 3  \cdot  11  \cdot  71$ so far.
I think that might be the answer, but not sure how I can be sure.
 A: The answer is, 
$$
\prod_{p-1\mid 70}p.
$$
I will prove it in a series of steps.


*

*First, check that, if $p-1\mid 70$, then if $a\equiv 0\pmod{p}$, we clearly have the divisibility. If $a\not\equiv 0\pmod{p}$, then it follows that $a^{p-1}\equiv 1\pmod{p}\implies a^{70}\equiv 1\pmod{p}$, hence, $a^{71}\equiv a\pmod{p}$. Hence, for every $p$ with $p-1\mid 70$, it holds that, $p\mid a^{71}-a$. Conversely, for any such prime divisor $p\mid {\rm gcd}(2^{71}-2,\dots,100^{71}-100)$ and $p<70$, it must hold that $p-1\mid 70$. To see this, let $g$ be a primitive root modulo $p$. Then, $g^{70}\equiv 1\pmod{p}$, and thus, $p-1\mid 70$.

*Next, we show if $p-1\mid 70$, then $p^2\nmid {\rm gcd}(2^{71}-2,\dots,100^{71}-100)$. To see this, simply take $a=p$, and observe that $p^{71}-p\not\equiv 0\pmod{p^2}$.

*Finally, take a prime $p>71$. Let $P(x)=x^{70}-1$. From the given condition, it holds that, this polynomial admits $1,2,3,\dots,70,71$ as its roots modulo $p$, which contradicts with Lagrange's theorem. Hence, no prime $p>71$ can possibly divide the gcd.


The end.
A: Hmm.  $k^{71} - k = k(k^{70} - 1)$
by fermat's little theorem:
If $p-1|70$ and $p\not \mid k$ then $k^{70}\equiv 1 \pmod p$ and so $p|k^{70} -1$ and $p|k^{71} -k$.  And if $p\mid k$ then $p|k^{71}-k$.
So $2,3,11, 71$ all divide all $k^{71} - k$ so $2\cdot 3\cdot 11 \cdot 71|\gcd$.
For any other prime $p$ then for any $p\not \mid k$ then then $k^{70\pmod {p-1} \not \equiv 0}\not \equiv 1 \pmod p$ so $p\not \mid k^{71} -k$ for any $k$ that isn't a multiple of $p$.  So as non-multiples of $p$ exist, $p$ can not be a factor of the $\gcd$.
So $\gcd = 2^a3^b11^c71^d$. But as $p\not \mid p^{70} -1$ then $p^2\not \mid p^{71} - p$ so no higher powers factor into the $\gcd$.
So $\gcd = 2\cdot 3\cdot 11 \cdot 71$ 
