Number system

Number Systems – Advanced Study Notes

(Designed for the Tripura Patwari / Lekhpal Quantitative Aptitude Programme – MIT‑Level)

1. Motivation & Scope

• Why number systems matter:

  • Foundations of all arithmetic, algebra, and computer science.
  • Critical for quick mental math, engineering calculations, and algorithm design.

• What we cover:

  • Base‑(b) representation, conversion algorithms, proofs of uniqueness.
  • Operations in arbitrary bases.
  • Divisibility and modular arithmetic.
  • Edge cases (negative numbers, fractions, infinite expansions).
  • Advanced topics (mixed radix, balanced bases, Gray codes).

2. Formal Definition of Base‑(b) Representation

Let (b\in \mathbb{N}), (b\ge 2).
Every integer (N\in \mathbb{Z}) can be uniquely written as

[ N = \sum_{k=0}^{m-1} d_k,b^{k}, ]

where

• (d_k \in {0,1,\dots,b-1}) (digits).
• (d_{m-1}\neq 0) (unless (N=0)).
• (m) is the number of digits (the length of the representation).

Theorem 1 (Existence and Uniqueness)
For any integer (N) and base (b\ge2), there exists a unique tuple ((d_{m-1},\dots,d_0)) satisfying the above conditions.

Proof sketch: Use the Euclidean division algorithm repeatedly.

• Base case: (N) can be divided by (b) to give quotient (q) and remainder (r\in [0,b-1]).
• Induction: Apply to (q) until it becomes (0).
• Uniqueness follows because the remainders are fixed by the division algorithm. ∎

Notation

• ([d_{m-1}\dots d_0]_b) denotes the number (N).
• For example, ([1011]2 = 1\cdot2^3+0\cdot2^2+1\cdot2^1+1\cdot2^0=11{10}).

3. Converting Between Bases

3.1 Integer Part – Division‑by‑(b) Algorithm

Input: integer N ≥ 0, base b
Output: digits d_k
k ← 0
while N > 0:
    d_k ← N mod b
    N ← ⌊N / b⌋
    k ← k+1
return (d_{k-1}, …, d_0)

Proof of correctness: Each loop iteration extracts the least significant digit, which is the remainder of division by (b). The quotient becomes the new number to be processed. After (m) iterations we have produced all digits.

3.2 Fractional Part – Repeated Multiplication

For a rational fraction (0 < f < 1):

Input: fraction f, base b
Output: digits s_1, s_2, …
while f ≠ 0:
    f ← f * b
    s_i ← ⌊f⌋
    f ← f - s_i
    i ← i+1

The sequence (s_i) is the fractional part in base (b).
If the fraction has a finite expansion, the algorithm terminates after a finite number of steps; otherwise it produces an infinite periodic sequence (e.g., 1/3 in base 10 is 0.333…).

3.3 Edge Cases

4. Arithmetic in Base‑(b)

4.1 Addition & Subtraction

• Algorithm: Same as decimal, but carry/borrow base‑(b).
• Proof of correctness: Each digit pair plus carry is summed; the remainder modulo (b) is the result digit, the quotient (carry) is propagated.

4.2 Multiplication

• Long multiplication: multiply each digit of the multiplier by the multiplicand, shift by base powers.
• Karatsuba / FFT multiplication: efficient for very large numbers; complexity (O(n^{\log_2 3})) or (O(n\log n)).

4.3 Division

• Long division algorithm: subtract multiples of divisor from the dividend, using base‑(b) estimation.
• Newton‑Raphson for reciprocals: compute (1/d) in base‑(b) to arbitrary precision.

5. Number Theory in Base‑(b)

5.1 Divisibility Tests

| Base | Test | Explanation | |------|------|