Prove $9^n \equiv 9 \pmod{24}\quad \forall n \in \Bbb N^*$ I accidentally found that $9^n\equiv 9\pmod{24} \quad \forall n \in \Bbb N^*$
But don't know how to prove it in an exact way.
Please help
 A: You can prove it using induction:
Initial case: It's trivial that $9\equiv 9 \text{ mod(24)}.$
Induction: We suppose $9^n\equiv 9 \text{ mod(24)}$ for some $n\in\mathbb{N}.$
Then, we'll see if it verifies for $9^{n+1}$:
$$9^{n+1}=9^n\cdot 9,$$
and using modular arithmetic properties we see that
$$(9^n\cdot 9) \text{ mod(24)}\equiv(9^n \text{ mod(24)}) \cdot(9\text{ mod(24)}),$$
so
$$(9^n\cdot 9) \text{ mod(24)}\equiv 9\cdot 9=81 \equiv 9 \text{ mod(24)}.$$
So we have proved that $9^{n+1}\equiv \text{ mod(24)}$, and by induction the statement is proved.
A: $24\mid 72\mid 9^{\large n}\!-9\,$ is easy: factor out $\,\color{#0a0}{c=9}\,$ via mod distributive law
$$\begin{align} 
ca\:\!\bmod cm \,&=\, \color{#0a0}c\,(a\bmod m)\\[.2em]
\Rightarrow\ \ 9^n-9\,\bmod\:\!\ 72 \,&=\,  \color{#0a0}9\,(\color{#c00}9^{n-1}\!-1\bmod 8)\\[.2em]
      &=\,  9(\,\color{#c00}1^{n-1}\!-1\bmod 8)\ \ {\rm by}\ \ \color{#c00}{9\equiv 1}\!\!\!\!\pmod{\!8}\\[.2em] 
      &=\,  9\,( 0)
\end{align}\quad\ $$
Remark $ $ Numbers like $\,9\,$ above with $\,a^2=a\,$ are called idempotents. This implies $\,a^{\large n} = a\,$ for all $\,n\ge 2\,$ either as above or by a simple induction $\,a^{\large n+1}\! = a\,a^{\large n} = a\cdot a = a.\,$ More conceptually: note $a$ is a fixed point of $\,f(x) = ax\,$ i.e. $\,f(a) = a,\,$ and fixed points always stay fixed on iteration by a simple induction: if $\,\color{#c00}{f^n(a) = a}\,$ then  $\,f^{\large n+1}(a) = f(\color{#c00}{f^{\large n}(a)}) = f(\color{#c00}a) = a$.
The $\!\bmod\!\!$ Distributive Law allows us to do this induction purely arithmetically, by cancelling out a factor to reduce it to the trivial induction $\,\color{#c00}1^n\equiv 1,\,$ exactly as in the special case above, i.e.
$$\begin{align} 
 a^n-a\,\bmod\, a(a\!-\!1) \,&=\,  \color{#0a0}a\,(\color{#c00}a^{n-1}\!-1\bmod a\!-\!1)\\[.2em]
      &=\,  a(\,\color{#c00}1^{n-1}\!-1\bmod a\!-\!1)\ \ {\rm by}\ \ \color{#c00}{a\equiv 1}\!\!\!\!\pmod{\!a\!-\!1}\\[.2em] 
      &=\,  a\,( 0)
\end{align}\!\!\!\!\!\!\!\! $$
therefore: $\ m\mid a(a\!-\!1)\mid a^{\large n}\!-a\ \Rightarrow\ a^n\equiv a\pmod{\!m}$
Or $\ \color{#c00}{a^{\large n}\equiv a}\pmod{\!(a\!-\!1)a},\,$ by it is true mod $\,a\!-\!1\!:$ $\,1^{\large n}\!\equiv 1\,$ & $\bmod a\!:\,0^{\large n}\!\equiv 0,\,$  thus it's also true $\!\bmod {\rm lcm}(a\!-\!1,a) = (a\!-\!1)a\,$ by CCRT, so the congruence persists $\!\bmod m\mid (a\!-\!1)a$.
Or $ $ by the Factor Theorem: $\, a\!-\!1\mid a^{\large n-1}\!-1\,\Rightarrow\, m\mid a(a\!-\!1)\mid a(a^{\large n-1}\!-1) = a^n-a$.
Idempotents $\!\bmod m\,$ play a fundament role in factorization of integers (and rings) since they correspond to splittings of $n$ into coprime factors, cf.  last paragraph here.
The $\!\bmod\!$ Distributive Law is essentially an operational form of CRT = Chinese Remainder Theorem. Unlike CRT it is formulated operationally which often makes it more convenient to apply in concrete calculations like those above.
A: $$\begin{array}{rcl}9^n-9&=&9(9^{n-1}-1)\\&=&9(9-1)(9^{n-2}+9^{n-3}+\ldots+9+1)\\&=&72(9^{n-2}+9^{n-3}+\ldots+9+1)\end{array}$$
so $9^n-9$ is divisible not only by $24$ but by $72$ as well.
