Summary
Highlights
Introduction to Modular Arithmetic00:00:14
Modular arithmetic is a system of arithmetic for integers where numbers 'wrap around' a certain value called the modulus (n). It can also be understood as 'clock arithmetic'. A formal definition states that 'a is congruent to b mod n' if and only if n divides (a - b), where a, b, and n are integers, and n is greater than 1.
Examples of Congruence and Finding Modulus 'n'00:01:06
Examples like '5 is congruent to 2 mod 3' are explained, where 3 divides (5-2). The definition also applies to negative values. The video demonstrates how to find possible values of 'n' given a congruence statement, such as finding 'n' when '11 is congruent to 5 mod n', which means n divides 6, leading to n = 2, 3, or 6.
Modular Arithmetic and Remainders00:02:54
Modular arithmetic deals with remainders. When a positive integer 'a' is divided by 'n', with quotient 'q' and remainder 'r', it implies 'a is congruent to r mod n'. An example is dividing 13 by 5, which gives a remainder of 3, so '13 is congruent to 3 mod 5'.
Operations in Modular Arithmetic00:04:52
In modular arithmetic, you can add, subtract, and multiply by the same number. Division, however, is problematic. The video illustrates this by showing how dividing both sides of a congruence by a common factor can lead to an incorrect statement if the modulus isn't also considered in a specific way.
Solving Congruences: Quadratic Example00:05:14
An example demonstrates solving 'x^2 + 3 is congruent to 0 mod 7'. By subtracting 3 and adding 7 (which is congruent to 0 mod 7), the equation becomes 'x^2 is congruent to 4 mod 7'. Solutions are x congruent to 2 and x congruent to -2, which is equivalent to 5 mod 7. This also shows that not all equations have solutions, as demonstrated by 'x^2 is congruent to 2 mod 4', which has no solution because perfect squares modulo 4 can only be 0 or 1.
Inverse and Division in Modular Arithmetic00:09:33
Fractions aren't directly defined in modular arithmetic. Instead, one multiplies by the inverse. The video explains finding the inverse of 3 mod 5 by adding multiples of 5 to the number 1, yielding '3x is congruent to 1 mod 5', which can be converted to '3x is congruent to 6 mod 5' and then solved as 'x is congruent to 2 mod 5'. This means the inverse of 3 mod 5 is 2.
The Chinese Remainder Theorem00:11:16
An ancient Chinese problem demonstrates a system of congruences: 'x is congruent to 2 mod 3', 'x is congruent to 3 mod 5', and 'x is congruent to 2 mod 7'. The solution, 23, satisfies all conditions. This type of problem is solved using the Chinese Remainder Theorem.
Applications: Finding the Last Digit of a Large Number00:12:43
Modular arithmetic can find the ones digit of large numbers, like 2 to the power of 2021. To find the ones digit, perform calculations modulo 10. The pattern of the ones digit of powers of 2 (2, 4, 8, 6) repeats every four terms. By finding 2021 mod 4, which is 1, the ones digit is the same as 2 to the power of 1, which is 2.
Applications: Remainder of a Factorial Sum00:15:01
Another application involves finding the remainder when an infinite sum of factorials (1! + 2! + 3!...) is divided by 9. Since 6! and all subsequent factorials are divisible by 9 (because 9 is a factor of 6!), their remainder is 0. Only the first five factorials need to be summed (1+2+6+24+120 = 153). The sum of digits of 153 (1+5+3=9) shows it's divisible by 9, so the remainder is 0.
Applications: Remainder of an Expression00:16:15
The video calculates the remainder of '2^n + 6 * 9^n' when divided by 7. By noting that 9 is congruent to 2 mod 7, the expression can be simplified to '2^n + 6 * 2^n', which equals '7 * 2^n'. Since any multiple of 7 is congruent to 0 mod 7, the remainder is 0.
Additional Topics in Modular Arithmetic00:17:40
The video concludes by listing advanced topics in modular arithmetic, including the Chinese Remainder Theorem, Fermat's Little Theorem, Euler's Theorem, Hensel's Lemma (for prime power moduli), and quadratic reciprocity.