Hello! When I hear the word “congruence,” the first thing that pops up in my mind is congruence in geometry. It turns out, however, that there can be congruence in numbers, well specifically in modular arithmetic! In this post, we will explore congruence in modular arithmetic.
Given integers a, b, and n, with n > 0, we say that a is congruent to b modulo n, or a ≡ b (mod n), if the value of (a - b) is visible by n. Two numbers a and b are said to be “congruent to modulo n” if (a mod n) = (b mod n). For example, 73 ≡ 4 (mod 23) since 73 - 23 = 69 is divisible by 23.
Now that we have an idea about the definition of congruence, we will explore some properties of congruence:
Consider four integers a, b, c, and d and a positive integer m (m >0) such that a ≡ b (mod m) and c ≡ d (mod m). In modular arithmetic, the following properties hold:
- Addition: a + c ≡ b + d (mod m)
- Subtraction: a - c ≡ b - d (mod m)
- Multiplication: ac ≡ bd (mod m)
- Division: (a/e) ≡ (b/e) {mod m/gcd (m, e)} where e is a positive integer that divides both a and b.
- Exponentiation: a^e ≡ b^e (mod m) where e is a positive integer
- a ≡ b (mod n) => b ≡ a (mod m)
- a ≡ b (mod m) and b ≡ c (mod n) => a ≡ c (mod n)
Some examples of the more advanced properties of congruence relations include the following:
- Wilson's theorem: p is prime if and only if (p − 1)! ≡ −1 (mod p)
- Chinese remainder theorem: If x ≡ a (mod m) and x ≡ b (mod n) such that m and n are co-prime (the only positive integer that divides both of them is 1), then x ≡ b mn–1 m + a nm–1 n (mod mn) where mn−1 is the inverse of m modulo n and nm−1 is the inverse of n modulo m
- Lagrange's theorem: The congruence f (x) ≡ 0 (mod p), where p is prime, and f (x) = a0 xn + ... + an is a polynomial with integer coefficients such that a0 ≠ 0 (mod p), has at most n roots.
This is it for today and I hope you all have a great rest of the day. Also, please feel free to contact me or comment below if you have any questions!
No comments:
Post a Comment