Theorems related to finding the last digit of large powers of integers [duplicate]

Note $n = c_0\! + c_1 1000 + \cdots\! + c_k 1000^k\! = f(1000)$ is a polynomial in $1000$ with integer coef's $\,c_i\,$ thus $\,{\rm mod}\ 7\!:\ \color{#c00}{1000}\equiv 10^3\equiv 3^3\equiv \color{#c00}{-1}\,\Rightarrow\, n = f(\color{#c00}{1000})\equiv f(\color{#c00}{-1}) \equiv c_0 - c_1 + \cdots + (-1)^k c_k$ follows by applying the Polynomial Congruence Rule below.

Similarly $\bmod 7\!:\ \color{#c00}{100\equiv 2}\Rightarrow n = f(\color{#c00}{100})\equiv f(\color{#c00}2)\,$ where $f$ is its radix $100$ polynomial as above.

[Note $ $ If congruences are unfamiliar then instead see the rules in divisibility form]

Below are the basic congruence rules. $ $ Let $\rm\ A,B,a,b\,$ be any integers.

Congruence Sum Rule $\rm\qquad\quad A\equiv a,\quad B\equiv b\ \Rightarrow\ \color{#90f}{A+B\,\equiv\, a+b}\ \ \ (mod\ m)$

Proof $\rm\ \ m\: |\: A\!-\!a,\ B\!-\!b\ \Rightarrow\ m\ |\ (A\!-\!a) + (B\!-\!b)\ =\ \color{#90f}{A+B - (a+b)} $

Congruence Product Rule $\rm\quad\ A\equiv a,\ \ and \ \ B\equiv b\ \Rightarrow\ \color{#0a0}{AB\equiv ab}\ \ \ (mod\ m)$

Proof $\rm\ \ m\: |\: A\!-\!a,\ B\!-\!b\ \Rightarrow\ m\ |\ (A\!-\!a)\ B + a\ (B\!-\!b)\ =\ \color{#0a0}{AB - ab} $

Congruence Power Rule $\rm\qquad \color{}{A\equiv a}\ \Rightarrow\ \color{#c00}{A^n\equiv a^n}\ \ (mod\ m)\ \ $ for all naturals $\rm\,n.$

Proof $\ $ For $\rm\,n=0\,$ it's $\,1\equiv 1\,$ so true. $\rm\,A\equiv a,\ A^n\equiv a^n \Rightarrow\, \color{#c00}{A^{n+1}\equiv a^{n+1}},\,$ by the Product Rule, so the result follows by induction on $\rm\,n.$

Congruence Inverse Rule $\rm \quad\ \color{#c00}{A\equiv a}\ \Rightarrow\ A^{-1}\equiv a^{-1},\ $ if $\rm\,A^{-1}\,$ exists.

Proof $\rm\,\ A^{-1} \equiv A^{-1} \color{#c00}a a^{-1}\equiv A^{-1} \color{#c00}A a^{-1} \equiv a^{-1}$ by PR = Product Rule $ $ (note $\rm\, a^{-1}$ exists by $\,\rm \color{#c00}aA^{-1}\equiv \color{#c00}AA^{-1}\equiv 1\,$ by PR). $ $ Alternatively: $ $ if $\rm\, A^{-1}\equiv b\,$ then PR $\rm\Rightarrow 1\equiv \color{#c00}Ab\equiv \color{#c00}ab\,$ so $\rm\, {a}^{-1} \equiv b\equiv A^{-1}\,$ by uniqueness of inverses.

Congruence Quotient Rule $ $ If $\rm\,(B,n)= 1\,$ then $\rm\!\bmod n\!:\, {\begin{align}\rm A\equiv a\\ \rm B\equiv b\end{align}\,\Rightarrow\, \dfrac{A}B\equiv \dfrac{a}b\:\! \overset{\rm def}\equiv\, ab^{-1}}$
Proof $\ $ See this answer, and see here for modular fractions.

Polynomial Congruence Rule $\ $ If $\rm\,f(x)\,$ is polynomial with integer coefficients then $\rm\ A\equiv a\ \Rightarrow\ f(A)\equiv f(a)\,\pmod m.\ $ Note: this is equivalent to the Factor Theorem.

Proof $\ $ By induction on $\rm\, n = $ degree $\rm f.\,$ Clear if $\rm\, n = 0.\,$ Else $\rm\,f(x) = f(0) + x\,g(x)\,$ for $\rm\,g(x)\,$ a polynomial with integer coefficients of degree $\rm < n.\,$ By induction $\rm g(A)\equiv g(a)$ so $\rm \color{#0a0}{A g(A)\equiv\! a g(a)}\,$ by the Product Rule. Hence $\rm \,f(A) = f(0)+\color{#0a0}{Ag(A)}\equiv f(0)+\color{#0a0}{ag(a)} = f(a)\,$ by the Sum Rule.

Beware $ $ that such rules need not hold true for other operations, e.g. the exponential analog of above $\rm A^B\equiv\, a^b$ is not generally true (unless $\rm B = b,\,$ so it follows by the Power Rule, or the Polynomial Rule with $\rm\,f(x) = x^{\rm b}),$ but there is a more limited rule that applies to integer powers - see modular order reduction.

Since $1001=143\cdot7$ it follows that $1000^k=(-1)^k$ modulo $7$ $(k\geq0)$. From this we can deduce that $$\sum_{k\geq0}^n a_k\>1000^k=\sum_{k\geq0}(-1)^k a_k\quad({\rm modulo}\ 7)\ .$$

$$ \quad{13\times7\times 11=1001\\A= \overline{...a_4a_3a_2a_1a_0}\\A=a_0+10a_1+100a_2+1000a_3+10000a_4+100000a_5+10^6a_6+...=\\(a_0+10a_1+100a_2)+(1000a_3+10000a_4+10^5a_5)+(10^6a_6+10^7a_7+10^8a_8)+...\\=(a_0+10a_1+100a_2)+1000(a_3+10a_4+100a_5)+1000^2(a_6+10a_7+100a_8)+...\\(\overline{a_2a_1a_0})+1000(\overline{a_5a_4a_3})+1000^2(\overline{a_8a_7a_6})+...\\(\overline{a_2a_1a_0})+(1001-1)(\overline{a_5a_4a_3})+(1001-1)^2(\overline{a_8a_7a_6})+...=\\(\overline{a_2a_1a_0})+(7k-1)(\overline{a_5a_4a_3})+(7q-1)^2(\overline{a_8a_7a_6})+...=\\(\overline{a_2a_1a_0})-1(\overline{a_5a_4a_3})+1(\overline{a_8a_7a_6})+...+\overbrace{7k+7q+...}^{7q'}\\ } $$so if A divided by 7 $$\quad{A = \space (\overline{a_2a_1a_0})-1(\overline{a_5a_4a_3})+1(\overline{a_8a_7a_6})+...+\overbrace{7k+7q+...}^{7q'}\\A-7Q=(\overline{a_2a_1a_0})-1(\overline{a_5a_4a_3})+1(\overline{a_8a_7a_6})+...}$$

Hint. $10^{6k}-1 \equiv 10^{6k - 3}+1 \equiv 0 \pmod{7}$.

This not an answer but an interesting other criterion for divisibility by 7

Consider $n\in\mathbb{N}$ and divide it by $10$ :

$$n=10q+r\qquad\mathrm{with}\,0\le r<10$$

Then we have :

$$7\mid n\Leftrightarrow 7\mid q-2r$$

The proof is very easy :

• Suppose $7\mid n$. We have $n=7k$ for some nonnegative integer $k$. Then $q-2r=q-2(n-10q)=21q-2n=7(3q-2k)$.

• Conversely, suppose $7\mid q-2r$. We have $q-2r=7K$ for some nonnegative integer $K$. Then $n=10(q-2r)+21r=7(10K+3r)$

This criteria has to be combined with iteration to show all its power ... Here is an example :

For $n=22925$, we compute $q=2292$, $r=5$ and $q-2r=2282$

For $n=2282$, we compute $q=228$, $r=2$ and $q-2r=224$

For $n=224$, we compute $q=22$, $r=4$ and $q-2r=14$

Since $7\mid14$ and by applying three times the above criteria, we conclude that $7\mid22925$.