6
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ The Chinese remainder theorem will help. $300=4\cdot 3\cdot 25$. $\endgroup$ – Arthur Feb 26 '15 at 14:06
  • 1
    $\begingroup$ See also: math.stackexchange.com/questions/81228/… $\endgroup$ – Martin Sleziak Feb 26 '15 at 15:20
  • $\begingroup$ @Arthur: I didn't see your comment until after I posted my answer, but that turns out to be a very nice way to go. $\endgroup$ – robjohn Feb 26 '15 at 16:41
6
$\begingroup$

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

$\endgroup$
5
$\begingroup$

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

$\endgroup$
5
$\begingroup$

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

$\endgroup$
1
$\begingroup$

${\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$

$\endgroup$
  • $\begingroup$ Beware $\ $ Modular fraction arithmetic is well-defined only for fractions with denominator coprime to the modulus. See here for further discussion. $\endgroup$ – Bill Dubuque Feb 26 '15 at 19:56
  • $\begingroup$ @Downvoter If something is not clear, please feel welcome ot ask questions. $\endgroup$ – Bill Dubuque Feb 26 '15 at 23:43
  • 1
    $\begingroup$ I didn't downvote, but I did tell you a few times people might find your posts very hard to follow when they have only three words in them. $\endgroup$ – Pedro Tamaroff Feb 26 '15 at 23:46
  • 1
    $\begingroup$ @Pedro What words do you think are missing? This is mathematics, not poetry! $\endgroup$ – Bill Dubuque Feb 26 '15 at 23:48
  • 1
    $\begingroup$ You sometimes insist on being pedagogic. This is not really pedagogic. You're condensing and skipping many steps in very few lines. Someone who's not already used to these kind of calculations is bound to struggle with this a while. $\endgroup$ – Pedro Tamaroff Feb 26 '15 at 23:55
1
$\begingroup$

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

$\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.