Elementary Number Theory: Show that $3^{10}\equiv 1 \pmod{11^2}$.

Question

As the title says, I need to show $3^{10}\equiv 1 \pmod{11^2}$. I'm currently practicing some problems related to Fermat's little theorem and Wilson's theorem, and things were going fine but I am stumped on this problem. What I know so far is:

$3^{10}\equiv 1 \pmod{11}$, by Fermat's Little Theorem.

I'm not sure where to go from here, it almost looks like a lifting problem, but we have no variable so a function's derivative would always just be 0. I tried looking up how to lift constants potentially, but I couldn't really find anything (maybe I just didn't search well, so I apologize if this is the case) Any hints would be greatly appreciated. Thanks!

Answer 1

There is no lifting here. You are right about that. All what you need, as I can see, is to calculate this manually modulo $121$ instead of being misled by $11^2$. For the calculation, it turns out to be not so hard to follow it up.

As all powers of $3$ below $5$ are lower than $121$, notice that $3^5$ is $1$ more $242$ which is nothing but $2*121$. What this essentially tells you?

Now, as we noticed that:

$$3^5 \equiv 1 \pmod {121}$$

What can this tell us about $3^{10}$??

Answer 2

Note that $3^2=11-2$

Then $$3^{10}=(11-2)^5= 11^5- \dots +\binom 51\times 11\times 2^4-2^5\equiv 880-32 \bmod 121$$

using the binomial expansion, and simply $848=7\times 121 +1$

Other solutions are slicker in this case, but the arithmetic here is pretty simple, and when you are looking at the square of a prime as the modulus most of the terms in the binomial expansion will simply drop out.

Answer 3

Below are $\,4\,$ simple ways to compute it using about $10$ seconds of mental arithmetic, by using the Binomial Theorem, which reduces to the first $\,2\,$ terms by $\,11^{\large 2+k}\!\equiv 0\pmod{\!11^{\large 2}},\:$ i.e.

$\!\!\bmod 11^{\large 2}\!\!:\ (a\! +\! 11b)^{\large n}\! \equiv a^{\large n}\! + \color{#0a0}{n\!\cdot\! a^{\large n-1} b}\!\cdot\! 11\equiv a^{\large n}\! + \color{#c00}c\!\cdot\! 11,\,\ $ where $\,\ \color{#0a0}{n\cdot a^{\large n-1} b}\,\equiv\, \color{#c00}c\,\pmod{\!11}$

$\left[3^{\large 2}\!\!=\! -2\!+\!11\right]^{\large 5}\!\!\Rightarrow \overbrace{3^{\large 10}\!\!\equiv -2^{\large 5}+ \color{#0a0}{5\!\cdot 2^{\large 4}}\!\cdot\!11\equiv\! -32\!+\!\color{#c00}3\!\cdot\!11\equiv 1 \phantom{I^{I^{I^{I^{I^I}}}}}\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!}^{\Large \bmod 11^{\Large 2}\ \ \ \ \,}\ \ \, $ by $\,\ \overbrace{\color{#0a0}{5\cdot 2^{\large 4}}\equiv 5\cdot 5\equiv \color{#c00}3\phantom{I^{I^{I^{I^{I^I}}}}}\!\!\!\!\!\!\!\!\!\!\!\!\!}^{\Large \bmod{11}\ \ \ \ \ }\ \ $ [Mark]

$\left[3^{\large 3}\! =\ 5\!+\!22\right]^{\large 4}\!\!\Rightarrow \color{#b0f}{3^{\large 12}} \equiv 5^{\large 4}\! + \color{#0a0}{4\!\cdot\!5^{\large 3}\!\cdot\!2}\!\cdot\! 11\equiv 5\!\cdot\!4\color{#c00}{-1}\!\cdot\!11\equiv\color{#b0f} 9\,\ $ by $\,\ 5^{\large 3}\!\equiv 4,\ \color{#0a0}{4(4)2}\equiv\color{#c00}{-1}$

$\left[3^{\large 4}\! =\, 4\!+\!77\right]^{\large 3}\!\Rightarrow \color{#b0f}{3^{\large 12}}\! \equiv 4^{\large 3}\!+\color{#0a0}{3\!\cdot\!4^{\large 2}\!\cdot\!7}\!\cdot\! 11\equiv\ 64\,\color{#c00}{-5}\!\cdot\!11\equiv\color{#b0f} 9\ \,$ by $\,\ \color{#0a0}{(3\!\cdot\! 7)4^{\large 2}}\equiv \color{#c00}{(-1)5}$

$\left[3^{\large 5}\!=1\!+\!242\right]^{\large 2}\!\!\!\Rightarrow 3^{\large 10}\!\equiv 1^{\large 2}\!\!+\! \color{#0a0}{2\!\cdot\! 1\!\cdot\! 22}\cdot 11\equiv \ \ 1+ \color{#c00}0\cdot 11\equiv 1\ \,$ by $\ \ \color{#0a0}{2\cdot 22}\equiv \color{#c00}{0}\quad $ [Will, Maged]

Note $\,\color{#b0f}{3^{\large 12}\!\equiv 9}\,\Rightarrow\, 3^{\large 10}\!\equiv 1\pmod{\!11^{\large 2}}\,$ by $\,3\,$ is invertible (so cancellable), by $\,\gcd(3,11^2)=1$

The other $2$ answers posted are essentially equivalent to one of the above cases, as $ $ [Annotated].