Concept:
Given: ax ≡ b (mod m) --(1)
Step 1:
Find d,
d = the GCD of (a,m)
We have exactly 'd', incongruent solutions
Step 2:
Divide (1) with 'd', on both sides
find x1 as one solution of this congruency,
Step 3:
Now, find the incongruent solutions,
Where, 0 ≤ p ≤ (d-1)
Putting the values of 'p' in (2), we will get the required solutions.
Analysis:
6 x ≡ 3 (mod 9) ---(3)
d = GCD(6, 9) = 3
We have exactly 3 incongruent solutions,
Now, dividing (3), with 3, we get
2x ≡ 1 (mod 3)
We can manually see that x = 2,
4 - 1 ≡ 3 and (3 mod 3) = 0
One solution is x1 = 2,
Now, to find all the incongruent solutions,
Where, 0 ≤ p ≤ (3-1)
put, p = 0,
x = 2 + 0 = 2
put, p = 1,
x = 2 + 3 × 1 = 5
put, p = 2,
x = 2 + 3 × 2 = 8
The three incongruent solutions modulo 9 of this congruence are: 2, 5, 8