1. ## Congruence classes

For the linear congruence equation $ax \equiv b \pmod{n}$, the general solution is given by $x = x_0 + \frac{nt}{d}$ where $x_0$ is a particular solution and $d = (a,n)$ and $t \in \mathbb{Z}$.

My book says for this general solution it forms 'd congruence classes mod n'. What does that mean?

I interpreted it as this:

$\frac{n}{d}$ is always a constant since $n = kd$ so $\frac{n}{d} = k$ for some integer constant $k$.

So $x = tk+x_0$ which can be written as $x \equiv x_0 \pmod{k}$ which says '$\frac{n}{d}$ congruence classes mod $\frac{n}{d}$'

There are $\frac{n}{d}$ congruence classes because $0 \le x_0 < k$ so there are $\{0, 1, 2, 3, \cdots k-1\}$ possible remainders, so there are $k$ congruence classes since there are $k$ possible remainders.

How did they get 'd congruence classes mod n'?

2. Originally Posted by usagi_killer
For the linear congruence equation $ax \equiv b \pmod{n}$, the general solution is given by $x = x_0 + \frac{nt}{d}$ where $x_0$ is a particular solution and $d = (a,n)$ and $t \in \mathbb{Z}$.

My book says for this general solution it forms 'd congruence classes mod n'. What does that mean?
Suppose we restrict t to $0 \le t < d$. It should be clear that these values of t will produce incongruent values mod n. Now suppose we let t = d. Then we have $x = x_0 + n \equiv x_0\ (\text{mod}\ n)$. So.. d congruence classes mod n.

3. Thanks but i still dont quite get it

say we have the basic equation a = b mod n

then a = nk+b where k is an integer.

now since 0<=b<n we have b = {0,1,2,3,...,n-1} as possible remainders which means n possible remainders so that means n congruence classes.

now applying this to the original Q

if we are using mod n then we have x = x_0 + (t/d) n.

now each congruence class represents a possible remainder, so 0=<x_0<n, so shouldn't there be n congruence classes?

4. Originally Posted by usagi_killer
Thanks but i still dont quite get it

say we have the basic equation a = b mod n

then a = nk+b where k is an integer.

now since 0<=b<n we have b = {0,1,2,3,...,n-1} as possible remainders which means n possible remainders so that means n congruence classes.

now applying this to the original Q

if we are using mod n then we have x = x_0 + (t/d) n.

now each congruence class represents a possible remainder, so 0=<x_0<n, so shouldn't there be n congruence classes?
$\displaystyle x_0$ doesn't range over the integers, but rather $\displaystyle t$ does.

Let's take a concrete example. Say we want to solve $\displaystyle 8x \equiv 16\ (\text{mod}\ 60)$. Obviously x=2 satisfies; we can use this as $\displaystyle x_0$. Now there are gcd(60,8)=4 distinct solutions mod 60. They are

$\displaystyle 2 + \frac{0\cdot60}{4} \equiv 2\ (\text{mod}\ 60)$

$\displaystyle2 + \frac{1\cdot60}{4} \equiv 17\ (\text{mod}\ 60)$

$\displaystyle2 + \frac{2\cdot60}{4} \equiv 32\ (\text{mod}\ 60)$

$\displaystyle2 + \frac{3\cdot60}{4} \equiv 47\ (\text{mod}\ 60)$