3
$\begingroup$

Find the following integers $x$:

$x \equiv 7^{57} \mod 133$

I need to use fermat's little theorem for this problem which I know. It is for a prime number p. Then $a^{p-1} \equiv 1 \pmod p$ but I do not see how this is related to the above.

If anyone can guide me through this problem that would be helpful.

$\endgroup$
2
$\begingroup$

Note that $133=7 \cdot 19$. Thus \begin{align*} x & \equiv 7^{57} \pmod{133} && \iff && x \equiv 7^{57} \pmod{7}\\ & && && x \equiv 7^{57} \pmod{19} \end{align*} The latter system can be rewritten as \begin{align*} x & \equiv 0 \pmod{7}\\ x & \equiv 7^{57} \equiv 7^{18(3)} \cdot 7^3 \equiv 7^3 \equiv 1\pmod{19} \end{align*} In the second congruence I have used Fermat's little theorem. Now you can use Chinese Remainder theorem or a simple inspection to get $x=77$.

$\endgroup$
1
$\begingroup$

We have $7^4\equiv{7}\pmod{133}$ hence $$ 7^{57}\equiv (7^{4})^{14}7\equiv(7^{14})7\equiv(7^{4})^37^3\equiv7^6\equiv7^3\equiv343\pmod{133} $$

$\endgroup$
0
$\begingroup$

Note that $133 = 7 \cdot 19$. Let us find $a= 7^{57} \mod 19$ and $b= 7^{57} \mod 7 = 0$.

By Fermat's little theorem, you have $a^p = a \mod p$. Then $a= 7^{19} = 7 \mod 19$, therefore $7^{57} = 7^3 \mod 19 = 1 \mod 19$.

So, you want a number $x$ such that $x = 1 \mod 19$ and $x=0 \mod 7$. Using the Chinese Remainder Theorem you get that $x=77$ (this being the smallest such solution, because there are infinitely many of them, all of the form $77 + n \cdot 133$ with $n \in \mathbb Z$.

$\endgroup$
0
$\begingroup$

Since $133=7\times 19$, we'll use the Chinese Remainder Theorem.

Modulo $7$, for lall $n$, $7^n\equiv 0\mod7$.

Modulo $19$ apply Little Fermat: $7^{19}=7$, hence $7^{57}\equiv7^3\equiv 1\mod 19$.

Now, a Bézout's relation between $7$ and $19$ is $3\cdot 19-8\cdot 7=1$, hence: $$x\equiv 3\cdot 19\cdot \color{red}0 -8\cdot 7\cdot\color{red}1=-56\equiv 77\mod 133.$$

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