Number system

Number System – Study Notes (AFCAT / IIT‑JEE)

Goal – To master the theory, tricks and computational strategies that appear in competitive exams.
Coverage – Integer & fractional representations, base conversions, arithmetic, negative‑number formats, divisibility tests, powers & roots, and key pitfalls.

Notation

• b – base of the system (b ≥ 2).
• n – number of digits or bits.
• x_b – the representation of a number in base b.
• ⌊·⌋ – floor, ⌈·⌉ – ceiling, ⌊·⌋! – factorial.
• 2^k – power of two, 10^k – power of ten, b^k – power of base b.

1. Representation of Numbers in Base b

Decimal value
[ x_b = \sum_{i=0}^{n-1} a_i , b^i ]

The digits a_i satisfy 0 ≤ a_i < b.
For bases > 10 we use alphabetic symbols: 10→A, 11→B, …, 15→F, etc.

2. Converting Between Bases

2.1 Decimal → Base b

Repeated division (long division algorithm)

1. Divide the decimal number N by b.
2. The remainder r_0 is the least significant digit.
3. Replace N by ⌊N/b⌋ and repeat until N = 0.
4. The digits read from last remainder to first give the representation.

Example
Convert 156 to base 5.

⇒ 156₁₀ = 1111₅.

2.2 Base b → Decimal

Use the positional formula: [ x_b = \sum_{i=0}^{n-1} a_i , b^i ]

Example
1011₂ → 1·2³ + 0·2² + 1·2¹ + 1·2⁰ = 8+0+2+1 = 11₁₀.

2.3 Base b_1 → Base b_2 (via Decimal)

1. Convert from b_1 to decimal.
2. Convert from decimal to b_2.
3. For large numbers, use the repeated multiplication method (see §2.3‑b).

2.3‑b Repeated Multiplication (direct base conversion)

Given x_b1 = a_{n-1} … a_1 a_0:

result = 0
for i = n-1 downto 0:
    result = result * b2 + a_i

At the end, result is the representation in base b2.

Proof:
After the k‑th iteration, result = a_{n-1} … a_{n-k} in base b2.
Multiplying by b2 shifts left by one place, adding a_{n-k} appends the next digit.
Finally, all digits are processed → correct conversion.

3. Arithmetic in Base b

3.1 Addition & Subtraction

• Use the usual column method.
• Carry occurs when the sum of digits ≥ b.
• Borrow occurs when subtracting a larger digit from a smaller one.

Example
111₂ + 110₁₀
Convert 110₁₀ = 110₂ → 111₂ + 110₂ = 1101₂.

3.2 Multiplication

• Schoolbook: Multiply each digit of the multiplier by the multiplicand, shift left by place value, sum.
• Shift‑Add (binary): Equivalent to adding