3
$\begingroup$

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

This is what I made:

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

$\endgroup$
5
  • 1
    $\begingroup$ 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? $\endgroup$
    – Desperado
    May 4, 2021 at 7:57
  • $\begingroup$ 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/… $\endgroup$
    – 5xum
    May 4, 2021 at 7:59
  • $\begingroup$ Unfortunately, I have to solve and derive with Fermat's little theorem and not with the way I did it $\endgroup$
    – Gsomeone
    May 4, 2021 at 8:04
  • $\begingroup$ Thanks for the formatting! $\endgroup$
    – Gsomeone
    May 4, 2021 at 8:04
  • 1
    $\begingroup$ 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. $\endgroup$ May 4, 2021 at 9:17

1 Answer 1

0
$\begingroup$

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.

$\endgroup$
8
  • 1
    $\begingroup$ 9 is not invertible mod 21. $\endgroup$ May 4, 2021 at 8:53
  • $\begingroup$ oh no. I need to do it over. @JaapScherphuis $\endgroup$
    – user403337
    May 4, 2021 at 8:56
  • $\begingroup$ 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, $\endgroup$ May 4, 2021 at 9:24
  • $\begingroup$ 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. $\endgroup$
    – user403337
    May 4, 2021 at 9:47
  • $\begingroup$ 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. $\endgroup$ May 4, 2021 at 9:54

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .