A way of finding $x \in \mathbb{Z}$, congruency

Question

I'm trying to find all $x \in \mathbb{Z}$ that satisfies this equation

$$3x \equiv 1 \pmod 6$$

---

I tried using trial and error, but couldn't find a suitable number for x.

I know that the $\mbox{gcd}$ is $3$.

How would I approach this?

Answer 1

Hint: A number $x$ satisfies $$3x \equiv 1 \pmod 6$$

if and only if there is an integer $k$ for which

$$3x - 1 = 6k$$

or alternatively,

$$3(x - 2k) = 1$$

---

More generally, the problem is that $3$ is a zero divisor in the ring of integers modulo $6$, and zero divisors can never be invertible.

Answer 2

No integer satisfies the equation. On the left hand side, $3| 3x$. On the right hand side, 3 does NOT divide $6k+1$ since $3$ does not divide 6.

Answer 3

Trial and error is fine in this case, as long as you try everything. If $x=0,1,2,3,4,5$ all don't work, you can conclude that there is no solution.

For larger moduli, "trying everything" is not practical, so we must look for conceptual shortcuts.

Answer 4

A solution mod $\,6\,$ remains a solution mod $\,3,\,$ yielding $\ 0\equiv 3x\equiv 1\pmod 3,\,$ contradiction.

Answer 5

There is no such $x,k\in Z$ such that $3(x-2k)=1$ is satisfied.