Mathematics Foundations/3.4 Modular Arithmetic

Modular Arithmetic Introduction Modular arithmetic is a system of arithmetic for integers where numbers "wrap around" after reaching a certain value called the modulus. This concept is fundamental to number theory and has numerous applications in computer science, cryptography, and everyday life. Congruence Relation Definition Two integers and are said to be congruent modulo (where ), written as , if divides the difference . Equivalently, and have the same remainder when divided by . Formally, if and only if for some integer . Examples: because because because Properties of Congruence Congruence modulo is an equivalence relation, meaning it satisfies: 1. Reflexivity: for any integer 2. Symmetry: If , then 3. Transitivity: If and , then Additionally, congruence respects basic arithmetic operations: 4. If and , then: * (addition) * (subtraction) * (multiplication) Proof of Multiplication Property: If and , then and for some integers and . Therefore: Thus, , which means . ∎ Congruence Classes The congruence relation modulo partitions the integers into equivalence classes called congruence classes. The set of all congruence classes modulo is denoted by or . Each congruence class contains all integers that have the same remainder when divided by . The class containing is often denoted by or simply when the modulus is clear from context. For modulus , the complete set of congruence classes is: Example: For , the congruence classes are: Modular Arithmetic Operations Modular arithmetic defines operations on congruence classes that mirror the standard operations on integers. Addition and Subtraction Addition and subtraction in modular arithmetic are performed by adding or subtracting representatives and then finding the remainder modulo : Example: In (clock arithmetic): Multiplication Multiplication in modular arithmetic is performed by multiplying representatives and then finding the remainder modulo : Example: In : Modular Exponentiation Modular exponentiation computes efficiently, even for large values of . A naive approach would compute and then find the remainder when divided by , but this becomes infeasible for large exponents due to the size of . The efficient algorithm uses the property that and employs the square-and-multiply method: 1. Express in binary: 2. Initialize 3. For each bit from down to 0: a. Set b. If , set 4. Return Example: Compute in binary is Initialize For bit : , then For bit : , then For bit : For bit : , then Therefore, Modular Multiplicative Inverse The modular multiplicative inverse of an integer modulo is an integer such that: The modular multiplicative inverse exists if and only if and are coprime, i.e., . The inverse can be computed using the Extended Euclidean Algorithm. If , then there exist integers and such that . The value of is the modular multiplicative inverse of modulo . Example: Find the modular multiplicative inverse of modulo Using the Extended Euclidean Algorithm, we find Therefore, We can verify: Modular Division Modular division is defined as , where is the modular multiplicative inverse of modulo . This operation is only defined when has a modular multiplicative inverse, i.e., when . Example: Compute First, find . From the previous example, Then, Properties of Modular Arithmetic Algebraic Structure The set with addition and multiplication modulo forms a commutative ring. If is prime, then forms a field, meaning every non-zero element has a multiplicative inverse. Fermat's Little Theorem Theorem: If is a prime number and is an integer not divisible by , then: An equivalent formulation is: for any integer . Proof Sketch: Consider the set . When we multiply each element by and take the result modulo , we get the set . Since , all elements in are distinct and none is congruent to 0 modulo . Therefore, is a permutation of . The product of all elements in is . The product of all elements in is . Since and contain the same elements (possibly in different order), their products are congruent modulo . Therefore: Since is not divisible by (by Wilson's theorem), we can cancel it from both sides to get: ∎ Euler's Theorem Euler's theorem generalizes Fermat's Little Theorem to any modulus , not just prime moduli. Theorem: If and are coprime positive integers, then: where is Euler's totient function, which counts the positive integers up to that are coprime to . Example: For , the numbers coprime to 15 are 1, 2, 4, 7, 8, 11, 13, 14, so . Therefore, if , then . Chinese Remainder Theorem The Chinese Remainder Theorem (CRT) provides a solution to systems of simultaneous congruences with coprime moduli. Theorem: Let be pairwise coprime positive integers. Then the system of congruences: has a unique solution modulo . The solution is given by: where and is the modular multiplicative inverse of modulo . Example: Solve the system: , (since ) , (since ) , (since ) We can verify: , , and . Applications of Modular Arithmetic Cryptography Modular arithmetic is fundamental to many cryptographic algorithms: RSA Encryption: Uses modular exponentiation with a composite modulus. Diffie-Hellman Key Exchange: Uses modular exponentiation for secure key exchange. ElGamal Encryption: Based on the difficulty of the discrete logarithm problem in modular arithmetic. Error Detection Checksums and check digits often use modular arithmetic: ISBN: The last digit of an ISBN-10 is a check digit computed using modulo 11. UPC and EAN: These barcode systems use modulo 10 check digits. Credit Card Numbers: The Luhn algorithm uses modulo 10 operations for validation. Hash Functions Many hash functions use modular arithmetic operations to compress data into a fixed-size output. Random Number Generation Linear congruential generators produce pseudorandom numbers using the recurrence relation: Calendar Calculations Modular arithmetic is used in determining the day of the week for a given date and in calculating dates of recurring events. Exercises 1. Compute: a) b) c) 2. Solve the following linear congruences: a) b) c) 3. Use the Chinese Remainder Theorem to solve the system: 4. Prove that if is prime and is not divisible by , then . 5. Find the last two digits of . 6. Determine all values of such that . 7. Prove that if is an odd prime, then (Wilson's theorem). 8. If and are distinct primes, find the number of solutions to . 9. Show that if is composite, there exists an integer such that and . 10. Implement an efficient algorithm for modular exponentiation and use it to compute .