Number System – Advanced Study Notes
(MIT‑style, first‑principles approach – suitable for Ladakh PSC Quantitative Aptitude)
1. Foundations of Positional Representation
| Symbol | Meaning | Example | General formula |
|---|---|---|---|
b |
Base (radix) | decimal → b = 10 |
|
dᵢ |
Digit at position i (0‑indexed from the right) |
345_10 → d₂=3, d₁=4, d₀=5 |
|
N |
Integer in base‑b |
N = Σ_{i=0}^{k} dᵢ b^i |
|
k |
Highest power of b present |
k = ⌊log_b N⌋ |
Theorem (Uniqueness).
For a given baseb ≥ 2, every non‑negative integerNhas a unique representation
N = Σ_{i=0}^{k} dᵢ b^iwith digits0 ≤ dᵢ < b.
Proof: By induction onk. Fork = 0, trivial. Assume uniqueness for all numbers< b^k. LetN < b^{k+1}. DivideNbyb:
N = q·b + r, 0 ≤ r < b.
By induction,qhas a unique representation with powers< b^k. ThusN’s representation is unique. ∎
2. Common Bases and Their Properties
| Base | Decimal value | Notation | Special Properties |
|---|---|---|---|
| 2 | Binary | b₂ |
b² = 4 → every even number ends in 0; odd in 1. |
| 3 | Ternary | b₃ |
Sum of digits ≡ N (mod 2). |
| 4 | Quaternary | b₄ |
Powers of 4 give sums of digits ≡ N (mod 3). |
| 5 | Quinary | b₅ |
Divisibility by 5 ⇔ last digit 0 or 5. |
| 8 | Octal | b₈ |
Octal representation is convenient for binary packing. |
| 10 | Decimal | b₁₀ |
Standard counting system. |
| 16 | Hexadecimal | b₁₆ |
b₁₆ = 2⁴. Hex digits 0–9, A–F. |
| 32 | Base‑32 | b₃₂ |
Useful in QR codes, base‑32 encoding. |
3. Conversion Algorithms
3.1 Decimal → Base‑b (Integer part)
while N > 0:
r = N mod b
prepend r to result
N = floor(N / b)
Complexity: O(log_b N).
3.2 Base‑b → Decimal
N = 0
for each digit d in representation:
N = N * b + d
3.3 Decimal Fraction → Base‑b (Fractional part)
frac = fractional part of N
while frac ≠ 0 and precision not reached:
frac = frac * b
digit = floor(frac)
append digit to result
frac = frac - digit
Edge case: Non‑terminating representation when b and denominator are not coprime (e.g., 1/3 in binary).
3.4 Base‑b Fraction → Decimal
frac = 0
for i from 1 to length:
digit = representation[i]
frac += digit / (b^i)
4. Arithmetic in Non‑Decimal Bases
4.1 Addition
Same as decimal, but carry threshold is b. Example (Base‑8):
345₈
+ 167₈
-------
546₈
Because 5+7=12₈ → write 2, carry 1.
4.2 Multiplication
Use partial products or shift‑and‑add. In binary, multiplication by 2^k is a left shift.
4.3 Division
Long division works with base b. Remainder < b.
4.4 Modulo Properties
a ≡ b (mod m) iff a and b have the same remainder when divided by m.
Useful for divisibility tests in any base:
| Base | Divisibility Rule |
|---|---|
| 2 | Last digit even |
| 3 | Sum of digits mod 3 |
| 4 | Last two digits mod 4 |
| 5 | Last digit 0 or 5 |
| 8 | Last three digits mod 8 |
| 16 | Last two hex digits mod 16 |
5. Advanced Topics
5.1 Mixed‑Radix Systems
- Time: 1h = 60 min, 1 min = 60 s → base 60 at each level.
- Calendar: 12 months, 30 days, 24 hours → a mixed base system.
Conversion: Treat each level as a digit in a base that is the product of all lower bases.
5.2 Gray Code (Binary Reflected Gray Code)
- Sequence where successive numbers differ by one bit.
- Useful for error detection in digital signals.
Construction:
- Start with
0and1. - Reflect list and prefix
0to first half,1to second half.
5.3 Negative Bases
- Base
-2representation can encode all integers without a sign. - Rule: For
N, repeatedly divide by-2, recording remainders0or1.
**Example