Master Mathematician

Tuesday 28 July 2020

Important result related congruence relation and an example.

The proof is in video link given below.https://youtu.be/fugV55xPq4g

Theorem 4.3. If ca= cb (mod n), then a= b (mod n/d), where d = gcd(c, n).

Theorem 4.3. If ca= cb (mod n), then a= b (mod n/d), where d = gcd(c, n). Proof. By hypothesis, we can write c(a - b) = ca - cb = kn
for some integer k. Knowing that gcd(c, n) = d, there exist relatively prime integers r ands satisfying c = dr, n = ds. When these values are substituted in the displayed equation and the common factor d canceled, the net result is
r(a - b) =ks
Hence, s I r(a - b) and gcd(r, s) = 1. Euclid's lemma yields s I a - b, which may be recast as a = b (mods); in other words, a = b (mod n/d).
For video lec link is below.
https://youtu.be/dopXp7SyKNo

a is congruent to b(modn) if and only if a and b give same positive remainder upon division by n

The prove is very simple and straight forward you can get in video link below.
Video link.
https://youtu.be/RW0QD8van60https://youtu.be/RW0QD8van60

Congruence Relation

Definition 4.1. Let n be a fixed positive integer. Two integers a congruent modulo n, symbolized by

a= b (mod n) if n divides the difference a b; that is, provided that a b = kn for some integer k.

consider n = 7. It is routine to check that 3 = 24 (mod 7)

- 31 = 11 (mod 7) , -15 = -64 (mod 7) because 3 - 24 = (-3)7 -31- 11 = (-6)7, and -15 -(-64) = 7 · 7. When

n A' (a - b), we say that a is incongruent to b modulo n, and in this case we write a ¢ b (mod n). For a simple example: 25 ¢ 12 (mod 7), because 7 fails to divide 25 -12 = 13. It is to be noted that any two integers are congruent modulo .

https://youtu.be/BzZ6fJ4KWAU