How can calculate $ a \mod n^2 $ be computed smartly if we know $a \mod n$?

Question

By example:

How can $ 2^{65536} \mod 7^2 $ be computed smartly?

I think that there is a faster method than writing next element and find cycles. I found that
$\mod 7 :$ $$ \color{red}{ 2^{0} \equiv 1\\2^{1} \equiv 2\\2^{2} \equiv 4}\\2^{3} \equiv 1 $$ and by these equations each number can be fastly computed for example: $$2^{65536} = 2^{21845\cdot 3 +1 } \equiv 2^1 \equiv 2 $$ but how can it be applied for $\mod 49$?

Answer 1

$$ 2^3 = 1 + 7 \implies 2^{21} = (1+7)^7 \equiv 1 \bmod 7^2 \implies 2^{65536} \equiv 2^{65536 \bmod 21} = 2^{16} \equiv 23 \bmod 7^2. $$ The key point is the binomial expansion of $(1+7)^7$.

Answer 2

You can solve this the same way, only the cycle is a bit longer. Euler's theorem guarantees that the length of the cycle is a divisor of $\phi(49)=42$ (where $\phi$ is Euler's totient function). (Modulo $7$, Euler's theorem guarantees that the cycle length is a divisor of $6$, and you found that the cycle has length $3$.)

We get $$ 2^{65536}=(2^{42})^{1560}\cdot2^{16}\\ \equiv 1^{1560}\cdot2^{16}\\ =(2^8)^2\equiv 11^2\equiv 23 $$

Answer 3

Repeated squaring:

$$\color{blue}2^2=4$$

$$2^4=16$$

$$2^8=256\equiv11\mod 49$$

$$2^{16}\equiv11^2=121\equiv\color{red}{23}\mod49$$

$$2^{32}\equiv23^2=529\equiv39\mod49$$

$$2^{64}\equiv39^2\equiv(-10)^2=100\equiv\color{blue}2\mod49$$

If you do this another $6$ times, you'll get $$2^{4096}\equiv\color{blue}2\mod49$$

and then after another $4$ times you'll get $$2^{65536}\equiv\color{red}{23}\mod49.$$

Answer 4

Hint $\ $ Apply twice the congruence $\ 2^{\large 2^{\Large 6}}\!\!\equiv 2\pmod{\!7^{\large 2}}\,$ by below Lemma

because $\,\ \ \ \begin{align} 2^{\large\color{#c00} 3} &\equiv 1\!\!\!\pmod{\!7}\\ 2^{\large 6} &\equiv 1\!\!\!\pmod{\!\color{#c00}3\cdot 7} \end{align}$

Lemma $\ \ \begin{align} a^{\large\color{#c00} j} &\equiv 1\!\!\!\pmod{\!n}\\ k\,&\equiv 1\!\!\!\pmod{\!\color{#c00}j\:\!n} \end{align} \Rightarrow\ a^{\large k }\! \equiv a \pmod{\!n^2}$

Proof $\ \ a^{\large j} = 1+i\,n\ $ so $\bmod n^2\!:\,\ a^{\large jn} \equiv (1+i\,n)^{\large n}\equiv 1\ $ by Binomial Theorem

therefore $\ jn\mid k-1\,\Rightarrow\, a^{\large k-1}\equiv 1\,\Rightarrow\, a^{\large k}\!\equiv a$

Answer 5

Since, as you noticed, $2^3\equiv 1\pmod 7$, let's look at what multiplying by $2^3$ does to a number mod $7^2$. We'll write our congruence class in the form $7a+b$ where $0\leq a, b\lt 7$; then $2^3(7a+b)$ $=(7+1)(7a+b)$ $=7^2a+7a+7b+b$ $\equiv 7(a+b)+b$. By iterating this, we see that $2^{3i}(7a+b)$ $\equiv 7(a+ib)+b$, so $2^{21}(7a+b)$ $\equiv 7(a+7b)+b$ $\equiv 7a+7^2b+b$ $\equiv 7a+b$. In other words, $2^{21}$ here is the identity mod $7^2$ just as $2^3$ was mod $7$ (this is another way of looking at Arthur's answer), so we can remove all the factors of $2^{21}$ from $2^{65536}$ and wind up with $2^{65536}\equiv 2^{16}$ $\equiv 2\cdot2^{15}$ $\equiv 2\cdot (2^3)^5$ $\equiv 2\cdot (5\cdot 7+1)$ $\equiv 3\cdot7+2 \equiv 23$.