Modular arithmetic question.

Question

What solutions does the equation $4x≡2\mod 10$ have? (Hint, it will have more that one.) What about solutions to an equation $ax≡d \mod n$, where $d=\gcd(a,n)$? This is the question that appear in our universities last year paper. But it is seems very difficult for me like for first part I am able to solve by simplifications I got $x=5.Z+3$ as solution which makes sense and seems fair but for the second one I have no idea how can I approach that. Can you please help me out with that one. I tried to simplify that by using Euclidean algorithm but still I didn't get any idea that what actually the solution will be. My final exam is on 2nd of next month and because of covid I am unable to contact in person for any help. So any help from this site will be appreciated. Thanks you for looking at this question!

Answer 1

In my opinion it is better for you to understand the first-degree linear congruence equations in full generality rather than the particular case you posted.

Theorem. The congruence equation $ax\equiv b\pmod{n}$ has solutions if and only if ${\rm gcd}(a,n)\mid b$.

Proof. $(\Rightarrow)$ Let $x$ be a solution of the congruence equation. Then there exists an integer $k$ such that $ax=b+kn$ and from the Bézout identity we can infer that $b$ must be a multiple of ${\rm gcd}(a,n)$.

$(\Leftarrow)$ Let $d:={\rm gcd}(a,n)$ and write $b=db_1$, $a=da_1$ and $n=dn_1$. The congruence equation can be thus simplified to $$ a_1x\equiv b_1\pmod{n_1}. $$ Note that ${\rm gcd}(a_1,n_1)=1$, thus $a_1$ is invertible modulo $n_1$ (basically by Bézout identity again) and hence $x\equiv a_1^{-1}b_1\pmod{n_1}$ are the solutions of the initial congruence equation. $\Box$

As for your example, you can divide both sides (and the modulus!) by $2$, yielding $2x\equiv 1\pmod{5}$. Then, following the second part of the above proof, note that $3$ is an inverse of $2$ modulo $5$ and thus the solutions of the congruence equation are $x\equiv 3\pmod{5}$.

Answer 2

Hint:

As $4$ and $100$ are not coprime, $4$ has no inverse mod $10$, so you have to resort to the Chinese remainder theorem and solve both, since $10=2\cdot 5$, \begin{cases} 4x\equiv 2\equiv 0\mod 2 &\text{(satisfied by any $x$)}\\ 4x\equiv 2 \mod5 \end{cases} So you have to multiply both sides of the last congruence by the inverse of $4\bmod 5$, then combine both solutions to obtain solution $\bmod 10$ via the inverse isomorphism $$\mathbf Z/2\mathbf Z\times \mathbf Z/5\mathbf Z\longrightarrow \mathbf Z/10\mathbf Z.$$