Linear congruence question

[mooshupork34]

If anyone could explain how the following is done, it would be greatly appreciated!

Find all incongruent solutions to the following linear congruence:

21x ≡ 14 (mod 91)

 

[daon]

Did you mean congruent? I suppose incongruent would be "everything but what is congruent," so either way... Divide through by 7.

3x = 2 mod (13) (note 91 was divided by the GCD(91,7) which just happens to be 7).

So, 13 | (3x-2) ... (3x-2) = 13k

The solution set will be all integers (13k+2) such that 3|(13k+2).

Since any integer can be written as 3m, 3m+1, 3m+2, a few short substitutions gives k=3m+1 as the answer.

So k=1,4,7,10,13,..., 1+3(n-1), ... etc for n=1,2,3,4...

And that implies x=5, 18, 31, 44, ... , (13(k_n)+2)/3 = 13n-8, ... etc

Those are the x's that satisfy the congruency.