How to solve modulo equations

Question

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.

Answer 1

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

Answer 2

It will be helpful if you look at Chinese Remainder theorem and Fermat's Little theorem. My solution to the second question is actually quite difficult, and it requires some knowledge of quadratic residues.

---

For the first question, by Chinese Remainder theorem, $x^{2018}\equiv 1\mod 21$ iff $$x^{2018}\equiv 1\bmod 3$$ $$x^{2018}\equiv 1\bmod 7$$

To solve the first congruence, first note that clearly $gcd(x,3)=1$. This means that we can apply Fermat's Little Theorem. We have $$x^{2018}\equiv 1\bmod 3$$ $$\left(x^2\right)^{1009}\equiv 1\bmod 3$$ $$(1)^{1009}\equiv 1\bmod 3$$ Hence, the congruence is satisfied for all $x$ coprime to $3$, which means $x\equiv 1,2\mod 3$

To solve the second congruence, first note that clearly $gcd(x,7)=1$. This means that we can apply Fermat's Little Theorem. We have $$x^{2018}\equiv 1\bmod 7$$ $$\left(x^6\right)^{336}x^2 \equiv 1\bmod 7$$ $$(1)^{336}x^2\equiv 1\bmod 7$$ $$x^2\equiv 1\bmod 7$$ $$x\equiv -1,1\bmod 7$$

So we have that $x$ must be congruent to $-1,1\bmod 7$ and $-1,1\bmod 3$. Using Chinese Remainder theorem, we can determine that there are $2^2$ solutions for $x$ in modulo $21$. Namely, (using brute force, or other methods) these are $$x\equiv 20,1,8,13\bmod 21$$

---

For the second question, after dividing by $5$ (watch out since $5|205$), we have $$x^{2107}\equiv 15\mod 41$$

To solve this congruence, first note that clearly $gcd(x,41)=1$. This means that we can apply Fermat's Little Theorem. We have $$x^{2107}\equiv 15\bmod 41$$ $$\left(x^{40}\right)^{52}x^{27}\equiv 15\bmod 41$$ $$(1)^{52}x^{27}\equiv 15\bmod 41$$ $$x^{27}\equiv 15\bmod 41$$ Note that we have $15+41\cdot 8=343=7^3$. Let's substitute $u=x^9$. $$u^3\equiv 15\bmod 41$$ $$u^3-343\equiv 0\bmod 41$$ $$(u-7)(u^2+7u+8)\equiv 0\bmod 41$$ Since the discriminant of $u^2+7u+8$ is $17$ and it's not hard to show with the law of quadratic reciprocity that using the legendre notation $$\left(\frac{17}{41}\right)$$ $$=\left(\frac{41}{17}\right)$$ $$=\left(\frac{7}{17}\right)$$ $$=\left(\frac{17}{7}\right)$$ $$=\left(\frac{3}{7}\right)$$ $$=-\left(\frac{7}{3}\right)$$ $$=-1$$ Hence, $17$ is a nonquadratic residue of $41$, so we get that the only solution to $u$ is $u\equiv 7\bmod 41$. So we now have $$x^9\equiv 7\bmod 41$$

Now substitute $v=x^3$, we want to find the solutions to $$v^3\equiv 7\bmod 41$$ The solutions to this are not trivial like the previous equation. However, note that by Fermat's Little theorem, we have $$7\equiv 7^{41}\equiv 7^{81}\equiv \left(7^{27}\right)^3\bmod 41$$ Hence, one of the solutions to $$v^3\equiv 7\bmod 41$$ is $v\equiv 7^{27}\bmod 41$. Note that $$7^{27}\bmod 41$$ $$\equiv 15^{9}\bmod 41$$ $$\equiv \left(15^2\cdot 15\right)^{3}\bmod 41$$ $$\equiv \left(20\cdot 15\right)^{3}\bmod 41$$ $$\equiv 13^3\bmod 41$$ $$\equiv 5\cdot 13\bmod 41$$ $$\equiv 24\bmod 41$$ Hence, we have the equation $$v^3\equiv 7\bmod 41$$ $$v^3\equiv 24^3\bmod 41$$ $$(v-24)(v^2+24v+2)\equiv 0\bmod 41$$ Note that the discriminant of $v^2+24v+2$ is $568\equiv 35\bmod 41$.

Since $\left(\frac{35}{41}\right)=\left(\frac{5}{41}\right)\left(\frac{7}{41}\right)$, we can show using similar reasoning as before with the law of quadratic reciprocity that $\left(\frac{5}{41}\right)=1$ and $\left(\frac{7}{41}\right)=-1$.

Hence, $35$ is also a quadratic nonresidue, which means that the only solution to $$v^3\equiv 7\bmod 41$$ is $v\equiv 35\bmod 41$

So we are now finally on the last lap with $$x^3\equiv 35\bmod 41$$ This one also does not have any trivial solutions. However, as we showed before, we know that one of the solutions will be $x\equiv 35^{27}\bmod 41$. We have $$35^{27}\bmod 41$$ $$7^9\bmod 41$$ $$15^3\bmod 41$$ $$13\bmod 41$$ Hence, we have $$x^3\equiv 35\bmod 41$$ $$x^3\equiv 13^3\bmod 41$$ $$(x-13)(x^2+13x+5)\equiv 0\bmod 41$$ The discriminant of $x^2+13x+5$ is $149\equiv 26\bmod 41$

Since $\left(\frac{26}{41}\right)=\left(\frac{2}{41}\right)\left(\frac{13}{41}\right)$. It follows from the second supplement of the law of quadratic reciprocity that $\left(\frac{2}{41}\right)=-1^{\frac{41^2-1}{8}}=1$.

We can show using similar reasoning as before with the law of quadratic reciprocity that $\left(\frac{13}{41}\right)=-1$. Thus, the only solution to $x^3\equiv 35\bmod 41$ is $\boxed{x\equiv 13\bmod 41}$

Answer 3

(1) $^{2018}=1 \pmod{21}$

Since $21 = 3 \cdot7$ is the prime decomposition of 21. \begin{align} x^{2018} \equiv 1 \pmod {21} \leftrightarrow x^{2018} \equiv 1\pmod {3} \wedge x^{2018} \equiv 1 \pmod {7} \end{align}

First let's check which number satisfy $x^{2018} \equiv 1\pmod {3}$:

Obviously $x=0$ doesn't work, but $x=1$ does satisfy $x^{2018} \equiv 1\pmod {3}$. We then check for $x=2$: \begin{align} 2^{2018} \equiv 4^{1009} \equiv 1^{1009} \equiv 1 \pmod {3} \end{align}

So the condition $x^{2018} \equiv 1\pmod {3}$ is satisfied for all $x \in \mathbb{Z}$ such that $x \equiv \pm 1 \pmod {3}.$

Let's now check which $x$ satisfy this first condition, and also satisfy the condition $x^{2018} \equiv 1 \pmod {7}$:

Obviously $x=1$ satisfies it. Now for $x=2$ we have:

\begin{align} 2^{2018} \equiv 4\cdot2^{2016} \equiv 4\cdot8^{672} \equiv 4\cdot1^{672} \equiv 4 \pmod {7} \end{align} which doesn't satisfy the condition. For $x = 3$ we have: \begin{align} 3^{2018} \equiv 9^{1009} \equiv 2^{1009} \equiv 2\cdot2^{1008} \equiv 2\cdot8^{336} \equiv 2\cdot1^{336} \equiv 2 \pmod {7} \end{align}

For $x = 4$ we have :

\begin{align} 4^{2018} \equiv 16^{1009} \equiv 2^{1009} \equiv 2\cdot2^{1008} \equiv 2\cdot8^{336} \equiv 2\cdot1^{336} \equiv 2 \pmod {7} \end{align}

For $x=5$ we have :

\begin{align} 5^{2018} \equiv 25\cdot 5^{2016} \equiv 4 \cdot 125^{672} \equiv 4\cdot 1^{672} \equiv 4 \pmod {7} \end{align}

For $x = 6$ we have : \begin{align} 6^{2018} \equiv 36^{1009} \equiv 1^{1009} \equiv 1 \pmod{7} \end{align}

which satisfies the condition.

we conclude that the only number which satisfy the original condition $x^{2018} \equiv 1 \pmod {21}$ are all $x \in \mathbb{Z}$ such that $x \equiv \pm 1 \pmod {3}$ and $ x \equiv \pm 1 \pmod {7}$

So those are the numbers in $\{..., -1,1,8,13,20,22,... \}$

Hopefully will this help you. I don't guarantee that this is the most efficient way to solve the problem but it does the job.

I am a bit stuck for the second exercise. You can say $5x^{2107} \equiv 75 \pmod {205} \implies x^{2107} \equiv 15 \pmod {41}$. Here it would be very painful to test every 41 possibilities for $x$. But since $41$ is prime you can use the little Fermat's theorem and say: \begin{align} x^{41} \equiv x \pmod{41} \end{align}

So it means :

\begin{align} x^{2017} \equiv x^{16} \cdot (x^{41})^{51} \equiv x^{16+51} \equiv x^{26} \cdot x^{41} \equiv x^{27} \pmod{41} \end{align}

Our problem is now $x^{27} \equiv 15 \pmod{41}$. But I don't know how to continue here either... If I was desperate and really wanted a solution, I would just try out every number from 0 to 40. Wolphrame alpha says the answer is $13 + 41\cdot k$ with $k \in \mathbb{Z}$

EDIT : now that I have seen the answer of Daniel Wainfleet I can finish this exercise.

He used a smart trick, which was to take the cube of that equation: $x^{27\cdot 3} \equiv 15^3 \equiv 13 \pmod{41}$. But how is this helpful ? Using the little Fermat's theorem again we can say \begin{align} a^{p-1} \equiv 1 \pmod{p} \end{align} if $p$ is prime. So that means $x^{40} \equiv 1 \pmod{41}$ which implies $x^{27} \equiv x^{81} \equiv x \cdot x^{40 \cdot 2} \equiv x \pmod{41}$.

From this he concludes $x \equiv 13 \pmod{41}$.