Year 12s: what will be the first way you research your future options? >>

linear congruence equations?

Hello, I have just recently started learning about congruence mod n and I'm starting to get in to many difficulties.

I just don't understand how to solve linear congruence equations or simultaneous linear congruence equations. I just can't see how to solve them other than using the definition and saying if ax is congruent to b mod n then ax-b=kn but then I don't see what else you can do as obviously this may not have integer solutions in x so I just don't get how to solve them, I tried reading through the notes and I kind of understand some the lemma's/theorems but I just don't understand the examples.

Anyone can help me on this? Suggest me a good place to learn this stuff or just help me out.

Thanks.

Reply 1

Smaug123

Chinese Remainder Theorem states that you can simultaneously solve congruences mod coprime moduli:

a_1 x \equiv b_1 \pmod{n_1}, a_2 x \equiv b_2 \pmod{n_2}

with

(n_1, n_2) = 1

has unique (mod

n_1 n_2

)

x

solving them. You should have had the CRT proved for you, and you should be able to step through the proof with an example. Such a proof is, for instance, here.