0
$\begingroup$

I want to solve this modular exponentiation by using Euler Fermat Theorem

$94^{151} \equiv x \mod 299$

The Euler Fermat Theorem is

$a^x\equiv \ a^{k\cdot \phi(n)} \mod n$

We notice that $ gcd(94,299)=1 $ and $\phi (299) = 264 $

We these information we should be able to solve this doesn't work in my case.

$94^{151} = 94^{0\cdot 264+151}=94^{264^0}\cdot 94^{151}\equiv 1^{0}\cdot94^{151} \mod 299$

Can you tell me what is wrong in my procedure?

I know the solution already $x=3$ but I would like to know how to get there.

$\endgroup$
  • $\begingroup$ Nothing wrong. But you don't get the solution that way. $\endgroup$ – Wuestenfux May 26 '17 at 14:08
  • $\begingroup$ I thought this theorem can be used to reduce large powers modulo n according to wikipedia. What's the alternative? $\endgroup$ – Anil May 26 '17 at 14:12
  • $\begingroup$ Fermat says $x^p=x$ in $\mathbb{Z}_p$. But if you have an exponent smaller than $p$, you need to develop the exponent say in base 2 and make successive square and reduction steps. $\endgroup$ – Wuestenfux May 26 '17 at 14:16
  • 1
    $\begingroup$ May be easier to factor $299=13\cdot 23$ and consider the congruences $94^{151} \mod 13$ and $94^{151} \mod 23$. Put those answers together using the Chinese Remainder Theorem to find the answer $\mod 299$ $\endgroup$ – sharding4 May 26 '17 at 14:21
2
$\begingroup$

Since $299=13\times23$, you might start by computing $94^{151}\pmod{13}$ and $94^{151}\pmod{23}$.

It turns out that $94\equiv3\pmod{13}$, and so $94^{151}\equiv 3^{151}\pmod{13}$. Besides, since $13$ is prime and since $151\equiv7\pmod{12}$, $3^{151}\equiv3^7\pmod{13}$. It happens that $3^7\equiv3\pmod{13}$. By a similar approach, $94^{151}\equiv 3\pmod{23}$. Therefore, $94^{151}\equiv3\pmod{299}$.

$\endgroup$
2
$\begingroup$

Since $299=13\cdot 23$ look at the 2 congruences $$\begin{align} 94^{151} &\mod 13 \\ 94^{151} &\mod 23 \end{align}$$ Now for the first $94 \equiv 3 \mod 13$ and for the second $94 \equiv 2 \mod 23$, while $151 \equiv 7 \mod 12$ and $151 \equiv 19 \mod 22$. Using the Fermat's Little Theorem we're reduced to finding $$\begin{align} 3^{7} &\mod 13 \\ 2^{19} &\mod 23 \end{align}$$ For the first note that $3^3 \equiv 1 \mod 13$, so that $3^{7} \equiv 3 \mod 13$ For the second note that $2^{11} \equiv 1 \mod 23$, so that $2^{19} \equiv 2^8 \equiv 3 \mod 23$. Then by the Chinese Remainder Theorem the solution is $3 \mod 299$

$\endgroup$
  • $\begingroup$ You explained it very well. I understood everything except the third paragraph. How do I know that $3^3 \equiv 1\ mod 13$ why does this imply that $3^7 \equiv 3\ mod 13$. The same for $2^{11}\ldots $ Can you explaine me this as well. Just by trying out? $\endgroup$ – Anil May 26 '17 at 15:10
  • $\begingroup$ You find that $3^3 \equiv 1 mod 13$ simply by trial and error ($3^3 =27 = 2\cdot 13 +1$). You do know that $3^r \equiv 1 \mod 13$ for some $r$ dividing $12$, because $(\Bbb{Z}/13\Bbb{Z})^{\times}$ is an abelian group of order 12. Since $3^7 = (3^3)^2 \cdot 3\,\ 3^7 \equiv 3 \mod 13$ follows. The computation with $2$ is similar but a little harder. $\endgroup$ – sharding4 May 26 '17 at 15:16
1
$\begingroup$

Use the Chinese remainder theorem: as $299=13\cdot 23$, $$\mathbf Z/299\mathbf Z\simeq\mathbf Z/13\mathbf Z\times\mathbf Z/23\mathbf Z.$$ Observe $94\equiv 3\mod 13,\enspace\equiv 2\mod 23$. By Lil' Fermat, one has $$94^{151}\equiv3^{151\bmod12}=3^7\mod13, \qquad94^{151}\equiv2^{151\bmod22}=2^{-3}\mod13 $$

Computing the successive powers of $3$ mod. $13$, we see $3$ has order $3$, so $94^{151}\equiv 3^7\equiv 3\mod 13$.

On the other hand, $2^{-1}\equiv 12\mod 23$, so $2^{-2}\equiv 144\equiv 6\mod 23$, and finally $94^{151}\equiv 2^{-3}\equiv 72\equiv 3\mod 23$.

There remains to solve the system of congruences $\begin{cases}x\equiv3\mod13,\\x\equiv3\mod 23,\end{cases}$ which is obviously $3$.

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