Can somebody fill in the skipped step so I can understand. Linear congruence equation.

Question

I'm trying to understand why $$~3y \equiv -1 \mod 2 \implies y \equiv 1 \mod 2~$$ I know that if $a \equiv b \pmod m$ then $a-b=km$ where $k$ is an integer.

And if you subtract a multiple of m you still have a multiple of m. But I'm still struggling to see this.

Can anybody fill in the steps very explicitly so I can try to understand why this implication is true?

Thanks so much.

Answer 1

$$3y \equiv -1 \equiv 1 \mod 2 \implies 2y + y \equiv 1 \mod 2 \implies y \equiv 1 \mod 2$$

because $1 - (-1) = 1\cdot 2$ and $2y \equiv 0 \mod 2$.

Answer 2

$-1 \mod 2$ and $1 \mod 2$ are both fancy names for odd numbers, you can easily check this with the definition. So the implication can be translated to $3y \:\: \textrm{is odd} \implies y \: \: \textrm{is odd}$, which I think you should be able to prove.

In general, suppose we want to solve the equation $ax \equiv b \mod n$, and assume that $\gcd(a,n) = 1$. There is a lemma called Bezout's lemma that guarantees the existence of integers $r,s$ such that $ar + ns = 1$, i.e. $ar \equiv 1 \mod n$. Multiplying our equation by $r$ on both sides gives the solution $x \equiv rb \mod n$. This implies that the solution $\mod n$ is unique, so if the right hand side of the implication is already given you just have to check if it satisfies the equation. If you want to solve for $r$ yourself, use the extended Euclidean algorithm. In case of very small numbers brute force also works of course.

Answer 3

I will sometimes denote $y \equiv x \mod b$ by $y \equiv_b x$.

When you have one of these rings $\mathbb Z_b$, there are certain algebraic rules you can use. When you write $3y \equiv_2 -1$, think about the number $3$. This doesn't exist in the ring $\mathbb Z_2$, does it? $\mathbb Z_2$ contains just two elements. "3" is in fact an alternate label for the element $1$ since: $$3 \equiv_2 1$$ It turns out to be consistent to reduce coefficients of numbers as well as the numbers themselves. i.e.: $$a \cdot y \mod b \equiv (a \mod b) \cdot (y \mod b)$$

In this case, $$3y \mod 2 \equiv (3 \mod 2) \cdot (y \mod 2) \equiv 1 \cdot y \mod 2$$

And so: $$3y \mod 2 \equiv -1 \Rightarrow y \mod 2 \equiv -1$$ And of course, $-1 \mod 2 \equiv 1$ since $-1 + 2 = 1$.

---

Proof: Multiplication is well-defined for modular arithmetic equivalence classes of $\mathbb Z$.

Let $a,b \in \mathbb Z$ such that $a = b + k\cdot n$ where $k \in \mathbb Z$. This is equivalent to saying:

Let $a,b \in \mathbb Z : a \equiv_n b$.

Let $y \in \mathbb Z$. Consider $a\cdot y \mod n$. $$a \cdot y \mod n = (b + k\cdot n) \cdot y \mod n = (b\cdot y + k\cdot y \cdot n) \mod n = b\cdot y \mod n$$

---

$a$ and $b$ here are equivalent elements of the structure $\mathbb Z_n$. The proof showed that this equivalence is well-defined under multiplication. That is, any two equivalent elements will multiply with other elements and yield the same result. This should be the case, otherwise the structure wouldn't be well-defined.

The point is that when you see numbers like "3" in a situation like this, they are in fact duplicate labels for one of the elements in the ring. In this case, "3" is like another label for the element "1". It is absolutely correct and consistent to think of it in this way.