Number Theory: Divisibility, Primes, GCD, LCM & Cryptography

TAKEAWAYS:

• Divisibility rules simplify checking if one number divides another (e.g., 3 divides a number if the sum of its digits is divisible by 3).
• GCD and LCM are found using the Euclidean algorithm and prime factorization, respectively.
• Modular arithmetic is the foundation of cryptographic systems like RSA and hashing.
• Number theory solves real problems: from eSewa transaction IDs to Ncell’s network routing.
• Prime numbers are the "building blocks" of all integers and are critical in encryption.
• The Euclidean algorithm efficiently computes GCD, even for large numbers.

1. Divisibility and Divisibility Rules

Divisibility means that when integer $a$ divides integer $b$ (written $a\mid b$), there exists an integer $k$ such that $b=a\cdot k$. For example, $3\mid 15$ because $15=3\times 5$.

Divisibility Rules (Quick Checks)

Example: Check if 12345 is divisible by 3.

• Sum of digits: $1+2+3+4+5=15$.
• $15$ is divisible by 3, so $3\mid 12345$.

Real-World Use:

• eSewa uses divisibility checks to validate transaction IDs (e.g., ensuring a 12-digit ID is divisible by 7 for error detection).
• Ncell’s billing system applies divisibility rules to verify phone numbers and invoice totals.

2. Prime Numbers and Factorization

A prime number is a natural number greater than 1 with no positive divisors other than 1 and itself. The first few primes are 2, 3, 5, 7, 11, etc.

Prime Factorization

Every integer $n>1$ can be expressed as a product of primes: $$n=p_1^{a_1}\cdot p_2^{a_2}\cdots p_k^{a_k}$$ Example: Factorize 60. $$60=2^2\times 3\times 5$$

Real-World Use:

• RSA Encryption (used by banks and eSewa) relies on the difficulty of factoring large primes.
• NEPSE stock market uses prime-based hashing to secure transaction logs.

3. Greatest Common Divisor (GCD) and Least Common Multiple (LCM)

GCD (Greatest Common Divisor)

The largest number that divides two or more integers without leaving a remainder. Methods to find GCD:

1. Prime Factorization: For $a=48=2^4\times 3$ and $b=18=2\times 3^2$, $$\text{GCD}(48,18)=2\times 3=6$$

2. Euclidean Algorithm (Efficient for large numbers): $$\text{GCD}(a,b)=\{\begin{array}{ll}a& \text{if }b=0,\\ \text{GCD}(b,a\mathrm{mod}b)& \text{otherwise.}\end{array}$$ Example: Compute $\text{GCD}(56,98)$. $$\begin{gathered} 98=56\times 1+42 \\ 56=42\times 1+14 \\ 42=14\times 3+0⟹\text{GCD}=14 \end{gathered}$$

LCM (Least Common Multiple)

The smallest positive integer divisible by both numbers. Relationship between GCD and LCM: $$\text{LCM}(a,b)=\frac{a\times b}{\text{GCD}(a,b)}$$ Example: Find $\text{LCM}(12,18)$. $$\text{GCD}(12,18)=6$$ $$\text{LCM}(12,18)=\frac{12\times 18}{6}=36$$

Real-World Use:

• NTC’s network scheduling uses LCM to synchronize signals across towers.
• Khalti’s payment cycles rely on GCD to avoid overlapping transaction deadlines.

4. Modular Arithmetic

Modular arithmetic deals with remainders. For integers $a,b,n$ (where $n>0$): $$a\equiv b(\mathrm{mod}n)$$ means $n\mid (a-b)$.

Example: Compute $17\mathrm{mod}5$. $$17=5\times 3+2⟹17\equiv 2(\mathrm{mod}5)$$

Applications:

• Cryptography (RSA): Encryption uses modular exponentiation.
• Hashing (used in databases): Converts large numbers into smaller indices.

Real-World Use:

• Pathao’s ride-matching system uses modular arithmetic to assign drivers to nearby passengers efficiently.
• Ncell’s SIM card PINs are generated using modular operations for security.

5. Cryptography and Number Theory

Cryptography uses number theory to secure data:

1. Public-Key Cryptography (RSA):

   • Relies on the difficulty of factoring large primes.
   • Example: If $n=p\times q$ (where $p,q$ are primes), breaking RSA requires finding $p$ and $q$.

2. Hash Functions:

   • Use modular arithmetic to produce fixed-length outputs (e.g., SHA-256).

Real-World Example:

• eSewa’s transaction security uses RSA to encrypt payment details.
• NEPSE’s blockchain employs hashing to verify trades.

6. Divisibility Proofs

Theorem: If $a\mid b$ and $a\mid c$, then $a\mid (b+c)$. Proof: Since $a\mid b$, $b=a\cdot k_1$ for some integer $k_1$. Since $a\mid c$, $c=a\cdot k_2$ for some integer $k_2$. Thus, $b+c=a\cdot k_1+a\cdot k_2=a(k_1+k_2)$. Therefore, $a\mid (b+c)$.

Real-World Tie-In:

• Bank loan calculations: If a bank charges interest $a$ on two loans $b$ and $c$, the total repayment $b+c$ must also be divisible by $a$ for equal installments.

In the Real World

1. eSewa’s Transaction IDs:

   • Uses divisibility by 7 to validate 12-digit IDs (e.g., 123456789012 must satisfy $123456789012\mathrm{mod}7=0$).
   • Why? Ensures no typos slip through before processing.

2. Ncell’s Network Routing:

   • Applies LCM to synchronize signal transmissions across cell towers.
   • Example: If Tower A broadcasts every 6 seconds and Tower B every 9 seconds, the LCM (18 seconds) ensures they align.

3. Khalti’s Payment Deadlines:

   • Uses GCD to avoid overlapping transaction deadlines.
   • Example: If User A has a 12-hour window and User B has an 18-hour window, the GCD (6 hours) sets the minimum sync period.

4. NEPSE’s Stock Trading:

   • Employs prime-based hashing to secure trade logs.
   • Example: A trade ID like PRIME_7919 (where 7919 is a large prime) ensures uniqueness and tamper-proofing.

5. Pathao’s Driver-Passenger Matching:

   • Uses modular arithmetic to assign the nearest available driver.
   • Example: If a passenger requests a ride at location $x$, the system computes $x\mathrm{mod}5$ to find the closest driver zone.

Exam Tip

1. Memorize divisibility rules—they appear in short-answer questions.
2. Practice the Euclidean algorithm for GCD; it’s often tested in proofs.
3. Relate LCM/GCD to real systems (e.g., NTC scheduling, Khalti payments).
4. For proofs, always start with definitions (e.g., "Since $a\mid b$, $b=a\cdot k$").
5. Cryptography questions usually ask about RSA or hashing—link to eSewa/Ncell.
6. Watch for traps: In GCD/LCM problems, ensure numbers are co-prime before applying $\text{LCM}(a,b)=a\times b$.

Visuals:

graph TD
    A["Divisibility Rules"] --> B["2: Even last digit"]
    A --> C["3: Sum of digits divisible by 3"]
    A --> D["5: Ends with 0 or 5"]
    A --> E["11: Alternating sum divisible by 11"]

graph LR
    A["Prime Factorization"] --> B["48 = 2^4 × 3"]
    A --> C["18 = 2 × 3^2"]
    B & C --> D["GCD(48,18) = 2 × 3 = 6"]
    B & C --> E["LCM(48,18) = 2^4 × 3^2 = 144"]

stateDiagram-v2
    [*] --> IsPrime: Check if n > 1
    IsPrime --> Yes: If yes, check divisibility by primes ≤√n
    Yes --> NoDivisors: If no divisors, prime
    Yes --> HasDivisors: If divisors exist
    HasDivisors --> [*]: Not prime
    NoDivisors --> [*]: Prime

flowchart TD
    A["Euclidean Algorithm"] --> B["Compute 98 ÷ 56 = 1 R42"]
    B --> C["Now GCD(56, 42)"]
    C --> D["56 ÷ 42 = 1 R14"]
    D --> E["Now GCD(42, 14)"]
    E --> F["42 ÷ 14 = 3 R0"]
    F --> G["GCD = 14"]

pie
    title Modular Arithmetic in Cryptography
    "RSA Encryption" : 45
    "Hashing" : 35
    "Error Detection" : 20