Number Theory: Divisibility, Primes, Congruences & Cryptography

Key Concepts and Definitions

Divisibility and Divisors

Definition: An integer $a$ is divisible by an integer $b$ (where $b\ne 0$) if there exists an integer $k$ such that $a=b\cdot k$. We write this as $b\mid a$.

Example: $15$ is divisible by $3$ because $15=3\times 5$. Here, $3\mid 15$.

Divisors of a Number: The integers $d$ such that $d\mid n$ are called divisors of $n$. For example, the divisors of $12$ are $\{-12,-6,-4,-3,-2,-1,1,2,3,4,6,12\}$.

Prime Numbers

Definition: A prime number is a natural number greater than $1$ that has no positive divisors other than $1$ and itself.

Example: $7$ is prime because its only divisors are $1$ and $7$. $4$ is not prime because it is divisible by $2$.

Fundamental Theorem of Arithmetic: Every integer greater than $1$ can be represented uniquely as a product of prime numbers, up to the order of the factors.

Example: $210=2\times 3\times 5\times 7$.

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

GCD: The greatest common divisor of two integers $a$ and $b$ is the largest integer that divides both $a$ and $b$. It is denoted by $\gcd (a,b)$.

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

LCM: The least common multiple of two integers $a$ and $b$ is the smallest positive integer that is divisible by both $a$ and $b$. It is denoted by $\text{lcm}(a,b)$.

Example: $\text{lcm}(4,6)=12$.

Relationship Between GCD and LCM: $$\gcd (a,b)\times \text{lcm}(a,b)=a\times b$$

Modular Arithmetic

Definition: For integers $a$ and $b$ (with $b>0$), $a$ modulo $b$ is the remainder when $a$ is divided by $b$. It is denoted by $a\mathrm{mod}b$.

Example: $17\mathrm{mod}5=2$ because $17=3\times 5+2$.

Congruence: Two integers $a$ and $b$ are congruent modulo $m$ if $m\mid (a-b)$. We write this as $a\equiv b(\mathrm{mod}m)$.

Example: $17\equiv 2(\mathrm{mod}5)$ because $5\mid (17-2)$.

Euclidean Algorithm

The Euclidean algorithm is an efficient method to compute the GCD of two numbers. It is based on the principle that $\gcd (a,b)=\gcd (b,a\mathrm{mod}b)$.

Example: Compute $\gcd (48,18)$:

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

Applications in Cryptography

Number theory is foundational in cryptography, particularly in public-key cryptosystems like RSA. RSA relies on the difficulty of factoring large integers into primes and properties of modular arithmetic.

In the Real World

1. eSewa and Khalti: Secure Transactions

Both eSewa and Khalti use cryptographic algorithms based on number theory to secure transactions. When you transfer money or pay bills, the system uses modular arithmetic to encrypt your data, ensuring that only the intended recipient can decode it. For example, when you send money to a friend, the transaction ID and amount are hashed using a one-way function (often involving modular arithmetic) to create a unique fingerprint. This ensures that the transaction cannot be altered or forged.

2. Ncell and NTC: Error Detection in Data Transmission

Ncell and NTC use checksums and cyclic redundancy checks (CRC) to detect errors in data transmission. These techniques rely on modular arithmetic to verify the integrity of transmitted data. For instance, when you send an SMS or make a call, the data is divided into packets, and each packet is checked using a polynomial division in modular arithmetic. If the checksum does not match, the data is retransmitted, ensuring error-free communication.

3. NEPSE: Stock Market Index Calculations

The Nepal Stock Exchange (NEPSE) uses divisibility and GCD concepts to adjust stock indices. For example, when a company splits its shares (e.g., a 1:2 split), the total number of shares doubles, but the total market capitalization remains the same. To adjust the index, NEPSE uses divisibility rules to ensure the index reflects the actual value of the market accurately.

Visualizing Key Concepts

Divisibility and Prime Factorization

This diagram shows the prime factorization of 12, where the final box represents the unique product of primes.

Euclidean Algorithm Steps

flowchart TD
    A["Start with 48 and 18"] --> B["48 = 2 × 18 + 12"]
    B --> C["Now find gcd(18, 12)"]
    C --> D["18 = 1 × 12 + 6"]
    D --> E["Now find gcd(12, 6)"]
    E --> F["12 = 2 × 6 + 0"]
    F --> G["gcd is 6"]

This flowchart traces the steps of the Euclidean algorithm to find $\gcd (48,18)$.

Modular Arithmetic Example

Consider $23\mathrm{mod}5$:

• Divide 23 by 5: quotient = 4, remainder = 3.
• Thus, $23\equiv 3(\mathrm{mod}5)$.

Worked Examples

Example 1: Divisibility and GCD

Problem: Find $\gcd (56,98)$ using the Euclidean algorithm.

Solution:

1. $98=1\times 56+42$
2. $56=1\times 42+14$
3. $42=3\times 14+0$ Thus, $\gcd (56,98)=14$.

Real-world tie-in: Imagine a bank like Nabil Bank processing loan repayments. If two loan amounts are 56,000 and 98,000, the GCD helps determine the largest possible equal installment that can be used for both loans without leaving a remainder.

Example 2: Congruence and Cryptography

Problem: Solve for $x$ in the congruence $3x\equiv 6(\mathrm{mod}9)$.

Solution:

1. Rewrite the congruence: $3x-6$ is divisible by 9.
2. Simplify: $3(x-2)\equiv 0(\mathrm{mod}9)$.
3. Divide by the GCD of 3 and 9, which is 3: $x-2\equiv 0(\mathrm{mod}3)$.
4. Thus, $x\equiv 2(\mathrm{mod}3)$.
5. The solutions are $x=2,5,8,11,\dots$.

Real-world tie-in: In RSA encryption, solving such congruences helps decrypt messages. For example, if Pathao uses a public key to encrypt a delivery confirmation code, the recipient (the delivery person) uses their private key (derived from modular arithmetic) to decode it.

Comparison Table: GCD vs. LCM

Advantages and Disadvantages

Divisibility Rules

Advantages:

• Quickly determine if a number is divisible by another without performing full division.
• Useful in simplifying fractions and solving equations.

Disadvantages:

• Rules are limited to specific divisors (e.g., 2, 3, 5, 9).
• Not applicable to all numbers or operations.

Prime Numbers

Advantages:

• Fundamental in cryptography (e.g., RSA encryption).
• Used in generating unique identifiers (e.g., serial numbers).

Disadvantages:

• Testing primality for very large numbers is computationally intensive.
• No known simple formula to generate primes.

Modular Arithmetic

Advantages:

• Efficient in computer science (e.g., hashing, error detection).
• Forms the basis of many cryptographic protocols.

Disadvantages:

• Can be abstract and difficult to visualize for beginners.
• Misapplication can lead to incorrect results in algorithms.

Exam Tip

For exams, focus on:

1. Definitions: Know the precise definitions of divisibility, primes, GCD, LCM, and congruence.
2. Algorithms: Be able to apply the Euclidean algorithm to find GCDs and solve congruences.
3. Proofs: Practice proving properties using mathematical induction or contradiction.
4. Applications: Understand how these concepts apply to real-world scenarios like cryptography, error detection, and financial calculations.
5. Visualization: Draw diagrams for prime factorization, Euclidean steps, and modular arithmetic to aid understanding.

Common Pitfalls:

• Misapplying divisibility rules (e.g., confusing divisibility by 2 and 3).
• Forgetting to consider negative divisors when listing all divisors of a number.
• Incorrectly solving congruences by not simplifying properly.