# How can I solve $36x \equiv 81 \pmod{21}$ with Fermat's little theorem?

$$36x \equiv 81 \pmod{21}$$

This is what I got, I made it in another way, but I have to do this with Fermat's little theorem.

\begin{align}36x &\equiv 81 \pmod{21}\\ 12x &\equiv 27 \pmod 7\\ \gcd(12,7)&=1\end{align}

$$\varphi(7)=6$$

$$x ≡ 27 * 12 ^{\varphi(7)-1}\equiv 6\cdot(-2)^5 \equiv -(-2)^5 = 25 = 32 ≡ 4 \pmod 7$$

$$x \in \{4, 11, 18\}$$

And this is where I got stuck with Fermat's little theorem:

\begin{align}36x &\equiv 81 \pmod{21}\\ 6^2 &\equiv 9^2 \pmod{21}\end{align}

Now what should I do? I was looking for examples, but unfortunately I didn’t understand.

• You prove that all solutions of the equation are among $x\in\{4,11,18\}$, and you can easily verifiy that all these indeed satisfy the equation. What is bothering you? May 4, 2021 at 7:57
• Notice I edited your question to improve the formatting. It is strongly advised that you use Mathjax to format your questions on this site - it's like LaTeX for the web. I edited your question this time since you are new, but in future, please format the question yourself. See here for a quick guide: math.meta.stackexchange.com/questions/5020/…
– 5xum
May 4, 2021 at 7:59
• Unfortunately, I have to solve and derive with Fermat's little theorem and not with the way I did it May 4, 2021 at 8:04
• Thanks for the formatting! May 4, 2021 at 8:04
• You can't directly apply Fermat (or Euler) to invert $36$ since it is not coprime to the modulus $21$. Cancelling $\,3 = \gcd(36,21)\,$ is the correct way to proceed. See here for the general method. May 4, 2021 at 9:17

By CRT, we are reduced to computing modulo $$3,7$$.

Modulo $$7$$, you can divide out $$9$$ to start, getting $$4x\equiv9\pmod 7$$, since $$(7,9)=1$$.

We have $$36x\equiv81\pmod3\iff 0\equiv0$$. That is, every $$x$$ is a solution.

$$\varphi (7)=6$$. We apply Fermat's little theorem.

Get that $$4^{-1}\equiv4^5\equiv (-3)^5\equiv-5\equiv2\pmod7$$.

So we get $$x\equiv18\equiv4\pmod7$$.

There's not a way to solve the problem solely with Fermat's little theorem w/o cancellation.

• 9 is not invertible mod 21. May 4, 2021 at 8:53
• oh no. I need to do it over. @JaapScherphuis
– user403337
May 4, 2021 at 8:56
• The completely new revision has a big gap (for beginners), viz. you don't explain how "dividing out $9$" changes the modulus from $21$ to $7$, nor do you say whether that is a unidirectional or bidirectional inferences. But OP already said they cannot use this method, May 4, 2021 at 9:24
• Thanks for the input @BillDubuque CRT reduces it to mod $3,7$ calculation. But mod $3$ we have a tautology. OP wanted to use Fermat's little theorem. Did that when inverting $4$, though it might have been easier to do it "mentally". I suspect the OP is confused about what he/she can do.
– user403337
May 4, 2021 at 9:47
• Your first answer essentially divided by zero, Your latest one does another mystical division. Even I can't figure out what you intend from that prior comment, so how can a beginner? Please try to be more precise. May 4, 2021 at 9:54