For the linear congruence equation , the general solution is given by where is a particular solution and and .
My book says for this general solution it forms 'd congruence classes mod n'. What does that mean?
I interpreted it as this:
is always a constant since so for some integer constant .
So which can be written as which says ' congruence classes mod '
There are congruence classes because so there are possible remainders, so there are congruence classes since there are possible remainders.
How did they get 'd congruence classes mod n'?
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?