1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.