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

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!

• $3^5 = 243 = 242 + 1$ Nov 24 '18 at 20:07
• @Will Lucky power choice, but it's still very quick even without luck if we exploit the Binomial Theorem, as I explain in my answer. Nov 25 '18 at 1:32

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}$$??

• Tells us that $(3^5)^2 \equiv 1$ mod $121$. Thank you for the answer :) Guess I over-looked this one. Nov 24 '18 at 20:41
• You are more than welcome :) Nov 24 '18 at 20:43

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.

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].