How to use Euler Fermat Theorem on this modular exponentiation?

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.

• Nothing wrong. But you don't get the solution that way. – Wuestenfux May 26 '17 at 14:08
• I thought this theorem can be used to reduce large powers modulo n according to wikipedia. What's the alternative? – Anil May 26 '17 at 14:12
• 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. – Wuestenfux May 26 '17 at 14:16
• 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$ – sharding4 May 26 '17 at 14:21

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

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$

• 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? – Anil May 26 '17 at 15:10
• 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. – sharding4 May 26 '17 at 15:16

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