Basics of Modular Arithmetic

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.

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.

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.

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.

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.

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.

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.

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.

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 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 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'.