How many solutions there are for $x \in Z_6$ in the following equations?

Question

How many solutions there are for $x \in Z_6$ in the following equations?

$x\cdot[3]_6 = [4]_6$
$x\cdot[5]_6 = [4]_6$
$x\cdot[5]_6 = [3]_6$
$x\cdot[3]_6 = [3]_6$

I can find the number of solutions simply by testing all (6) possible x's, but I'd like a smart explanation of the behavior of the number of solutions of these different equations.

Answer 1

For an equation $$ [a]x=[b] $$ (where $a,b\in\Bbb Z$ and $x\in\Bbb Z_n$ for some natural $n$), there are either $\gcd(a,n)$ solutions, or no solutions. These solutions exist iff $b$ is a multiple of $\gcd(a,n)$.

First of all, the smallest positive integer $k$ such that $[a]x=[k]$ has a solution is $\gcd(a,n)$ (the extended Euclidean algorithm or Bézout's identity can tell you this). Further, any multiple of $k$ also clearly gives solutions. Finally, if $\ell$ is an integer which is not a multiple of $k$, then there cannot be any solutions to $[a]x=[\ell]$, as that would imply a solution to $[a]x=[\gcd(k,\ell)]$, where $0<\gcd(k,\ell)<k$, which can't happen by definition of $k$.

And why are there $\gcd(a,n)$ solutions? Because by the above characterisation of which conjugacy classes $[b]$ give solutions, there are $\frac{n}{\gcd(a,n)}$ such classes. And each of them have an equal number of solutions.

So in your case, for instance, the equations $[3]x=[b]$ will have $\gcd(3,6)$ solutions iff $b$ is a multiple of $\gcd(3,6)$, and no solutions otherwise.

Answer 2

The first equation is 3x= 4 (mod 6) which is the same as 3x= 4+ 6n or 3x- 6n= 4, for some integer, n. I have an immediate problem with that! For any x and n, 3x and 6n are divisible by 3, so 3x- 6n is a multiple of 3 but 4 is not. There is no solution.

The second equation is 5x= 4 (mod 6) which is the same as 5x= 4+ 6n or 5x- 6n= 4. It is obvious that 6- 5= 1 so taking x= -1 and n= -1, 5x- 5n= 5(-1)- 6(-1)= 6- 5= 1. Multipying by 4, 5(-4)- 6(-4)= 4. One solution is x= -4, All solutions are of the form x= -4+ 6k for some integer k. Taking k= 1 gives x= -4+ 6= 2 as the only solution in $Z_6$.

The third equation is 5x= 3 (mod 6) which is the same as 5x= 3+ 6n or 5x- 6n= 3. Again 5(-1)- 6(-1)= 6- 5= 1 so 5(-3)- 6(-3)= 3. All solutions are of the form x= -3+ 6k for some k. x= -3+ 6(1)= 3 is the only solution in $Z_6$.

The last equation is 3x= 3 (mod 6). Dividing by 3 gives x= 1 as an obvious solution but 6 is also divisible by 3 so writing the equation as 3x= 3+ 6k, we have x= 1+ 3k. Now taking k= 1 we have x= 4. There are two solutions, x= 1 and x= 4, in $Z_6$.