How do I divide a congruence equation?

Question

I found similar topics on StackExchange but none of them had answers that made any sense.

I'm trying to find at least one value of X such that x $\cong 3$ (mod 4) x $\cong$ 5 (mod 9)

I write it as:

x=9a +5

9a+5 $\cong$ 3 (mod 4)

Subtracting 5 from both sides yields:

9a $\cong$ 2 (mod 4)

I need to divide by 9 now. How on earth does this work?

And were my previous steps correct?

Answer 1

Yes your previous steps are OK.

You don't need to divide by $9$ since $9\equiv 1 \pmod 4$ so $9a\equiv 1a \pmod 4$ and thus you have $$a\equiv 2\pmod 4$$

---

So $a=4b+2$ and thus $x = 9(4b+2)+5 = 36b+23$

Answer 2

Your steps so far are pretty good. Dividing in moduli equivalences is tricky, as you can only divide by values coprime to the modulus. In this case, you can do so by finding what $9$ is equivalent to$\mod4$, and finding the power of that value that equals $2$. Below is an alternate solution.

When you have congruences where the moduli are mutually coprime, we know that there's a solution by the Chinese Remainder Theorem, and we can find this solution via Bezout's Identity.

So, we know that there exists, some $n, m\in\mathbb Z$ such that $x = 4n+3=9m+5$. So, $4n-9m=2$. By Bezout's Identity, we know that when $n=5$, $m=2$, $9m-4n=2$,so we have the desired relation. So, a solution in $\mathbb Z/36\mathbb Z$ is $4(5)+3=\color{red}{23}$.

Answer 3

Alternatively: $$x\equiv 3 \pmod{4} \Rightarrow 9x\equiv 27\pmod{36}\\ x\equiv 5 \pmod{9} \Rightarrow 4x\equiv 20\pmod{36}\\ \underbrace{5x}_{9x-4x}\equiv \underbrace{7}_{27-20} \pmod{36} \Rightarrow \\ 35x\equiv 49\pmod{36} \Rightarrow \\ 36x-x\equiv 13 \pmod{36} \Rightarrow \\ x\equiv -13\equiv 23\pmod{36}. $$

Answer 4

In general, if you want to "divide by $d$" in a ring, you multiply by the inverse of $d$ if it exists. In your case, $d=9\equiv 1 (\mod 4)$. You hence get the necessary condition $$a \equiv 2 (\mod 4)$$. Let's try with a=2, which gives $x=23$. Indeed, you get what you wanted since $23 \equiv 3 (\mod 4)$ and $(23 \equiv 5 (\mod 9)$.

In fact, it is also a sufficient condition, set $X:=\{x \in \mathbb{Z} \big| \ x\equiv 3 (\mod 4) \textrm{ and } x \equiv 5 (\mod 9)\}$ : $$x\in X \Longleftrightarrow x=9a + 5 \textrm{ for } a\equiv 2 (\mod 4)$$

Now, $a\equiv 2 (\mod 4)$ iff $a$ is of the form $a = 4k + 2$ for $k \in \mathbb{Z}$, this allows us to determine $X$ : $$X = \{9(4k+2)+5 \big| \ k\in \mathbb{Z}\}$$