Solve the following linear congruences by using Euler’s Theorem:
(a) $7x \equiv 33 \pmod {50}$
(b) $13x \equiv 51 \pmod {100}$
(c) $13x \equiv 52 \pmod {100}$
(a) Since $\gcd(50,7)=1$, we can use Euler's Theorem
$$ 7^{\phi(50)} \equiv 1 \pmod {50} $$
Using $\phi(50) = 20$ we have
$$ \begin{align} 7^{20} & \equiv 1 \pmod {50} \\ \\ 7^{20} \times 33 & \equiv 33 \pmod {50} \\ \\ 7 \times (7^{19} \times 33) & \equiv 33 \pmod {50} \end{align}$$
Noting that $7^2 \equiv 49 \equiv -1 \pmod {50}$ gives us $7^{19} \equiv (7^2)^9 \times 7 \equiv -7 \pmod {50}$.
And so
$$ \begin{align} 7 \times (7^{19} \times 33) & \equiv 33 \pmod {50} \\ \\ 7 \times (-7 \times 33) & \equiv 33 \pmod {50} \\ \\ 7 \times (-231) & \equiv 33 \pmod {50} \end{align}$$
Noting that $-231 \equiv 19 \pmod {50}$ gives us the solution
$$ x \equiv 19 \pmod {50} $$
(b) Since $\gcd(13,100)=1$, we can use Euler's Theorem
$$ 7^{\phi(100)} \equiv 1 \pmod {100} $$
Using $\phi(100) = 40$ we have
$$ \begin{align} 13^{40} & \equiv 1 \pmod {100} \\ \\ 13^{40} \times 51 & \equiv 51 \pmod {100} \\ \\ 13 \times (13^{39} \times 51) & \equiv 51 \pmod {100} \end{align}$$
Noting that $13^3 \equiv 2197 \equiv -3 \pmod {100}$ gives us $13^{39} \equiv (13^3)^{13} \equiv -1594323 \equiv 77 \pmod {100}$
And so
$$ \begin{align} 13 \times (77 \times 51) & \equiv 51 \pmod {100} \\ \\ 13 \times (3927) & \equiv 51 \pmod {100} \end{align}$$
Noting that $3927 \equiv 27 \pmod {100}$ gives us the solution
$$ x \equiv 27 \pmod {100}$$
(c) Since $\gcd(13,100)=1$, we can use Euler's Theorem
$$ 7^{\phi(100)} \equiv 1 \pmod {100} $$
Using $\phi(100) = 40$ we have
$$ \begin{align} 13^{40} & \equiv 1 \pmod {100} \\ \\ 13^{40} \times 52 & \equiv 52 \pmod {100} \\ \\ 13 \times (13^{39} \times 52) & \equiv 52 \pmod {100} \end{align}$$
Noting that $13^3 \equiv 2197 \equiv -3 \pmod {100}$ gives us $13^{39} \equiv (13^3)^{13} \equiv -1594323 \equiv 77 \pmod {100}$
And so
$$ \begin{align} 13 \times (77 \times 52) & \equiv 52 \pmod {100} \\ \\ 13 \times (4004) & \equiv 52 \pmod {100} \end{align}$$
Noting that $4004 \equiv 4 \pmod {100}$ gives us the solution
$$ x \equiv 4\pmod {100}$$