Number Theory: Divisibility, Primes, Congruences & Applications

TAKEAWAYS:

• Master divisibility rules (e.g., 3, 9, 11) to simplify proofs and computations.
• Understand Euclid’s algorithm for GCD and its role in cryptography (e.g., RSA encryption).
• Apply modular arithmetic to solve problems in scheduling, hashing, and cyclic systems.
• Prove irrationality and primality using fundamental theorems (e.g., Fermat’s Little Theorem).
• Recognize real-world uses in error detection (e.g., ISBN checks), encryption (e.g., WhatsApp), and resource allocation (e.g., NEPSE stock trading).

Core Concepts and Definitions

1. Divisibility and Divisors

Definition:

• An integer $a$ is divisible by $b$ (written $b\mid a$) if there exists an integer $k$ such that $a=b\cdot k$.
• Divisors of $a$ are all integers $d$ where $d\mid a$.

Example:

• Divisors of 12: $\{-12,-6,-4,-3,-2,-1,1,2,3,4,6,12\}$.
• Visualization:

Note: Divisors come in pairs $(d,\frac{a}{d})$ except for perfect squares (e.g., 36 has $\pm 6$).

2. Prime Numbers and Fundamental Theorem of Arithmetic

Definition:

• A prime number $p$ has exactly two distinct positive divisors: 1 and $p$.
• Composite numbers have more than two divisors.

Fundamental Theorem of Arithmetic: Every integer $n>1$ can be expressed uniquely (up to ordering) as a product of primes: $$n=p_1^{k_1}{p}_2^{k_2}\dots p_m^{k_m}$$ where $p_i$ are primes and $k_i$ are positive integers.

Example:

• Prime factorization of 60: $$60=2^2\times 3\times 5$$

Why it matters:

• Used in cryptography (e.g., RSA relies on prime factorization being hard to reverse).
• Simplifies divisibility proofs (e.g., proving $\sqrt{2}$ is irrational).

Key Theorems and Proof Techniques

3. Euclid’s Algorithm for GCD

Definition: The greatest common divisor (GCD) of two integers $a$ and $b$ is the largest integer that divides both. Algorithm:

1. Divide $a$ by $b$, find remainder $r$.
2. Replace $a$ with $b$ and $b$ with $r$.
3. Repeat until $r=0$. The non-zero remainder is $\gcd (a,b)$.

Worked Example: Find $\gcd (48,18)$:

48 = 2 × 18 + 12
18 = 1 × 12 + 6
12 = 2 × 6 + 0

Answer: $\gcd (48,18)=6$.

Visualization:

graph LR
  A["48 ÷ 18"] -->|"remainder 12"| B["18 ÷ 12"]
  B -->|"remainder 6"| C["12 ÷ 6"]
  C -->|"remainder 0"| D["GCD = 6"]

Application:

• Used in simplifying fractions (e.g., $\frac{48}{18}=\frac{8}{3}$).
• Real-world: eSewa uses GCD to validate transaction amounts (e.g., ensuring no fractional cents in payments).

4. Least Common Multiple (LCM) and Relationship with GCD

Definition: The smallest positive integer divisible by both $a$ and $b$. Formula: $$\text{lcm}(a,b)=\frac{|a\cdot b|}{\gcd (a,b)}$$

Example: Find $\text{lcm}(12,18)$: $$\gcd (12,18)=6$$ $$\text{lcm}(12,18)=\frac{12\times 18}{6}=36$$

Table Comparison:

Real-world:

• NTC Bus Routes: If Bus A comes every 12 minutes and Bus B every 18 minutes, they meet every $\text{lcm}(12,18)=36$ minutes at a stop.

5. Modular Arithmetic

Definition: Two integers $a$ and $b$ are congruent modulo $m$ if $m\mid (a-b)$, written $a\equiv b(\mathrm{mod}m)$.

Properties:

1. $a\equiv b(\mathrm{mod}m)$ implies $a=b+km$ for some integer $k$.
2. Operations preserve congruence:
   • $(a+c)\equiv (b+c)(\mathrm{mod}m)$
   • $(a\cdot c)\equiv (b\cdot c)(\mathrm{mod}m)$

Example:

• $17\equiv 2(\mathrm{mod}5)$ because $17-2=15$ and $5\mid 15$.

Application in Cryptography:

• WhatsApp Encryption: Uses modular arithmetic to scramble messages. For example, sending a message $M$ encrypted as $C\equiv M\cdot K(\mathrm{mod}p)$, where $p$ is a large prime.

Proof Techniques

6. Proving Irrationality (Example: $\sqrt{2}$)

Theorem: $\sqrt{2}$ is irrational. Proof by Contradiction:

1. Assume $\sqrt{2}=\frac{p}{q}$ where $p,q$ are coprime integers.
2. Then $2=\frac{p^2}{q^2}$ ⇒ $2q^2=p^2$.
3. $p^2$ is even ⇒ $p$ is even ⇒ $p=2k$.
4. Substitute: $2q^2=(2k{)}^2=4k^2$ ⇒ $q^2=2k^2$.
5. $q^2$ is even ⇒ $q$ is even ⇒ Contradicts $p,q$ being coprime. Conclusion: $\sqrt{2}$ is irrational.

Visualization of Contradiction:

flowchart TD
  A["Assume √2 = p/q"] --> B["Square both sides: 2q² = p²"]
  B --> C["p² even ⇒ p even"]
  C --> D["p = 2k ⇒ 2q² = 4k² ⇒ q² even ⇒ q even"]
  D --> E["Contradicts coprimality"]
  E --> F["√2 is irrational"]

7. Fermat’s Little Theorem

Theorem: If $p$ is prime and $a$ is not divisible by $p$, then: $$a^{p-1}\equiv 1(\mathrm{mod}p)$$

Example: Verify for $p=5$, $a=2$: $$2^4=16\equiv 1(\mathrm{mod}5)$$ (since $16-1=15$ is divisible by 5).

Application:

• Primality Testing: Quickly check if a number is prime (though not foolproof).
• Digital Signatures: Used in cryptographic protocols (e.g., ElGamal).

## In the Real World

1. eSewa and Khalti (Transaction Validation):

   • Divisibility Rule: Both apps use modular arithmetic to check transaction amounts. For example, a payment of Rs. 125.75 is rejected if the decimal part doesn’t satisfy $0.75\equiv 0(\mathrm{mod}0.25)$ (ensuring no fractional paisa errors).
   • GCD in Fraud Detection: If a user sends Rs. 100 to two different accounts simultaneously, the system checks for overlapping divisors to flag anomalies.

2. NTC Bus Scheduling:

   • LCM for Timetables: Buses on routes with frequencies 10 and 15 minutes meet every $\text{lcm}(10,15)=30$ minutes at a terminal. This ensures passengers don’t wait indefinitely.
   • Modular Arithmetic for Seat Allocation: Seats are assigned using modulo operations to cycle through available seats efficiently.

3. NEPSE Stock Trading:

   • Divisibility in Order Matching: When buying/selling shares, the system checks if the quantity is divisible by the lot size (e.g., 100 shares per lot). For example, an order for 150 shares is split into 1 lot of 100 and 1 of 50 (if allowed).
   • Prime Numbers in Encryption: NEPSE’s secure trading platform uses prime-based encryption (like RSA) to protect transaction data.

4. Pathao’s Ride Matching:

   • Pigeonhole Principle: If Pathao has 100 drivers and 1000 requests in a city, the pigeonhole principle guarantees at least 10 drivers will receive 10 requests each (used for load balancing).

## Exam Tip

1. Proofs:

   • For irrationality proofs (e.g., $\sqrt{3}$), always use contradiction and assume the opposite.
   • For divisibility proofs, use direct proof or modular arithmetic.

2. Algorithms:

   • Memorize Euclid’s algorithm steps and practice on numbers like $\gcd (1234,567)$.
   • Know the relationship between GCD and LCM: $\gcd (a,b)\times \text{lcm}(a,b)=|a\cdot b|$.

3. Applications:

   • Link theorems to real-world examples (e.g., "This is how eSewa checks for valid payments").
   • For modular arithmetic, always verify with small numbers (e.g., $7\equiv 2(\mathrm{mod}5)$).

4. Common Pitfalls:

   • Off-by-one errors: In divisibility, $n\mid 0$ is always true (since $0=n\times 0$).
   • Prime checks: 1 is not a prime number. Always verify divisibility up to $\sqrt{n}$.

5. Past Exam Patterns:

   • Direct Proof: "Show that the sum of two odd numbers is even." Solution: Let $a=2k+1$, $b=2m+1$. Then $a+b=2(k+m+1)$, which is even.
   • Pigeonhole Principle: For 24 students and 10 grades, the maximum number of unique grades to ensure a duplicate is $10$ (since $11$ students would force a repeat by the pigeonhole principle).

Final Note: Number theory is the backbone of secure systems. Master these concepts, and you’ll ace both the exam and real-world problem-solving!