Unit 1: Number Theory-I

1. The Integers and Divisibility

Number theory forms the mathematical cornerstone of modern cryptography, public-key encryption, and hashing algorithms. The domain of study is the set of integers $\mathbb{Z} = \{..., -2, -1, 0, 1, 2, ...\}$.

1.1 Definition of Divisibility

Let $a, b \in \mathbb{Z}$ with $a \neq 0$. We say that $a$ divides $b$ (written as $a \mid b$) if there exists an integer $c \in \mathbb{Z}$ such that:
$b = a \cdot c$

• If $a$ divides $b$, then $a$ is called a factor or divisor of $b$, and $b$ is called a multiple of $a$.
• If $a$ does not divide $b$, we write $a \nmid b$.
• Example: $3 \mid 12$ because $12 = 3 \times 4$. Conversely, $5 \nmid 12$ because no integer $c$ satisfies $12 = 5c$.

1.2 Fundamental Properties of Divisibility

For all integers $a, b, c \in \mathbb{Z}$:

2. The Division Algorithm

Despite its historical name, the Division Algorithm is a foundational theorem that guarantees the existence and uniqueness of quotients and remainders.

2.1 Formal Statement

Let $a \in \mathbb{Z}$ (the dividend) and $d \in \mathbb{Z}^+$ (a positive integer divisor). Then there exist unique integers $q$ (the quotient) and $r$ (the remainder) such that:

$a = d \cdot q + r \quad \text{where} \quad 0 \le r < d$

• $q = \lfloor a / d \rfloor = a \operatorname{div} d$
• $r = a - d \cdot q = a \bmod d$

CODECopy Code
Dividend (a)  =  Divisor (d) * Quotient (q)  +  Remainder (r)
                 [-------------------------]    [-----------]
                       Multiple of d             0 <= r < d

2.2 The Strict Constraint on the Remainder

The remainder $r$ must strictly satisfy $0 \le r < d$. It can never be negative, and it must be strictly less than the divisor.

2.3 Division with Negative Dividends

When $a$ is negative, careful application of $0 \le r < d$ is mandatory:

• Example 1: Divide $a = -23$ by $d = 5$.
  $-23 = 5 \cdot (-5) + 2$
  Here, $q = -5$ and $r = 2$. Note that writing $-23 = 5 \cdot (-4) - 3$ is mathematically invalid under the Division Algorithm because $r = -3 < 0$.
• Example 2: Divide $a = -11$ by $d = 4$.
  $-11 = 4 \cdot (-3) + 1 \implies q = -3, r = 1$

3. Modular Arithmetic and Congruence

Modular arithmetic studies the arithmetic of remainders, forming the bedrock of cryptographic ciphers like RSA and Diffie-Hellman.

3.1 Definition of Congruence

Let $m \in \mathbb{Z}^+$ be a positive integer called the modulus. Two integers $a$ and $b$ are said to be congruent modulo $m$ (written $a \equiv b \pmod m$) if $m$ divides their difference:

$a \equiv b \pmod m \iff m \mid (a - b)$

Equivalent Characterization:
$a \equiv b \pmod m$ if and only if $a$ and $b$ leave the exact same remainder when divided by $m$:
$a \bmod m = b \bmod m$

Examples:

• $17 \equiv 5 \pmod 6$ because $17 - 5 = 12$, and $6 \mid 12$.
• $28 \equiv -2 \pmod{10}$ because $28 - (-2) = 30$, and $10 \mid 30$.

3.2 Equivalence Relation and Residue Classes

Congruence modulo $m$ is an equivalence relation satisfying:

1. Reflexive: $a \equiv a \pmod m$ since $m \mid 0$.
2. Symmetric: If $a \equiv b \pmod m$, then $b \equiv a \pmod m$.
3. Transitive: If $a \equiv b \pmod m$ and $b \equiv c \pmod m$, then $a \equiv c \pmod m$.

It partitions $\mathbb{Z}$ into exactly $m$ disjoint residue classes modulo $m$:
$\mathbb{Z}_m = \{[0], [1], [2], ..., [m - 1]\}$
Where each class $[r] = \{km + r \mid k \in \mathbb{Z}\}$ represents all integers leaving remainder $r$ when divided by $m$.

3.3 Algebraic Compatibility with Addition and Multiplication

If $a \equiv b \pmod m$ and $c \equiv d \pmod m$, then:

1. Addition Compatibility:
   $a + c \equiv b + d \pmod m$
2. Multiplication Compatibility:
   $a \cdot c \equiv b \cdot d \pmod m$
3. Exponentiation Compatibility:
   $a^k \equiv b^k \pmod m \quad \text{for any positive integer } k$

3.4 Failure of General Cancellation

Unlike standard arithmetic over $\mathbb{R}$, cancellation does not hold generally in modular arithmetic:
$ac \equiv bc \pmod m \quad \not\!\implies \quad a \equiv b \pmod m$

Counterexample: $2 \cdot 4 \equiv 2 \cdot 1 \pmod 6$ (since $8 \equiv 2 \pmod 6$), but canceling the $2$ gives $4 \equiv 1 \pmod 6$, which is false!

The Correct Cancellation Rule:
$ac \equiv bc \pmod m \iff a \equiv b \pmod{\frac{m}{\gcd(c, m)}}$
If $\gcd(c, m) = 1$ (i.e., $c$ and $m$ are coprime), then $c$ can be cancelled safely:
$ac \equiv bc \pmod m \implies a \equiv b \pmod m \quad (\text{provided } \gcd(c, m) = 1)$

4. Representations of Integers and Base Expansions

4.1 Base-$b$ Expansion Theorem

Let $b$ be an integer greater than 1 (the base or radix). Any positive integer $n$ can be uniquely expressed in the base-$b$ positional system as:

$n = a_k b^k + a_{k-1} b^{k-1} + ... + a_1 b + a_0$

Where:

• $k$ is a non-negative integer.
• Each digit $a_i$ satisfies $0 \le a_i < b$.
• The leading coefficient $a_k \neq 0$.
• Notation: $n = (a_k a_{k-1} ... a_1 a_0)_b$.

4.2 Algorithm for Base Conversion

To convert a decimal integer $n$ to base $b$:

1. Divide $n$ by $b$ to get quotient $q_0$ and remainder $a_0 = n \bmod b$.
2. Divide $q_0$ by $b$ to get $q_1$ and remainder $a_1$.
3. Repeat until quotient becomes $0$. The remainders read in reverse order (bottom-up) form the base-$b$ representation.

4.3 Common Cryptographic Number Bases

Hexadecimal letter values: $A = 10, B = 11, C = 12, D = 13, E = 14, F = 15$.

4.4 Fast Conversion Shortcuts: Binary $\leftrightarrow$ Octal $\leftrightarrow$ Hexadecimal

Because $8 = 2^3$ and $16 = 2^4$, conversion between binary and octal/hexadecimal requires zero arithmetic:

• Binary to Octal: Partition binary bits into groups of 3 bits starting from the right (pad with leading zeros on left if needed), then replace each 3-bit group with its octal digit.
  • $(11010111)_2 \rightarrow (011)(010)(111)_2 = (327)_8$.
• Binary to Hexadecimal: Partition binary bits into groups of 4 bits starting from the right, then replace each 4-bit group with its hexadecimal character.
  • $(11010111)_2 \rightarrow (1101)(0111)_2 = (D7)_{16}$.
• Hexadecimal to Binary: Expand each hex digit into its corresponding 4-bit nibble.
  • $(2AF)_{16} = (0010)(1010)(1111)_2 = (1010101111)_2$.

5. Modular Exponentiation and Fast Algorithms

In modern cryptosystems (such as RSA $c = m^e \bmod n$ and Diffie-Hellman $A = g^a \bmod p$), numbers often have 2048 or 4096 bits. Calculating $a^b$ directly produces astronomical numbers exceeding the atoms in the observable universe.

5.1 Square-and-Multiply (Repeated Squaring) Algorithm

To compute $a^b \bmod m$ efficiently:

1. Express the exponent $b$ in binary form: $b = (b_k b_{k-1} ... b_1 b_0)_2$.
2. Initialize result $x = 1$ and base power $P = a \bmod m$.
3. For each bit from $i = 0$ to $k$:
   • If bit $b_i = 1$, update $x = (x \cdot P) \bmod m$.
   • Square the base power: $P = (P \cdot P) \bmod m$.
4. Return $x$.

Time Complexity: Requires at most $2 \log_2 b$ modular multiplications ($O(\log b)$ runtime), making computations feasible in milliseconds even for 4096-bit exponents.

Common Pitfalls & Anti-Patterns

1. Negative Remainders: Writing $-15 = 4 \cdot (-3) - 3$ instead of $-15 = 4 \cdot (-4) + 1$. The remainder must strictly satisfy $0 \le r < d$.
2. Illegal Cancellation in Modulo: Assuming $4x \equiv 4y \pmod{12} \implies x \equiv y \pmod{12}$. In truth, $\gcd(4, 12) = 4$, so $x \equiv y \pmod 3$.
3. Misgrouping Bits for Base Conversion: Grouping from left to right instead of right to left when converting binary to octal or hex causes catastrophic padding errors.
4. Dividing in Modular Arithmetic: Division by $a$ is undefined unless an explicit modular multiplicative inverse $a^{-1} \pmod m$ exists (which requires $\gcd(a, m) = 1$).

Exam Tips & High-Yield Formulas

• Division Algorithm: $a = dq + r$, with $0 \le r < d$.
• Congruence: $a \equiv b \pmod m \iff m \mid (a - b) \iff a \bmod m = b \bmod m$.
• Cancellation Rule: $ac \equiv bc \pmod m \iff a \equiv b \pmod{\frac{m}{\gcd(c, m)}}$.
• Base Groupings: Binary to Octal = groups of 3 bits; Binary to Hex = groups of 4 bits (grouped from right to left).
• Linearity: If $a \mid b$ and $a \mid c$, then $a \mid (mb + nc)$ for any integers $m, n$.

Quick Revision Summary

• Divisibility: $a \mid b$ requires $b = ac$. Divisibility is reflexive, transitive, and linear.
• Division Algorithm: Uniquely breaks any integer $a$ into $dq + r$ with strictly non-negative remainder $0 \le r < d$.
• Modulo System: Partitions integers into $m$ equivalence classes. Addition and multiplication are preserved; cancellation requires coprimality.
• Base Expansions: Encodes integers into radix $b$. Powers of 2 ($2^3=8, 2^4=16$) permit direct 3-bit and 4-bit regrouping.
• Fast Exponentiation: Square-and-multiply evaluates $a^b \bmod m$ in logarithmic time $O(\log b)$ by exploiting binary expansion.