Find the following integer $ x $, s.t. $x \equiv 7^{57} \pmod {133}$

Question

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.

Answer 1

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

Answer 2

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

Answer 3

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

Answer 4

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