Find the following integer $ x $, s.t. $x \equiv 7^{57} \pmod {133}$ 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.
 A: 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$.
A: 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}
$$
A: 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.$$
A: 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$.
