Unit 1: Number Theory-I

Number theory studies the integers ℤ = {…, −2, −1, 0, 1, 2, …} and the exact relationships between them; it is the arithmetic foundation on which modern cryptography (RSA, Diffie–Hellman) is built. This unit establishes divisibility, the residue structure modulo m, positional number systems, and the digit-by-digit algorithms a machine uses to add and multiply.

• Domain: all statements concern integers, not reals — remainders are exact, never rounded.
• Closure: ℤ is closed under addition, subtraction and multiplication, but not division (5 ÷ 2 ∉ ℤ).
• Order and sign: every nonzero integer is positive or negative; magnitude is written |a|.
• Positional principle: an integer's value depends on both the digit and its place, weighted by powers of a fixed base b.
• Notation: a | b reads "a divides b"; a mod m denotes the remainder; a ≡ b (mod m) denotes congruence.

II. Divisibility and the Division Algorithm

The exact-quotient relation and the theorem that pins down remainders.

A. Division

Divisibility is exact multiplicity: one integer fits into another a whole number of times.

• Definition: for integers a, b with a ≠ 0, a divides b (a | b) if there exists an integer c with b = ac. Then a is a factor of b and b a multiple of a.
• Example: 3 | 12 because 12 = 3·4; but 3 ∤ 7 since no integer c gives 7 = 3c.
• Basic properties: for all integers a, b, c:
  • Transitivity: if a | b and b | c then a | c.
  • Linearity: if a | b and a | c then a | (mb + nc) for any integers m, n.
  • Multiplicative: if a | b then a | bc for any integer c.
• Everything divides zero: a | 0 for every nonzero a, since 0 = a·0.

B. The Division Algorithm

The Division Algorithm guarantees a unique quotient and a bounded, non-negative remainder.

• Statement: for any integer a and positive integer d, there exist unique integers q and r with

a = dq + r,   0 ≤ r < d

• Symbols: a = dividend, d = divisor, q = quotient = a div d, r = remainder = a mod d.
• Key constraint: the remainder is always non-negative and strictly less than d, which forces uniqueness.
• Negative dividends: for a = −11, d = 3: −11 = 3·(−4) + 1, so q = −4, r = 1 — not q = −3, r = −2, because r must be ≥ 0.
• Divisibility link: d | a exactly when the remainder r = 0.

III. Modular Arithmetic

Working with integers under a fixed modulus, where only remainders matter.

A. Modular Arithmetic

Modular arithmetic collapses the integers into a finite set by identifying numbers that share a remainder.

• Congruence definition: a ≡ b (mod m) if m | (a − b), for a positive integer m (the modulus).
• Remainder form: a ≡ b (mod m) iff a mod m = b mod m — both leave the same remainder.
• Example: 17 ≡ 5 (mod 12) because 12 | (17 − 5) = 12; clock arithmetic uses m = 12.
• Equivalence relation: congruence mod m is reflexive, symmetric and transitive, partitioning ℤ into m residue classes [0], [1], …, [m−1].
• Cryptographic relevance: RSA computes c = mᵉ mod n, so all ciphertext lives in a fixed residue range.

B. Arithmetic Modulo m

Congruences can be added and multiplied like equations, giving a self-contained algebra on {0, 1, …, m−1}.

• Compatibility: if a ≡ b (mod m) and c ≡ d (mod m), then
  • Addition: a + c ≡ b + d (mod m)
  • Multiplication: ac ≡ bd (mod m)
• Defined operations: on ℤₘ = {0, …, m−1}:

a +ₘ b = (a + b) mod m
a ·ₘ b = (a · b) mod m

• Example (m = 7): 5 +₇ 4 = 9 mod 7 = 2; 5 ·₇ 4 = 20 mod 7 = 6.
• Reduce early: to compute 7·9 mod 5, replace with 2·4 = 8 ≡ 3 (mod 5) — keeping numbers small is the basis of efficient modular exponentiation.
• Caution: cancellation fails in general — 2·3 ≡ 2·0 (mod 6) does not give 3 ≡ 0.

IV. Representations of Integers

How a single integer is written in different positional bases.

A. Representations of Integers

Every positive integer has one and only one representation in a chosen base.

• Base-b theorem: for any base b > 1, each positive integer n is uniquely

n = aₖbᵏ + aₖ₋₁bᵏ⁻¹ + … + a₁b + a₀,   0 ≤ aᵢ < b,  aₖ ≠ 0

• Symbols: b = base/radix, aᵢ = digits, k = highest place index.
• Finding digits: repeatedly divide by b; the remainders, read bottom-up, are the digits.
• Example: 100 in base 8 → 100 = 8·12 + 4, 12 = 8·1 + 4, 1 = 8·0 + 1 → (144)₈.
• Common bases: decimal (10), binary (2), octal (8), hexadecimal (16).

B. Binary Expansions

Binary uses only 0 and 1, matching the two-state (on/off) hardware of computers.

• Digits: each bit is a coefficient of a power of 2.
• Example: (1011)₂ = 1·8 + 0·4 + 1·2 + 1·1 = 11.
• Decimal → binary: divide by 2, collect remainders. 19: 19→1, 9→1, 4→0, 2→0, 1→1 ⇒ (10011)₂.
• Place values: …, 16, 8, 4, 2, 1 — each bit doubles the weight of the one to its right.

C. Octal and Hexadecimal Expansions

Octal (base 8) and hexadecimal (base 16) compress long binary strings into fewer, human-readable digits.

• Octal digits: 0–7, coefficients of powers of 8. (345)₈ = 3·64 + 4·8 + 5 = 229.
• Hexadecimal digits: 0–9 then A–F, where A = 10, B = 11, C = 12, D = 13, E = 14, F = 15.
• Example (hex): (2AF)₁₆ = 2·256 + 10·16 + 15 = 687.
• Why they matter: 8 = 2³ and 16 = 2⁴, so each octal/hex digit maps cleanly onto a fixed block of bits.

D. Conversion Between Binary, Octal, and Hexadecimal Expansions

Because 8 and 16 are powers of 2, conversion is grouping of bits — no arithmetic through decimal is needed.

1. Binary ⇄ octal: group bits in threes from the right, each group → one octal digit.
   • Example: (11 010 111)₂ → groups 011, 010, 111 → (327)₈.
2. Binary ⇄ hexadecimal: group bits in fours from the right, each group → one hex digit.
   • Example: (1101 0111)₂ → 1101 = D, 0111 = 7 → (D7)₁₆.
   • Octal ⇄ hex: route through binary — expand each octal digit to 3 bits, regroup into 4-bit nibbles.
   • Padding: add leading zeros to complete the leftmost group before mapping.

V. Algorithms for Integer Operations

The digit-level procedures that implement arithmetic in any base.

A. Algorithms for Integer Operations

Machine arithmetic operates on base-2 (or base-b) digit strings, using carries and shifts rather than memorized tables.

• Representation: operands stored as digit arrays aₙ₋₁ … a₁ a₀ in a fixed base b.
• Cost measure: efficiency counts bit operations — single-digit adds or multiplies.
• Building blocks: two core routines, addition and multiplication, from which subtraction and division are derived.
• Base independence: the same carry-and-column logic works in binary, octal, or decimal by changing b.

B. Addition Algorithm

Addition proceeds right to left, summing aligned digits and propagating a carry.

• Procedure: given a = (aₙ₋₁…a₀)₂ and b = (bₙ₋₁…b₀)₂, set carry c = 0:

for j = 0 to n−1:
    sum = aⱼ + bⱼ + c
    sⱼ  = sum mod 2      # digit kept
    c   = sum div 2      # carry out
sₙ = c                   # final carry

• Symbols: sⱼ = result digit at position j, c = carry into next column.
• Example (binary): 1011 + 1101: column sums with carry give 11000 = 24 (i.e. 11 + 13).
• Complexity: n-bit addition uses O(n) bit operations — linear in the number of digits.

C. Multiplication Algorithm

Multiplication forms shifted partial products and adds them, mirroring long multiplication.

• Procedure: for each bit bⱼ of the multiplier, form a partial product a·bⱼ shifted left by j places, then sum all partials.

product = 0
for j = 0 to n−1:
    if bⱼ = 1:
        product = product + (a shifted left j bits)

• Shift = scaling: shifting a binary number left by j positions multiplies it by 2ʲ.
• Example (binary): 110 × 101 → partials 110 (j=0) and 11000 (j=2, since b₁ = 0 is skipped) → sum 11110 = 30 (i.e. 6 × 5).
• Complexity: n partial products each requiring an n-bit shift and add gives O(n²) bit operations, the schoolbook bound that fast algorithms later improve.