Calculate $121^{199} \mod 300$

Question

Using Fermat's little theorem I proved that

$$121^{199} = 121^{39} \mod 300$$

(as $\phi(300)$ is $80$) but I don't think I can leave it like this. My question being how can I solve $121^{39}\hspace{-3mm}\mod 300$. Any ideas, suggestions?

Answer 1

Probably not better than Jyrki's method, but I'm stating it anyway. First of all, you've overlooked that you're dealing with a square number. So

$$121^{39}\equiv11^{78}\equiv11^{-2}\pmod{300}$$

$11$ has a rather easy divisibility test, so it's not that hard to find a multiple of $11\equiv1\pmod{300}$. A $3$-digit number won't work as the sum of the first digit and $1$ cannot possibly be a multiple of $11$. Among $4$-digit numbers starting with $1$, the only multiple of $11$ is $1001$ which doesn't work. For a first digit of $2$, on the other hand, we have $2101$ ($2-1+0-1=0$).

$$\frac{2101}{11}=191\equiv-109\pmod{300}$$

Now that we have the inverse of $11$, we just have to square it.

$$(-109)^2=10000+1800+81=11881=11700+181$$

Answer 2

On second thought, maybe a combination of the 2 previous methods is best. Again

$$121^{39}\equiv11^{78}\equiv11^{-2}\equiv121^{-1}\pmod{300}$$

And now use the Chinese remainder theorem to find the inverse of $121$. We have

$$121\equiv-4\pmod{25}\text{ and }121\equiv1\pmod{12}$$

So our inverse is equivalent to $6\pmod{25}$ and $1\pmod{12}$.

Answer 3

The Chinese Remainder Theorem is your friend:

• Calculate the result modulo $100$ (the order of $121$ modulo $100$ is a single-digit integer)
• Calculate the result modulo $3$.
• This is enough to know the answer modulo $3\cdot100$ as $\gcd(3,100)=1.$

---

[Edit 2702] Others have given solutions based on Euler's totient function. While that is often an indispensable tool in attacking problems like this, I believe in stretching the limitations of elementary tools. In spite of such solutions being a bit ad hoc. Concepts originating from elementary group theory are very useful to have, and form a way of distilling what we have learned over the centuries. But for the developing mathematical mind an adventure in experimenting has its merits. I recall having worked out remainders like this in school without any deeper concepts - some of those one only learns to appreciate later. What follows is a result of such experimentation. Of course, mixed with the hindsight of having learned about CRT and such.

Modulo $100$ we have $121\equiv21$. The key shortcut here comes from the trivial observation that $10^2=100\equiv0$. Therefore all but the constant and the linear terms vanish modulo $100$ whenwe apply the binomial theorem $$ \begin{aligned} 21^n&=(1+20)^n=1+\binom{n}1 20+\binom{n}2 20^2+\cdots\\ &\equiv 1+20\cdot n\pmod{100}. \end{aligned} $$ Therefore $$21^{199}\equiv1+199\cdot20\equiv81\pmod {100}.$$ Modulo $3$ things are trivial. $121\equiv1\pmod3$, so $121^{199}\equiv1\pmod3$ also.

The above modulo $100$ calculation tells us that the remainder modulo $300$ is either $81$, $181$ or $281$. Of these only $181$ is congruent to $1$ modulo $3$, so that is the answer.

Polonius: "Though this be madness, there's method in't."

Answer 4

${\rm mod}\ 25\!:\ \overbrace{11^{20}\equiv 1}^{\large\rm Euler\ \varphi}\,\Rightarrow\, x = 11^{398}\equiv \dfrac{1}{11^2}\equiv \dfrac{-24}{-4}\equiv \color{}6\iff x = \color{#0a0}{6\!+\!25n}$

${\rm mod}\ 12\!:\ 11^{398}\equiv (-1)^{398}\equiv \underbrace{1\equiv \color{#0a0}{6\!+\!25n}\equiv 6\!+\!n}_{\Large n\ \equiv\ -5\ \equiv\ \color{#c00}7}\ \Rightarrow\ x = 6\!+\!25(\underbrace{\color{#c00}7\!+\!12k}_{\Large n}) = 181+300k$

Answer 5

There are several approaches to this computation.

---

Intelligent Brute Force

Write $199=11000111_{\text{two}}$ then work mod $300$ with binary exponents: $$ \begin{align} 1&\equiv121^0\\ 121&\equiv121^1&&\text{multiply by }121\\ 241&\equiv121^{10}&&\text{square}\\ 61&\equiv121^{11}&&\text{multiply by }121\\ 121&\equiv121^{110}&&\text{square}\\ 241&\equiv121^{1100}&&\text{square}\\ 181&\equiv121^{11000}&&\text{square}\\ 61&\equiv121^{110000}&&\text{square}\\ 181&\equiv121^{110001}&&\text{multiply by }121\\ 61&\equiv121^{1100010}&&\text{square}\\ 181&\equiv121^{1100011}&&\text{multiply by }121\\ 61&\equiv121^{11000110}&&\text{square}\\ 181&\equiv121^{11000111}&&\text{multiply by }121\\ \end{align} $$ Therefore, $$ 121^{199}\equiv181\pmod{300} $$ As noted by Bill Dubuque in comments, this is known as exponentiation by squaring.

---

Chinese Remainder Theorem and Fermat's Little Theorem

Note that $300=3\cdot4\cdot25$. Furthermore, $121\equiv1\pmod3$ and $121\equiv1\pmod4$, therefore, $$ 121^{199}\equiv1\pmod{12}\tag{1} $$ Now we just need to work mod $25$.

$121\equiv-4\pmod{25}$ and $199\equiv-1\pmod{20}$ where $20=\phi(25)$. Therefore, $$ \begin{align} 121^{199} &\equiv(-4)^{-1}\\ &\equiv6\qquad\pmod{25}\tag{2} \end{align} $$ We could have used the Extended Euclidean Algorithm to get $(-4)^{-1}\equiv6\pmod{25}$, but it just seemed so self-evident.

We need to find an $x$ that satisfies $$ \begin{align} x&\equiv1\pmod{12}\\ x&\equiv6\pmod{25} \end{align}\tag{3} $$ We can solve $(3)$ by solving $$ \begin{align} x&\equiv1\pmod{12}\\ x&\equiv0\pmod{25} \end{align}\tag{4} $$ and $$ \begin{align} x&\equiv0\pmod{12}\\ x&\equiv1\pmod{25} \end{align}\tag{5} $$ and adding $1\times$ the solution to $(4)$ to $6\times$ the solution to $(5)$.

Again, we could use the Extended Euclidean Algorithm to solve $(4)$ and $(5)$, but each has a seemingly self-evident solution. $(4)$ has a solution of $x=25$, and $(5)$ has a solution of $x=-24$.

Thus, as claimed above, we get a solution for $(3)$ with $$ x=1\times25+6\times(-24)=-119\equiv181\pmod{300}\tag{6} $$