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?
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this communityUsing 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?
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$$
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}$.
The Chinese Remainder Theorem is your friend:
[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."
${\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$
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} $$