Using modular arithmetic to help calculate Greatest Common Divisors

In a recent FPM class we discussed how to determine \(\mathrm{GCD}(21,2^{70}+5)\).
[See also my earlier post on Greatest Common Divisors]
The answer here was that \(21 \mathrel{|} 2^{70}+5\) and so

\(\mathrm{GCD}(21,2^{70}+5) = 21\,.\)

We discussed various ways to prove this. Some students had shown separately that \(3 \mathrel{|} 2^{70}+5\) and \(7 \mathrel{|} 2^{70}+5\), from which it follows, e.g. by prime factorization (Fundamental Theorem of Arithmetic, FTA), or by more elementary means, that \(21 \mathrel{|} 2^{70}+5\) too.

In the Engagement Session we showed, instead, that \(2^{70} \equiv 2^4 = 16\)  \((\mathrm{mod}~ 21)\), which gives us

\(2^{70}+5 \equiv 16+5 = 21 \equiv 0\)  \((\mathrm{mod}~ 21)\)

and so \(21 \mathrel{|} 2^{70}+5\).
We discovered that \(2^{70} \equiv 2^4\)  \((\mathrm{mod}~ 21)\) by looking at powers of \(2\) mod \(21\), and spotting that we had a repeating pattern with period \(6\) , so that

\(2^{70}=2^{4+66} \equiv 2^4\) \((\mathrm{mod}~ 21)\)

We then made this slightly more formal by noting that \(2^6=64 = 3 \times 21+1\), so that

\(2^6 \equiv 1\) \((\mathrm{mod}~ 21)\),

which explains the repeating pattern. If you want to use the other approach (divisibility by \(3\) and by \(7)\), I would note that

\(2^2=4 \equiv 1\) \((\mathrm{mod}~ 3)\),

and

\(2^3=8 \equiv 1\) \((\mathrm{mod}~ 7)\).

Then \(2^{70} = (2^2)^{35} \equiv 1^{35}=1\) \((\mathrm{mod}~ 3)\), which gives us

\(2^{70}+5 \equiv 1+5 = 6 \equiv 0\) \((\mathrm{mod}~ 3)\),

and so \(3 \mathrel{|} 2^{70}+5\) .
[An alternative is to use \(2 \equiv -1\) \((\mathrm{mod}~ 3)\), so that \(2^{70} \equiv (-1)^{70}=1\) \((\mathrm{mod}~ 3)\), etc.] Similarly \(2^{69} =(2^3)^{23} \equiv 1^{23}=1\) \((\mathrm{mod}~ 7)\), which gives us

\(2^{70}+5 = 2 \times 2^{69} + 5 \equiv 2 \times 1 + 5 = 7 \equiv 0\) \((\mathrm{mod}~ 7)\)

and so \(7 \mathrel{|} 2^{70}+5\) .