Algebra of Congruent Modulo n

For any integers a, b, c, d and positive integer n

1. a ≡ a (mod n)

2. If a ≡ b (mod n), then b ≡ a (mod n).

3. If a ≡ b (mod n) and b ≡ c (mod n), then a ≡ c (mod n).

4. If a ≡ b (mod n) and c ≡ d (mod n), then a ± c ≡ b ± d (mod n).

5. If a ≡ b (mod n) and c ≡ d (mod n), then ac ≡ bd (mod n).

6. The division in two congruent modulo n is not always possible, means, one cannot say as a rule that If a ≡ b (mod n) and c ≡ d (mod n), then a/c ≡ (b/d) (mod n). Hence there is a concept of inverse congruent module, which we learn later.

7. Very important. Let a = nq + r. That is: a == r mod n.

Then we have remainder (r|a) = remainder (r|n).

Its converse is also true. Given, remainder (r|a) = remainder (r|n); then a = r mod n. Thus gcd(a, r) = gcd(n, r).

Without proof but with an example we can put it like this.

We have: 447 == 6 mod 7, as 447-6 = 441 is divisible by 7.

Hence remainder (7|447) = remainder (7|6) = 6; and gcd (7, 447) = gcd(6, 7) = 1.

And conversely, given that remainder (5|17) = remainder (5|87) = 2;

then 87 == 2 mod 5

Now Remainder (109, 5) = 4; Remainder (128, 5) = 3; Remainder (141, 5) = 1; Remainder (176, 5) = 1; Remainder (193, 5) = 3.

Now, the property (e) is the most important and most interesting.