Krdytkyu

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!

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

Note that $3^2=11-2$

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

using the binomial expansion, and simply $848=7times 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 0pmod{!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! 11equiv a^{large n}! + color{#c00}c!cdot! 11,, $ where $, color{#0a0}{ncdot a^{large n-1} b},equiv, color{#c00}c,pmod{!11}$

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

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

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

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

Note $,color{#b0f}{3^{large 12}!equiv 9},Rightarrow, 3^{large 10}!equiv 1pmod{!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].