# Solving linear congruences with Fermat's theorem and Euler's theorem

Use Fermat's Theorem to solve $18X \equiv 23 \pmod{37}$

Use Euler's Theorem to solve $7X \equiv 39 \pmod{54}$

I don't see how these theorems would work in these instances

## 2 Answers

You know that $$18^{37-1} \equiv 1 \mod (37)$$ So $$18^{37-1}\times 23 \equiv 23\mod(37)$$ So take $X = 18^{35}\times 23$

The other one is similar, except you need to first find $\phi(54)$

Well, $37$ is a prime number, so you can say that for any non-zero $a$ in $(\mathbb{Z}_{37},\times)$ we have: $a^{36}=1$ or written in congruence notations $a^{36} \equiv 1 \pmod{37}$ if $a \not\equiv 0 \pmod{37}$. That means $a^{35}.a \equiv 1\pmod{37}$, so $a^{35}$ is the inverse of $a$ (because inverses are unique for each element). Now you need to find $a^{35} \equiv x \pmod{37}$ such that $x$ is small enough to do multiplication (If you want to do it by hand). You'd better find $x \in \{\pm 1, \pm 2, \cdots, \pm 18\}$.

Euler's theorem generalizes this to the case where the modulus doesn't need to be prime. It states that if $(a,n)=1$ then $a^{\varphi(n)} \equiv 1 \pmod{n}$ where $\varphi(n)$ is Euler's totient function. It's obvious that in that case, the inverse of $a$ would be $a^{\varphi(n)-1}$. So, in other words, all you need to do is find $a^{\varphi(n)-1}$ to find the inverse of $a$ in $\mathbb{Z}_n=\mathbb{Z}/n\mathbb{Z}$.