2.1 Modular arithmetic and congruences

Modular arithmetic is a game-changer in number theory. It's like a clock where numbers wrap around after reaching a certain point. This system simplifies complex calculations and reveals hidden patterns in numbers, making it a powerful tool for solving tricky math problems.

In the world of additive number theory, modular arithmetic is a key player. It helps us understand how numbers behave when we add, subtract, or multiply them in a cyclic system. This knowledge is crucial for tackling more advanced concepts in the field.

Modular Arithmetic

Definition and Properties

• Modular arithmetic is a system of arithmetic for integers where numbers "wrap around" when reaching a certain value, called the modulus
• The modulus is a positive integer that determines the cyclical nature of the arithmetic
• Two numbers are said to be congruent modulo $n$ if their difference is divisible by $n$, denoted as $a \equiv b \pmod{n}$
• Modular arithmetic follows certain properties:
  • Reflexive property: $a \equiv a \pmod{n}$
  • Symmetric property: If $a \equiv b \pmod{n}$, then $b \equiv a \pmod{n}$
  • Transitive property: If $a \equiv b \pmod{n}$ and $b \equiv c \pmod{n}$, then $a \equiv c \pmod{n}$
• Modular arithmetic is closed under addition, subtraction, and multiplication, meaning that performing these operations on congruent numbers modulo $n$ results in congruent answers modulo $n$

Multiplicative Inverses and Division

• Modular arithmetic does not always have the property of division, as not every element has a multiplicative inverse modulo $n$
• A multiplicative inverse of $a$ modulo $n$, denoted as $a^{-1}$, exists when $gcd(a, n) = 1$
• When a multiplicative inverse exists, it can be used to solve linear congruences of the form $ax \equiv b \pmod{n}$
• The multiplicative inverse can be found using the extended Euclidean algorithm
• Example: To find the multiplicative inverse of 3 modulo 7, use the extended Euclidean algorithm:
  • $7 = 2 \cdot 3 + 1$
  • $3 = 3 \cdot 1 + 0$
  • Working backwards: $1 = 1 \cdot 7 - 2 \cdot 3$, so $3^{-1} \equiv -2 \pmod{7}$

Solving Linear Congruences

Methods for Solving Linear Congruences

• A linear congruence is an equation of the form $ax \equiv b \pmod{n}$, where $a$, $b$, and $n$ are known integers, and $x$ is an unknown integer
• To solve a linear congruence, find the value(s) of $x$ that satisfy the congruence
• One method to solve linear congruences is by using the multiplicative inverse of $a$ modulo $n$, denoted as $a^{-1}$, when $gcd(a, n) = 1$
  • Multiply both sides of the congruence by $a^{-1}$ to isolate $x$: $a^{-1}ax \equiv a^{-1}b \pmod{n}$ simplifies to $x \equiv a^{-1}b \pmod{n}$
• Another method is to use the extended Euclidean algorithm to find the modular multiplicative inverse when $gcd(a, n) = 1$
• Example: Solve the linear congruence $3x \equiv 4 \pmod{7}$
  • Using the multiplicative inverse method: $3^{-1} \equiv -2 \pmod{7}$, so $x \equiv -2 \cdot 4 \equiv 6 \pmod{7}$

Linear Congruences with No or Multiple Solutions

• If $gcd(a, n) \neq 1$, the linear congruence may have no solutions or multiple solutions
  • If $gcd(a, n)$ does not divide $b$, there are no solutions
  • If $gcd(a, n)$ divides $b$, there are $gcd(a, n)$ solutions
• Example: Consider the linear congruence $6x \equiv 9 \pmod{15}$
  • $gcd(6, 15) = 3$, which divides 9, so there are 3 solutions
  • Dividing both sides by 3 yields $2x \equiv 3 \pmod{5}$
  • Solving for $x$: $x \equiv 2^{-1} \cdot 3 \equiv 4 \pmod{5}$
  • The three solutions are $x \equiv 4, 9, 14 \pmod{15}$

Chinese Remainder Theorem

• The Chinese Remainder Theorem can be used to solve a system of simultaneous linear congruences with coprime moduli
• If the system of congruences is:
  • $x \equiv a_1 \pmod{n_1}$
  • $x \equiv a_2 \pmod{n_2}$
  • ...
  • $x \equiv a_k \pmod{n_k}$
• and $gcd(n_i, n_j) = 1$ for all $i \neq j$, then there exists a unique solution modulo $N = n_1 \cdot n_2 \cdot ... \cdot n_k$
• The solution is given by $x \equiv \sum_{i=1}^{k} a_i \cdot N_i \cdot y_i \pmod{N}$, where:
  • $N_i = N / n_i$
  • $y_i$ is the modular multiplicative inverse of $N_i$ modulo $n_i$

Applications of Modular Arithmetic

Number Theory

• Modular arithmetic is a powerful tool in solving various problems in number theory
• Fermat's Little Theorem states that if $p$ is prime and $gcd(a, p) = 1$, then $a^{p-1} \equiv 1 \pmod{p}$. This can be used to test for primality or to simplify calculations
• Euler's Theorem generalizes Fermat's Little Theorem for composite moduli: If $gcd(a, n) = 1$, then $a^{\phi(n)} \equiv 1 \pmod{n}$, where $\phi(n)$ is Euler's totient function
• The Chinese Remainder Theorem can be used to solve systems of linear congruences, which has applications in cryptography and coding theory
• Example: RSA cryptosystem relies on modular exponentiation and the difficulty of factoring large numbers

Cryptography and Coding Theory

• Modular exponentiation, computing $a^b \pmod{n}$, is a key operation in many cryptographic systems, such as RSA
• The security of RSA is based on the difficulty of factoring large numbers, which is related to the hardness of solving certain congruences
• Quadratic residues and the Legendre symbol can be used to determine the solvability of quadratic congruences modulo prime numbers
• Example: In the ElGamal encryption system, the public key is generated using modular arithmetic, and the security relies on the discrete logarithm problem

Modular Arithmetic vs Divisibility

Relationship between Modular Arithmetic and Divisibility

• Modular arithmetic is closely related to the concept of divisibility
• If $a \equiv b \pmod{n}$, then $n$ divides $a - b$, or equivalently, $a$ and $b$ have the same remainder when divided by $n$
• The congruence $a \equiv 0 \pmod{n}$ is equivalent to saying that $n$ divides $a$
• The set of integers modulo $n$, denoted as $\mathbb{Z}/n\mathbb{Z}$ or $\mathbb{Z}_n$, consists of equivalence classes of integers with the same remainder when divided by $n$
• Example: The set of integers modulo 5, $\mathbb{Z}_5$, consists of five equivalence classes: $[0], [1], [2], [3], [4]$

Division Algorithm and Divisibility Rules

• The division algorithm states that for any integers $a$ and $b$ with $b > 0$, there exist unique integers $q$ (quotient) and $r$ (remainder) such that $a = bq + r$, where $0 \leq r < |b|$. This is related to the congruence $a \equiv r \pmod{b}$
• Divisibility rules, such as the rules for divisibility by 2, 3, 5, 9, or 11, can be derived using modular arithmetic
• Example: A number is divisible by 3 if and only if the sum of its digits is divisible by 3, which can be proven using modular arithmetic:
  • Let the number be $a_n \cdot 10^n + a_{n-1} \cdot 10^{n-1} + ... + a_1 \cdot 10 + a_0$
  • Since $10 \equiv 1 \pmod{3}$, the number is congruent to $a_n + a_{n-1} + ... + a_1 + a_0 \pmod{3}$
  • Therefore, the number is divisible by 3 if and only if the sum of its digits is divisible by 3