Week 9 - Number Theory
Congruence
- Congruence is a specific equality between numbers.
- Two numbers are congruent if they have the same remainder when divided by another number.
- We use the symbol “≡” to represent congruence.
For example: 17 ≡ 5 (mod 4) means that 17 and 5 have the same remainder (1) when divided by 4.
Example:
Determine if 23 and 11 are congruent when divided by 6.
- Divide 23 by 6. The remainder is 5.
- Divide 11 by 6. The remainder is also 5.
Since both remainders are the same (5), we conclude that 23 ≡ 11 (mod 6).
Multiplicative Inverse:
- A number that, when multiplied by another number, gives a product of 1.
- For example, the multiplicative inverse of 4 is 1/4 because 4 * 1/4 = 1.
Now, let’s learn about multiplicative inverse in the context of congruence (modular arithmetic).
Step-by-step process to find the multiplicative inverse of 724 modulo 47 using the Extended Euclidean Algorithm:
- (skip this step for now) Check if 724 and 47 are coprime. Since 724 = 2^3 * 181 and 47 is a prime number, they are coprime (GCD(724, 47) = 1).
We start with coefficients 0 and 1 because they represent the initial values for the identity ax + by = GCD(a, b). In this case, 724 * 1 + 47 * 0 = 724, and 724 * 0 + 47 * 1 = 47.
- Apply the Extended Euclidean Algorithm:
| Step | Remainder | Coefficient of 724(x) | Coefficient of 47(y) | Equation |
|---|---|---|---|---|
| 1 | 724 | 1 | 0 | 724(1) + 47(0) = 724 |
| 2 | 47 | 0 | 1 | 724(0) + 47(1) = 47 |
| 3 | 19 | 1 | -15 | 724(1) + 47(-15) = 19 |
| 4 | 9 | -2 | 31 | 724(-2) + 47(31) = 9 |
| 5 | 1 | 5 | -77 | 724(5) + 47(-77) = 1 |
- From the table, we see that the value of ‘x’ = 5 is the modular multiplicative inverse of 724 modulo 47.
So, the multiplicative inverse of 724 modulo 47 is 5, as 724 * 5 ≡ 1 (mod 47).
Incase, you get negative value of ‘x’, add modulus to it to get positive inverse, Positive inverse = -x + 47.
