It is an equivalence relation, that is :
An important case is when m is a prime p :
If p is a prime Z/pZ is a field 
The condition is also necessary because if m is not prime, Z/mZ has at least one divisor of 0,
that is there are two integers a and b not null with a×b ≡ 0 (mod m).
If m is not prime, Z/mZ is just a ring.
Every element (a) in Z/pZ has an inverse (a') : (a)×(a') = 1 that is a×a' ≡ 1 (mod p)
If m not prime, (a) has an inverse iff GCD(a,m) = 1.
Example : 14x ≡ 21 (mod 35)
GCD of 14 and 35 is 7, dividing 21, solutions are the same as 2x ≡ 3 (mod 5)
Inverse of 2 modulo 5 is 3 , hence x ≡ 3×3 ≡ 4 (mod 5)
And 7 solutions in Z/35Z : 4, 9, 14, 19, 24, 29, 34.
Let m = m_{1}m_{2}...m_{n}
and calculate the inverses
q_{i} ≡ (m/m_{i})^{1} modulo m_{i}
Then x ≡ ∑q_{i}a_{i}m/m_{i} modulo m
Applying EulerFermat gives a formula for the
q_{i} ≡ (m/m_{i})^{φ(mi)1} modulo m_{i}
Practically we prefer to use Euclide algorithm to solve
(m/m_{i})×q_{i} ≡ 1 modulo m_{i}.
Example :
x ≡ a modulo 7
x ≡ b modulo 11
x ≡ c modulo 13
7, 11 and 13 being two by two coprime (and even just primes),
We get a unique x modulo 7×11×13 = 1001.
q_{1} ≡ (11×13)^{1} ≡ 143^{1} ≡ 3^{1} ≡ 5 modulo 7
q_{2} ≡ (7×13)^{1} ≡ 91^{1} ≡ 3^{1} ≡ 4 modulo 11
q_{3} ≡ (7×11)^{1} ≡ 77^{1} ≡ 12^{1} ≡ 12 modulo 13
x ≡ a×5×11×13 + b×4×7×13 + c×12×7×11 ≡ 715a + 364b + 924c modulo1001
We can then suppose GCD(a,m) = 1.
Hence a has an inverse a', and multiplying by a' we get
x² + b'.x + c' ≡ 0
Our examples gives 1/7 = 8 (mod 11) and
7k² + 6k + 9 ≡ 0 (mod 11) <=>
k² + 4k + 6 ≡ 0 (mod 11)
To finish this example, (k + 2)² + 2 ≡ 0 (mod 11) that is
y² ≡ 9 (mod 11) => y ≡ ±3 (mod 11).
and taking calculation backwards k = y  2 then
x = 1 + 3k = 3y  5 ≡ 4 and 19 (mod 33)
For instance : x² + 3x + 5 ≡ 0 (mod 25)
1/2 = 13 (mod 25) hence :
x² + 3x + 5 ≡ x² + 2×(13×3)x + 5
≡ x² + 2×14x + 5 that is
(x+14)² ≡ 14²  5 ≡ 16 (mod 25)
then solutions are x + 14 ≡ ± 4 (mod 25) that is x = 7 and 15 mod 25
Multiplication by q = 1/2 is useless if b even = 2b' :
x² + 2b'.x + c ≡ 0 can directly be written
(x + b')² ≡ b'²  c
Example : x² + 7x + 2 ≡ 0 (mod 8)
1) x = 2u : 4u² + 14u + 2 ≡ 4u² + 6u + 2 ≡ 0 (mod 8)
2u² + 3u + 1 ≡ 0 (mod 4), 3u + 1 ≡ 0 (mod 2), u = 2k + 1
(2k + 1)² + 3k + 4 ≡ (2k + 1)² + k ≡ 0 (mod 2)
4k² + 5k + 1 ≡ k + 1 ≡ 0 (mod 2)
hence k = 2m + 1 and x = 2u = 4k + 2 = 8m + 6
2) x = 2u + 1 : 4u² + 18u + 10 ≡ 4u² + 2u + 2 ≡ 0 (mod 8)
2u² + u + 1 ≡ 0 (mod 4), u = 2k + 1
(2k + 1)² + k + 1 ≡ 0 (mod 2)
4k² + 5k + 2 ≡ k ≡ 0 (mod 2)
hence k even = 2m, x= 2u + 1 = 4k + 3 = 8m + 3
And two solutions modulo 8.
x² ≡ 1 (mod 2) has only one solution : x = 1
x² ≡ 1 (mod 4) has two solutions : x = ± 1 x² ≡ 1 (mod 2^{n}), n>2, has four solutions : x = ± 1 and x = ±(2^{n  1}  1) x² ≡ 1 (mod p^{n}), p odd prime, has two solutions : x = ± 1 
The same number at most of solutions for x² ≡ a (mod m),
else, no solutions at all.
we define a quadratic residue as a number a for which
x² ≡ a (mod m) has a solution.
We just limit to numbers to a being coprime with m, and even to m being p^{n}, p prime,
by using chinese remainder theorem.
Coming back to x² ≡ a (mod m), let's try an example :
find all squares which end in 329.
x² ≡ 329 (mod 1000).
As 1000 = 2³×5³ we have first to solve the two modular equations :
x² ≡ 329 ≡ 1 (mod 8) and
x² ≡ 329 ≡ 79 (mod 125)
The first one x² ≡ 1 (mod 8) has solutions x ≡ ±1 or ±3 (mod 8)
the second one x² ≡ 79 (mod 125) is a litle bit harder.
Let's solve first x² ≡ 79 ≡ 4 (mod 5)
whose solutions are obviously x ≡ ±2 (mod 5).
Solutions of x² ≡ 79 ≡ 4 (mod 25),
even if in this case obvious, but just to show the method, are deduced from
the previous solutions ±2 (mod 5)
as being ±2 + 5k.
that is (±2 + 5k)² = 4 ± 20k + 25k² ≡ 4 (mod 25)
Hence 20k ≡ 0 (mod 25) or 4k ≡ 0 (mod 5).
Solutions of x² ≡ 4 (mod 25) are then as expected
x ≡ ±2 (mod 25)
Search then solutions of x² ≡ 79 (mod 125) from those modulo 25
as being ±2 + 25k :
(±2 + 25k)² = 4 ± 100k + 25²k² ≡ 79 (mod 125)
that is ±100k ≡ 75 (mod 125) hence ±4k ≡ 3 (mod 5)
whose solutions are k = ±2 + 5m then
x = ±2 + 25k = ±52 + 125m.
Generally speaking, solutions of x² ≡ a (mod p^{n+1})
are obtained from solution x_{0} of x² ≡ a (mod p^{n}) as being
x_{0} + k.p^{n} :
(x_{0} + k.p^{n})^{2} = x_{0}^{2} + 2k.x_{0}p^{n} + k^{2}p^{2n} ≡ x_{0}^{2} + 2k.x_{0}p^{n} ≡ a (mod p^{n+1})
as 2n>n+1 as soon as n>1.
Because x_{0}² ≡ a (mod p^{n}), this reduces to a modulo p relation :
2k.x_{0} ≡ a  x_{0}² (mod p).
Hence value of k and x_{0} + k.p^{n}.
Solutions of x² ≡ 329 (mod 8) and of
x² ≡ 329 (mod 125) are then "mixed" by the chinese remainder theorem
to get solutions of x² ≡ 329 (mod 1000).
First of all let's calculate 1/125 ≡ 5 (mod 8) and 1/8 ≡ 47 (mod 125)
then solutions are : u×5×125 + v×47×8 (mod 1000)
with u any solution of x² ≡ 329 (mod 8) that is the four values ±1 and ±3,
and v solution of x² ≡ 329 (mod 125) that is v = ±52
hence 4×2 = 8 solutions :
1×625 + 52×376 ≡ 177 (mod 1000)
1×625  52×376 ≡ 73 (mod 1000)
1×625 + 52×376 ≡ 927 (mod 1000)
1×625  52×376 ≡ 823 (mod 1000)
3×625 + 52×376 ≡ 427 (mod 1000)
3×625  52×376 ≡ 323 (mod 1000)
3×625 + 52×376 ≡ 677 (mod 1000)
3×625  52×376 ≡ 573 (mod 1000)
(Which we can reduce two just two solutions : 73 and 177 modulo 250)
Remains just to solve x² ≡ a (mod p), p prime.
For small values of p the most efficient is just try (p1)/2 values from
1 to (p1)/2,
for larger p there is a more efficient method : TonelliShanks algorithm.
Generally speaking, there is a primitive root g of m iff m = 2, 4, p^{n}, 2p^{n}, p odd prime.
g^{k} ≡ 1 modulo m, and the smallest k (order of g) is φ(m), Euler totient function of m.
There are then φ(φ(m)) primitive roots.
The problem is to find a primitive root.
g is not a primitive root of m if :
 GCD(g,m) ≠ 1
 or p is a prime factor of φ(m) and g^{φ(m)/p} ≡ 1 modulo m
Finding g can be done systematically or at random :
m = 2 : g = 1
m = 4 : g = 3 m = p^{n} or 2p^{n} : find a primitive root of p
If g not a primitive root of p^{n}, remplace g by g + p

Number of solutions of x^{n} ≡ a modulo p is either 0 or d = GCD(n, p1) 
The problem is then to find a primitive root g of p, and to find h with a ≡ g^{h} modulo p.
Example :
x^{10} ≡ 43 modulo 97
First find a primitive root of 97
φ(97) = 96 = 2^{5}×3, test on g is then on g^{φ(m)/p} = g^{48} and g^{32}
2^{16} ≡ 61 modulo 97 at most 2^{32} ≡ 35 and 2^{48} ≡ 1
3^{16} ≡ 61 modulo 97 at most 3 doesn't work either
5^{16} ≡ 36 modulo 97 at most 5^{32} ≡ 35 and 5^{48} ≡ 96
Hence 5 is a primitive root of 97.
We have then to find h such as 5^{h} ≡ 43 modulo 97
Calculating successive powers of 5 gives :
5, 25, 28, 43... hence 43 = 5^{4} (without need of calculating all the 96 powers ! pff !)
Remains to solve 10.k ≡ 4 modulo 96 that is 5.k ≡ 2 modulo 48 and k = 10 and 58.
And finally two solutions x ≡ 5^{10} ≡ 53 modulo 97
and x ≡ 5^{58} ≡ 44 modulo 97.