math.wiki
Logic, proof and discrete math › Introductory number theory › Numbers in other bases
Open on the map
Discrete Mathematics and Proof

Numbers in other bases

Ten is only one choice of base. Does every positive integer have a numeral in base seven or base two, and could one number ever have two different numerals?

You need
The division algorithmDiscrete Mathematics and ProofEvaluating expressions and formulasMath 6Place valueGrades 1 to 5
Where you are 8 in Introductory number theory
Logic, proof and discrete math6
Introductory number theory8
▴ 1 aboveModular arithmetic7The division algorithm
Numbers in other bases
The Euclidean algorithm and coprime numbersBezout's identity and the extended Euclidean algorithm▾ Show all 8 (2 more)

When you reach for it

Numbers in other bases bundled straws in fives and in twos: a digit counts how many of a place, and each place is worth b of the place to its right. This lesson states that as a theorem and proves it: every positive integer has a base-b numeral, and only one.

Reach for it to read or write a number in another base (binary and base sixteen in computing), and when a proof works with a number through its digits.

The procedure

Digits and expansions. Fix an integer b \ge 2, the base. The base-b digits are the integers 0, 1, \dots, b - 1; above base ten, letters stand in for digits from ten up, so base sixteen uses \mathrm{A} = 10 through \mathrm{F} = 15. For digits d_0, \dots, d_k, write

\begin{aligned}(d_k d_{k-1} \cdots d_1 d_0)_b &= d_k b^k + d_{k-1} b^{k-1} + \cdots + d_1 b + d_0 \\ &= \sum_{i=0}^{k} d_i b^i.\end{aligned}

The digit d_i sits in the b^i place. The string is a base-b expansion of n when its value is n and its leading digit d_k is not 0. A numeral with no subscript is in base ten.

The theorem. Let b \ge 2 be an integer. Every positive integer n has exactly one base-b expansion: exactly one k \ge 0 and one list of digits d_0, \dots, d_k in \{0, 1, \dots, b - 1\} with d_k \ne 0 and n = \sum_{i=0}^{k} d_i b^i.

The proof rests on The division algorithm, used here and proved in its own lesson: for integers a \ge 0 and b \ge 1 there is exactly one pair of integers q, r with a = qb + r and 0 \le r < b. If k \ge 1, factoring b out of every term but the last (the distributive property) gives

(d_k \cdots d_1 d_0)_b = (d_k \cdots d_1)_b \cdot b + d_0.

Since 0 \le d_0 < b, this is a division of n by b: the last digit is the remainder, and deleting it leaves the quotient.

Proof of existence. We use Strong induction and well-ordering on n. If 1 \le n \le b - 1, then n is itself a nonzero digit and n = (n)_b. Now let n \ge b and assume every m with 1 \le m < n has a base-b expansion. Divide: n = qb + r with 0 \le r < b. Then q \ge 1, since q = 0 would give n = r < b; and q < n, since n \ge qb \ge 2q > q. So q has an expansion (c_m \cdots c_0)_b with c_m \ne 0, and

\begin{aligned} n = qb + r &= c_m b^{m+1} + \cdots + c_0 b + r \\ &= (c_m \cdots c_0 \, r)_b,\end{aligned}

an expansion of n with leading digit c_m \ne 0. \square

Proof of uniqueness. Again by strong induction on n; the case n < b uses no hypothesis, so it is the base case. A string of two or more digits is worth at least d_k b^k \ge b, so when n < b every expansion of n is the single digit n. Now let n \ge b, assume each m with 1 \le m < n has only one expansion, and let (d_k \cdots d_0)_b and (e_j \cdots e_0)_b both be expansions of n. Both have k, j \ge 1, so

\begin{aligned} n &= (d_k \cdots d_1)_b \cdot b + d_0 \\ &= (e_j \cdots e_1)_b \cdot b + e_0,\end{aligned}

with both remainders in \{0, \dots, b - 1\}. Uniqueness in the division algorithm gives d_0 = e_0 and (d_k \cdots d_1)_b = (e_j \cdots e_1)_b = q, with 1 \le q < n as before. Both strings have nonzero leading digits, so they are expansions of q, and by the hypothesis they are the same string: k = j and d_i = e_i for every i. \square

Base b to base ten. The definition is itself a method: multiply each digit by its place value and add. Applying the displayed fact to (d_k \cdots d_1)_b, then to (d_k \cdots d_2)_b, and so on, nests it into Horner’s form, which needs no powers:

\begin{aligned}&(d_k \cdots d_0)_b \\ &= \Bigl(\cdots\bigl((d_k b + d_{k-1})\,b + d_{k-2}\bigr)\,b + \cdots\Bigr)\,b + d_0.\end{aligned}

Start with d_k; for each next digit, multiply the running total by b and add the digit. Each running total is the value of the digits read so far.

Base ten to base b. The existence proof is the method. Divide n by b: the remainder is d_0. Divide the quotient by b: the remainder is d_1. Continue until the quotient is 0, which happens because the quotients strictly decrease, and read the remainders from last to first. Uniqueness makes the result the base-b numeral. Each division undoes one Horner step.

The number of digits. If n has k + 1 digits in base b, then d_k \ge 1 gives n \ge b^k, and every digit at most b - 1 gives

\begin{aligned} n &\le (b - 1)(b^k + \cdots + b + 1) \\ &= (b^{k+1} + \cdots + b) - (b^k + \cdots + 1) = b^{k+1} - 1.\end{aligned}

So n has exactly k + 1 digits when b^k \le n < b^{k+1}: the number of digits is the number of powers b^0, b^1, \dots at most n, which is \lfloor \log_b n \rfloor + 1 (Evaluating logarithms, common and natural).

Bases 2, 8 and 16. Since 8 = 2^3 and 16 = 2^4, binary converts to base eight in blocks of three digits and to base sixteen in blocks of four, counted from the right, padding the last block with zeros on the left. Why, for any base b and block length m: let B_j = (d_{mj+m-1} \cdots d_{mj})_b be the jth block from the right. Regrouping the sum by blocks (associative and commutative properties) and using b^{mj+i} = (b^m)^j \, b^i,

n = \sum_{i} d_i b^i = \sum_{j} B_j \,(b^m)^j.

By the bound just proved, 0 \le B_j \le b^m - 1, so each block is a base-b^m digit, and the leftmost is nonzero. This is a base-b^m expansion of n, so by uniqueness it is the one.

Last digits and divisibility. Splitting off the last j digits the same way gives n = Q b^j + t with Q = (d_k \cdots d_j)_b and t = (d_{j-1} \cdots d_0)_b. If m \mid b^j, then m \mid Q b^j, so m \mid t gives m \mid n, and m \mid n gives m \mid n - Qb^j = t (Proving statements about divisibility). So m \mid n exactly when m divides the number formed by the last j digits. With j = 1: in an even base, n is even exactly when its last digit is.

Worked examples

Example 1

Base seven to base ten, two ways

Find the base-ten value of (2516)_7, first by place values and then by Horner’s form.

Solution

The places, from the right, are worth 7^0 = 1, 7^1 = 7, 7^2 = 49 and 7^3 = 343.

7^{3}
 2 343 686
7^{2}
 5 49 245
7^{1}
 1 7 7
7^{0}
 6 1 6 place digit value product sum 944
Figure 1Each digit of (2516)_7 times the value of its place. The four products add to 944.
\begin{aligned}(2516)_7 &= 2 \cdot 343 + 5 \cdot 49 + 1 \cdot 7 + 6 \\ &= 686 + 245 + 7 + 6 = 944.\end{aligned}

By Horner’s form, start with the leading digit 2 and, for each next digit, multiply by 7 and add: 2 \cdot 7 + 5 = 19, then 19 \cdot 7 + 1 = 134, then 134 \cdot 7 + 6 = 944. The running totals are values of the leading digits: 19 = (25)_7 and 134 = (251)_7.

Example 2

Base ten to base seven, and to base five

Write 944 in base 7 and in base 5.

Solution

Divide by 7 repeatedly, keeping each remainder:

divisionquotientremainder
944 = 134 \cdot 7 + 61346
134 = 19 \cdot 7 + 1191
19 = 2 \cdot 7 + 525
2 = 0 \cdot 7 + 202

The first remainder is the ones digit, so reading the remainders from the bottom up gives 944 = (2516)_7. The quotients 134, 19, 2 are Example 1’s running totals in reverse.

In base 5: 944 = 188 \cdot 5 + 4, 188 = 37 \cdot 5 + 3, 37 = 7 \cdot 5 + 2, 7 = 1 \cdot 5 + 2 and 1 = 0 \cdot 5 + 1, so 944 = (12234)_5. Check: 625 + 2 \cdot 125 + 2 \cdot 25 + 3 \cdot 5 + 4 = 944.

Example 3

One number in bases 2, 8 and 16

Write 429 in base 2, then use blocks to write it in base 8 and base 16.

Solution

Halving repeatedly: 429 = 214 \cdot 2 + 1, 214 = 107 \cdot 2 + 0, 107 = 53 \cdot 2 + 1, 53 = 26 \cdot 2 + 1, 26 = 13 \cdot 2 + 0, 13 = 6 \cdot 2 + 1, 6 = 3 \cdot 2 + 0, 3 = 1 \cdot 2 + 1, 1 = 0 \cdot 2 + 1. From the bottom up, 429 = (110101101)_2.

1 1 0 1 0 1 1 0 1 1 A D 6 5 5 base 16 base 2 base 8
Figure 2The binary digits of 429 grouped from the right. Blocks of four give (\mathrm{1AD})_{16}; blocks of three give (655)_8.

Blocks of three from the right are 110, 101, 101, worth 6, 5, 5, so 429 = (655)_8. Blocks of four are 1, 1010, 1101, worth 1, 10, 13, so 429 = (\mathrm{1AD})_{16}. Check: 6 \cdot 64 + 5 \cdot 8 + 5 = 429 and 256 + 10 \cdot 16 + 13 = 429.

Example 4

Base sixteen to base eight without base ten

Write (\mathrm{B7E})_{16} in base 8.

Solution

Neither base is a power of the other, but both are powers of 2, so pass through binary. Each base-sixteen digit becomes exactly four binary digits, inside zeros kept: \mathrm{B} = (1011)_2, 7 = (0111)_2 and \mathrm{E} = (1110)_2. So (\mathrm{B7E})_{16} = (101101111110)_2. Regroup in threes from the right: 101, 101, 111, 110, which are 5, 5, 7, 6. Hence (\mathrm{B7E})_{16} = (5576)_8.

Check: 11 \cdot 256 + 7 \cdot 16 + 14 = 2942 and 5 \cdot 512 + 5 \cdot 64 + 7 \cdot 8 + 6 = 2942.

Example 5

Counting digits without converting

How many digits does 1{,}000{,}000 have in base 2, and in base 16?

Solution

The count is k + 1 for the k with b^k \le n < b^{k+1}. In base 2, 2^{19} = 524{,}288 \le 1{,}000{,}000 < 2^{20} = 1{,}048{,}576, so there are 20 binary digits. In base 16, 16^4 = 65{,}536 \le 1{,}000{,}000 < 16^5 = 1{,}048{,}576, so there are 5 digits.

These agree: 20 binary digits make 5 blocks of four. Indeed 1{,}000{,}000 = (\mathrm{F4240})_{16}.

Example 6

Divisibility read off the last digits

Without finding its value, decide which of 2, 3, 4, 8, 9 divide n = (34052)_6.

Solution

Since 2 \mid 6 and 3 \mid 6, the last digit decides: 2 \mid 2, so 2 \mid n; and 3 \nmid 2, so 3 \nmid n. Since 4 and 9 divide 36 = 6^2, the last two digits decide, and (52)_6 = 32. So 4 \mid n because 4 \mid 32, and 9 \nmid n because 9 \nmid 32. Finally 8 \nmid 36 but 8 \mid 216 = 6^3, so use three digits: (052)_6 = 32, so 8 \mid n.

Check: n = 3 \cdot 1296 + 4 \cdot 216 + 5 \cdot 6 + 2 = 4784, and 4784 = 8 \cdot 598 = 3 \cdot 1594 + 2 = 9 \cdot 531 + 5.

Example 7

Weighing with powers of two

Vusi has a pan balance and seven weights of 1, 2, 4, 8, 16, 32 and 64 grams, one of each. The object goes on one pan and the chosen weights on the other. Prove that every whole number of grams from 1 to 127 can be balanced in exactly one way, and find the weights for 89 grams.

Solution

Record a choice of weights as digits: d_i = 1 if 2^i is chosen, d_i = 0 if not. The total is \sum d_i 2^i, and if the largest chosen weight is 2^k, then (d_k \cdots d_0)_2 is a binary expansion of the total. So a choice balancing n grams is the same thing as a binary expansion of n with at most seven digits.

Existence. By the theorem, n has a binary expansion, and n \le 127 < 2^7 means it has at most seven digits. (Strong induction and well-ordering proved this half on its own.)

Uniqueness. Two different choices balancing n would be two different binary expansions of n, which the theorem rules out. \square

For 89: 89 = 44 \cdot 2 + 1, 44 = 22 \cdot 2 + 0, 22 = 11 \cdot 2 + 0, 11 = 5 \cdot 2 + 1, 5 = 2 \cdot 2 + 1, 2 = 1 \cdot 2 + 0, 1 = 0 \cdot 2 + 1, so 89 = (1011001)_2 and Vusi uses 64 + 16 + 8 + 1.

Boundaries

  • The base is an integer b \ge 2. With b = 1 the only digit is 0 and every string is worth 0.
  • Digits lie in \{0, \dots, b - 1\}. The proof used 0 \le d_0 < b to call d_0 the remainder; with a digit 7 allowed in base 7, (17)_7 would be 14 = (20)_7.
  • The leading digit is nonzero. (0516)_7 and (516)_7 are the same number, which is also why padding a block is harmless.
  • The theorem is about positive integers. Zero is written (0)_b by agreement; a negative integer is - the expansion of its absolute value. Digits after a point (Terminating and repeating decimals) are a separate story.
  • Blocks work only between powers of one base: 2 with 8 or 16, 3 with 9. Since 16 is not a power of 10, base ten to sixteen goes by division.
  • The last-digit test needs m \mid b^j. In base 7, (13)_7 = 10 and (23)_7 = 17 share a last digit and differ in parity, because no power of 7 is even.

Where this goes next

The last digit, the remainder on division by b, is the central object of Modular arithmetic, and Congruence modulo n and its arithmetic gives it a symbol. With it, Where the divisibility tests come from proves the digit-sum tests (by 3 and 9 in base ten) that the last-digit argument cannot reach. Repeated division returns in the The Euclidean algorithm and coprime numbers, and the shape of this theorem, existence plus uniqueness, in the fundamental-theorem-of-arithmetic.

Exercises

Base b to base ten

  1. Write (3241)_5 in base ten.
  2. Write (110011)_2 in base ten.
  3. Write (7061)_8 in base ten.
  4. Write (\mathrm{2FA})_{16} in base ten.
  5. Use Horner’s form to write (12021)_3 in base ten, listing the running totals.

Base ten to base b

  1. Write 500 in base 3.
  2. Write 777 in base 6.
  3. Write 1000 in base 16.
  4. Write 300 in base 2.
  5. Write (1202)_3 in base 5.

Bases 2, 8 and 16

  1. Write (10111011001)_2 in base 8 and in base 16.
  2. Write (6405)_8 in base 16 without passing through base ten.
  3. Since 9 = 3^2, base nine converts to base three in blocks of two. Write (8172)_9 in base 3.

Size and divisibility

  1. How many digits does 10{,}000 have in base 3?
  2. How many positive integers have exactly 4 digits in base 5? Give the smallest and largest in both bases.
  3. How many digits does 2^{100} have in base 8, and in base 16? Write both expansions.
  4. Without finding its value, decide which of 2, 3, 4, 9, 12 divide (53220)_6.
  5. Compute (13)_5 and (23)_5, and explain why no rule of the form “look at the last j digits” can decide parity in base 5.

Reasoning and proof

  1. Prove that (121)_b is a perfect square for every base b \ge 3. Why is b \ge 3 needed?
  2. Prove that (1001)_b is composite for every base b \ge 2.
  3. Let n = (d_k \cdots d_0)_b and 1 \le j \le k. Prove that dividing n by b^j leaves quotient (d_k \cdots d_j)_b and remainder (d_{j-1} \cdots d_0)_b.
  4. Prove that if n has p digits and m has s digits in base b, then nm has p + s - 1 or p + s digits.
  5. Prove that n is a power of b exactly when its base-b expansion is a 1 followed by zeros, and that n + 1 is a power of b exactly when every base-b digit of n is b - 1.
  6. Suppose a digit 2 were allowed in base 2. Find two strings with the same value, and say which step of the uniqueness proof breaks.
Answers
  1. 446. 3 \cdot 125 + 2 \cdot 25 + 4 \cdot 5 + 1 = 375 + 50 + 20 + 1.
  2. 51. 32 + 16 + 2 + 1.
  3. 3633. 7 \cdot 512 + 6 \cdot 8 + 1 = 3584 + 48 + 1.
  4. 762. 2 \cdot 256 + 15 \cdot 16 + 10 = 512 + 240 + 10.
  5. 142. Running totals 1, 1 \cdot 3 + 2 = 5, 5 \cdot 3 + 0 = 15, 15 \cdot 3 + 2 = 47, 47 \cdot 3 + 1 = 142.
  6. (200112)_3. The remainders of 500, 166, 55, 18, 6, 2 on division by 3 are 2, 1, 1, 0, 0, 2; read upward. Check: 486 + 9 + 3 + 2 = 500.
  7. (3333)_6. 777 = 129 \cdot 6 + 3, 129 = 21 \cdot 6 + 3, 21 = 3 \cdot 6 + 3, 3 = 0 \cdot 6 + 3. Check: 3 \cdot 259 = 777.
  8. (\mathrm{3E8})_{16}. 1000 = 62 \cdot 16 + 8, 62 = 3 \cdot 16 + 14, 3 = 0 \cdot 16 + 3.
  9. (100101100)_2. 300 = 256 + 32 + 8 + 4.
  10. (142)_5. First (1202)_3 = 27 + 18 + 2 = 47; then 47 = 9 \cdot 5 + 2, 9 = 1 \cdot 5 + 4, 1 = 0 \cdot 5 + 1.
  11. (2731)_8 and (\mathrm{5D9})_{16}. Threes: 10, 111, 011, 001. Fours: 101, 1101, 1001. Both equal 1497.
  12. (\mathrm{D05})_{16}. Binary 110\,100\,000\,101, regrouped in fours as 1101, 0000, 0101. Both equal 3333.
  13. (22012102)_3. Each base-nine digit becomes two base-three digits: 8 = (22)_3, 1 = (01)_3, 7 = (21)_3, 2 = (02)_3. Both equal 5978.
  14. 9 digits, since 3^8 = 6561 \le 10{,}000 < 3^9 = 19{,}683.
  15. 500: the n with 5^3 \le n < 5^4, and 625 - 125 = 500. Smallest 125 = (1000)_5, largest 624 = (4444)_5.
  16. 34 digits in base 8 and 26 in base 16. 2^{100} = 2 \cdot 8^{33} is (2)_8 followed by 33 zeros; 2^{100} = 16^{25} is (1)_{16} followed by 25 zeros.
  17. 2, 3, 4 and 12 divide it; 9 does not. The last digit 0 is divisible by 2 and 3. Since 4, 9, 12 divide 36, use (20)_6 = 12: 4 \mid 12, 12 \mid 12, 9 \nmid 12. (Value: 7212.)
  18. (13)_5 = 8 and (23)_5 = 13: same last digit, opposite parity. For any j, if n = Q \cdot 5^j + t then n + 5^j = (Q + 1) \cdot 5^j + t, so the two have the same last j digits (Exercise 21). But 5^j is odd, so n and n + 5^j have opposite parity.
  19. (121)_b = b^2 + 2b + 1 = (b + 1)^2. The digit 2 exists only when b \ge 3.
  20. (1001)_b = b^3 + 1 = (b + 1)(b^2 - b + 1), with b + 1 \ge 3 and b^2 - b + 1 = b(b - 1) + 1 \ge 3, so both factors exceed 1.
  21. Splitting off the last j digits gives n = (d_k \cdots d_j)_b \cdot b^j + t with t = (d_{j-1} \cdots d_0)_b, and the digit bound gives 0 \le t \le b^j - 1. By uniqueness in the division algorithm with divisor b^j, these are the quotient and remainder.
  22. The bounds give b^{p-1} \le n < b^p and b^{s-1} \le m < b^s, so b^{p+s-2} \le nm < b^{p+s}, which means p + s - 1 or p + s digits.
  23. b^k = (1 0 \cdots 0)_b with k zeros, so a power has that expansion, and by uniqueness only powers do. The all-(b-1) string of length k + 1 is worth b^{k+1} - 1 (the bound above), so if n + 1 = b^{k+1} that string is the expansion of n, and conversely.
  24. (12)_2 = 2 + 2 = 4 = (100)_2. The proof called the last digit the remainder on division by 2, which needs 0 \le d_0 < 2; with d_0 = 2 that fails, so uniqueness in the division algorithm no longer applies.
kg1128 · updated 2026-10-22 · CC-BY-SA-4.0