3
$\begingroup$

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!

$\endgroup$
  • 6
    $\begingroup$ $3^5 = 243 = 242 + 1$ $\endgroup$ – Will Jagy Nov 24 '18 at 20:07
  • $\begingroup$ @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. $\endgroup$ – Bill Dubuque Nov 25 '18 at 1:32
2
$\begingroup$

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

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

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.