How to solve modulo equations I was hoping someone would help me on how to solve the following modulo equations (they are from an exercise book in my course which unfortunately is without conclusion):
(1) $x^{2018}=1 \pmod {21}$
(2) $5x^{2107}=75 \pmod {205}$
For (1) I have started writing $(x^{2})^{1009}=1 \pmod {21}$ but then I did not know how to proceed since I still have x raised in a high number (prime number so can not be simplified more).
And for (2) I simplified to $x^{2107}=15 \pmod {205}$ but have the same problem here as above. Unfortunately I didn't find any similar equations online so I hope someone here would like to help me on how to solve these equations.
 A: Use the totient function $\phi (n).$ For $n\in \Bbb N,$ the value of $\phi(n)$ is the number of members of $$G(n)=\{j\in \Bbb N: j\le n\land gcd(j,n)=1\}.$$ If $m,n\in\Bbb N$ and $gcd(m,n)=1$ then $\phi(mn)=\phi(m)\phi(n).$ If $p$ is prime and $n\in \Bbb N$ then $\phi(p^n)=p^{n-1}(p-1).$
Multiplication mod $n$ on the set $G(n)$ is a $group$ with $\phi(n)$ members, so for every $j\in G(n)$ we have $j^{\phi(n)}\equiv 1\mod n.$ (LaGrange's Theorem on finite groups.)
If $0\ne x\in\Bbb Z$ and if $gcd(x,n)=1$ then $x\equiv j \mod n$ for some $j\in G(n)$ so $x^{\phi(n)}\equiv j^{\phi(n)}\equiv 1 \mod n.$
$(1)$. We have $\phi(21)=\phi(3)\phi(7)=2\cdot 6=12.$ If $x^{2018}\equiv 1\pmod {21}$ then $x\ne 0$ and $gcd(x,21)=1$ so $x^{12}\equiv 1 \pmod {21}.$ Hence $$1\equiv x^{2018}\equiv (x^{12})^{168}\cdot x^2\equiv x^2\pmod {21}.$$ So $(3)(7)|(x^2-1)=(x-1)(x+1).$ So $x\equiv \pm 1\pmod 3$ and $x\equiv\pm 1\pmod 7.$ So  $x\equiv y \pmod {21}$ for some (any) $y\in \{1,8,13,20\}.$
$(2)$. We have $5x^{2107}\equiv 75 \pmod {205}\iff$ $ (5)(41)=205|(5x^{2107}-75)\iff$ $ 41|(x^{2107}-15).$ We have $\phi(41)=40$ and we have $2107=(40)(52)+27.$ So $$5x^{2107}\equiv 75 \pmod {205} \implies x^{2107}\equiv 15 \pmod {41}\implies$$ $$\implies x^{27}\equiv 15 \pmod {41}\implies$$ $$\implies x\equiv (x^{40})^2\cdot x\equiv (x^{  27})^3\equiv 15^3\equiv 13\pmod {41}.$$ Note we chose to "cube it" because $(27)(3)$ is $1$ more than a multiple of $\phi(41).$
Footnote: In Number Theory, a function $f$ with domain $\Bbb N$ is called "multiplicative" if $f(m)f(n)=f(mn)$ whenever $gcd(m,n)=1.$ It does NOT mean that $f(m)f(n)$ must be $f(mn)$ for $all$ $m,n.$
