Number Theory & Modular Arithmetic: Divisibility, Congruences, Primes & Applications

Unit 5: Number Theory and Modular Arithmetic

5.1 Divisibility and Divisors

Definitions

• Divisibility: An integer $a$ is divisible by an integer $b\ne 0$ if there exists an integer $k$ such that $a=b\cdot k$. We write $b\mid a$.
• Divisors: For an integer $n$, the set of all divisors of $n$ is denoted by $\text{Div}(n)$.
• Greatest Common Divisor (GCD): The largest integer that divides two or more integers. Denoted by $\gcd (a,b)$.
• Least Common Multiple (LCM): The smallest positive integer that is divisible by two or more integers. Denoted by $\text{lcm}(a,b)$.

Properties

• GCD Properties:
  • $\gcd (a,b)=\gcd (b,a\mathrm{mod}b)$ (Euclidean algorithm).
  • $\gcd (a,b)=\gcd (a,b+ka)$ for any integer $k$.
• LCM Properties:
  • $\text{lcm}(a,b)=\frac{|a\cdot b|}{\gcd (a,b)}$.

Worked Example

Find $\gcd (48,18)$ and $\text{lcm}(48,18)$.

Solution: Using the Euclidean algorithm:

1. $48=2\cdot 18+12$
2. $18=1\cdot 12+6$
3. $12=2\cdot 6+0$ Thus, $\gcd (48,18)=6$.

Now, $\text{lcm}(48,18)=\frac{48\cdot 18}{6}=144$.

---

5.2 Prime Numbers and Factorization

Definitions

• Prime Number: An integer $p>1$ is prime if its only positive divisors are 1 and $p$.
• Composite Number: An integer $n>1$ that is not prime (i.e., has divisors other than 1 and itself).
• Fundamental Theorem of Arithmetic: Every integer $n>1$ can be represented uniquely (up to ordering) as a product of prime numbers.

Prime Testing

• Trial Division: Check divisibility by all integers up to $\sqrt{n}$.
• Fermat's Little Theorem: If $p$ is prime and $a$ is not divisible by $p$, then $a^{p-1}\equiv 1(\mathrm{mod}p)$.
  • Example: Test if 561 is prime.
    • $2^{560}\mathrm{mod}561\ne 1$ (561 is a Carmichael number, not prime).

Applications

• Cryptography (RSA algorithm relies on primality testing).
• Hashing and error detection in computer science.

---

5.3 Modular Arithmetic

Definitions

• Congruence: Two integers $a$ and $b$ are congruent modulo $m$ if $m\mid (a-b)$. Written as $a\equiv b(\mathrm{mod}m)$.
• Modular Arithmetic: Arithmetic operations performed on integers modulo $m$.

Properties

• Reflexivity: $a\equiv a(\mathrm{mod}m)$.
• Symmetry: If $a\equiv b(\mathrm{mod}m)$, then $b\equiv a(\mathrm{mod}m)$.
• Transitivity: If $a\equiv b(\mathrm{mod}m)$ and $b\equiv c(\mathrm{mod}m)$, then $a\equiv c(\mathrm{mod}m)$.
• Addition/Subtraction: $a\equiv b(\mathrm{mod}m)$ and $c\equiv d(\mathrm{mod}m)$ implies $a+c\equiv b+d(\mathrm{mod}m)$ and $a-c\equiv b-d(\mathrm{mod}m)$.
• Multiplication: $a\equiv b(\mathrm{mod}m)$ and $c\equiv d(\mathrm{mod}m)$ implies $a\cdot c\equiv b\cdot d(\mathrm{mod}m)$.

Worked Example

Solve $3x\equiv 2(\mathrm{mod}5)$.

Solution: Find the multiplicative inverse of 3 modulo 5. Since $3\cdot 2=6\equiv 1(\mathrm{mod}5)$, the inverse of 3 is 2. Multiply both sides by 2: $x\equiv 4(\mathrm{mod}5)$. Thus, $x=5k+4$ for any integer $k$.

---

5.4 Applications in Computer Science

Hashing

• Modular arithmetic is used to compute hash values (e.g., $\text{hash}(key)=key\mathrm{mod}\text{table size}$).

Cryptography

• RSA Encryption: Relies on modular exponentiation and properties of primes.
• Digital Signatures: Use modular inverses for verification.

Pseudorandom Number Generation

• Linear congruential generators use modular arithmetic: $X_{n+1}=(a{X}_n+c)\mathrm{mod}m$.

---

5.5 Comparison Table: Key Concepts

---

5.6 Advantages and Disadvantages

---

Exam Tip

1. Understand Definitions: Memorize definitions of divisibility, GCD, LCM, primes, and congruences. Many questions test these directly.
2. Practice Euclidean Algorithm: Be able to compute GCD and LCM efficiently.
3. Modular Arithmetic: Know how to solve linear congruences (e.g., $ax\equiv b(\mathrm{mod}m)$) using inverses.
4. Prime Testing: Recognize Fermat's Little Theorem and its limitations (e.g., Carmichael numbers).
5. Applications: Link concepts to real-world uses like cryptography, hashing, and pseudorandom number generation.
6. Common Mistakes:
   • Forgetting that $\gcd (a,0)=a$.
   • Misapplying modular arithmetic (e.g., $(a+b)\mathrm{mod}m\ne (a\mathrm{mod}m+b\mathrm{mod}m)\mathrm{mod}m$ in general).
   • Confusing $\lfloor x\rfloor$ and $\lceil x\rceil$ in problems involving divisibility.

---

Past Exam Questions Covered:

• Divisibility and set representation (e.g., multiples of 3).
• Prime testing and Fermat's Little Theorem.
• Modular arithmetic in congruences.
• Applications in cryptography and combinatorics (e.g., counting problems).