Digits and Bases

Study Sheet

Digits and Bases

Place value in any base and the tricks it enables

Base bb Representation

Concept
Every integer, every base

For any base b≥2b \ge 2, every positive integer has a unique representation n=dkbk+⋯+d1b+d0n = d_kb^k + \cdots + d_1b + d_0 with digits 0≤di<b0 \le d_i < b, written dk⋯d1d0‾b\overline{d_k\cdots d_1d_0}_b. Convert to base bb by repeated division (the remainders are the digits, last to first); convert back by evaluating the polynomial.

Base representation is the division algorithm applied repeatedly: n=bq0+d0n = bq_0 + d_0, then q0=bq1+d1q_0 = bq_1 + d_1, and so on until the quotient is 00. The first remainder is the units digit, because it is what is left after taking out all the whole groups of bb. Uniqueness comes from uniqueness of remainders. Base 22 underlies computers, base 1616 compresses base 22, and base 33 with digits −1,0,1-1, 0, 1 (balanced ternary) solves the classic weighing puzzles.

Example
4545 in binary
3211608141201132 + 8 + 4 + 1 = 45
Each box is a power of 2; a 1 means that power is used once.

Divide by 22 repeatedly, recording remainders: 45=2⋅22+145 = 2\cdot22 + 1, 22=2⋅11+022 = 2\cdot11 + 0, 11=2⋅5+111 = 2\cdot5 + 1, 5=2⋅2+15 = 2\cdot2 + 1, 2=2⋅1+02 = 2\cdot1 + 0, 1=2⋅0+11 = 2\cdot0 + 1. The first remainder is the units digit, so read them from the bottom up: 45=101101245 = 101101_2. Check: 32+8+4+1=4532 + 8 + 4 + 1 = 45.

Example
Convert 20242024 to base 77

2024=7⋅289+12024 = 7\cdot289 + 1; 289=7⋅41+2289 = 7\cdot41 + 2; 41=7⋅5+641 = 7\cdot5 + 6; 5=7⋅0+55 = 7\cdot0 + 5. Digits from the last division to the first: 562175621_7. Check: 5⋅343+6⋅49+2⋅7+1=1715+294+14+1=20245\cdot343 + 6\cdot49 + 2\cdot7 + 1 = 1715 + 294 + 14 + 1 = 2024. ✓

Example
Binary to hexadecimal

Write 10110110210110110_2 in base 1616. Since 16=2416 = 2^4, each block of four binary digits (from the right) is exactly one hexadecimal digit: 1011 ∣ 01101011\,|\,0110 is 11 ∣ 611\,|\,6, and the digit eleven is written B. So 101101102=B616=11⋅16+6=18210110110_2 = \text{B6}_{16} = 11\cdot16 + 6 = 182. Check in binary: 128+32+16+4+2=182128 + 32 + 16 + 4 + 2 = 182.

Side note
Where it goes wrong

Reading the remainders top to bottom. For 20242024 they come out 1,2,6,51, 2, 6, 5, and writing "126571265_7" gives 343+98+42+5=488343 + 98 + 42 + 5 = 488, not 20242024. The first remainder is the ones digit and belongs on the RIGHT. A one-line check by evaluating the polynomial catches this every time.

Try it
Try it: base 22

Write 200200 in binary, and say how many 11s it has.

Show the answer

The largest powers of 22 that fit: 200=128+64+8200 = 128 + 64 + 8, so 200=110010002200 = 11001000_2 (bits for 128,64,32,16,8,4,2,1128, 64, 32, 16, 8, 4, 2, 1). It has three ones. Repeated division gives the same digits.

Arithmetic in Other Bases

Concept
Carry at bb

Addition and multiplication work column by column in any base, exactly as in base ten, except that a column carries when it reaches bb instead of 1010. An equation between numerals in an unknown base becomes a polynomial equation in bb, with one extra condition: every digit that appears must be less than bb.

The column method is the distributive law: d1d0‾b+e1e0‾b=(d1+e1)b+(d0+e0)\overline{d_1d_0}_b + \overline{e_1e_0}_b = (d_1 + e_1)b + (d_0 + e_0), and when d0+e0≥bd_0 + e_0 \ge b we trade bb units for one bb, which is the carry. Nothing about ten was ever special. For unknown bases, expanding each numeral as a polynomial turns a puzzle about symbols into ordinary algebra; the digit condition then picks out the one root that makes sense.

Example
Adding in base 88

Compute 3658+2478365_8 + 247_8. Units: 5+7=12=1⋅8+45 + 7 = 12 = 1\cdot8 + 4, write 44 and carry 11. Eights: 6+4+1=11=1⋅8+36 + 4 + 1 = 11 = 1\cdot8 + 3, write 33 and carry 11. Sixty-fours: 3+2+1=63 + 2 + 1 = 6. So the sum is 6348634_8. Check in base ten: 245+167=412245 + 167 = 412 and 6⋅64+3⋅8+4=4126\cdot64 + 3\cdot8 + 4 = 412. ✓

Example
Multiplying in base 55

Compute 345×3534_5 \times 3_5. Units: 4⋅3=12=2⋅5+24\cdot3 = 12 = 2\cdot5 + 2, write 22 carry 22. Fives: 3⋅3+2=11=2⋅5+13\cdot3 + 2 = 11 = 2\cdot5 + 1, write 11 carry 22, which becomes the next digit. So 345×35=212534_5\times3_5 = 212_5. Check: 345=1934_5 = 19, 19⋅3=5719\cdot3 = 57, and 2⋅25+1⋅5+2=572\cdot25 + 1\cdot5 + 2 = 57. ✓

Example
Finding the base

In which base bb is 13b⋅15b=217b13_b\cdot15_b = 217_b? Expand: (b+3)(b+5)=2b2+b+7(b + 3)(b + 5) = 2b^2 + b + 7, i.e. b2+8b+15=2b2+b+7b^2 + 8b + 15 = 2b^2 + b + 7, so b2−7b−8=0b^2 - 7b - 8 = 0 and (b−8)(b+1)=0(b - 8)(b + 1) = 0. A base is positive, so b=8b = 8, and it must exceed every digit used — the largest is 77, so b=8b = 8 qualifies. Check: 11⋅13=143=2⋅64+8+711\cdot13 = 143 = 2\cdot64 + 8 + 7. ✓

Side note
Where it goes wrong

Forgetting the digit condition. An equation such as 5b+4=245b + 4 = 24 solves to b=4b = 4, but a numeral containing the digit 55 cannot be in base 44 — so there is NO valid base. Every root of the polynomial must be checked against the digits before it is accepted, and negative or fractional roots discarded.

Try it
Try it: an unknown base

Find the base bb in which 24b+35b=103b24_b + 35_b = 103_b.

Show the answer

Expand: (2b+4)+(3b+5)=b2+3(2b + 4) + (3b + 5) = b^2 + 3, so b2−5b−6=0b^2 - 5b - 6 = 0, (b−6)(b+1)=0(b - 6)(b + 1) = 0, and b=6b = \mathbf{6} (positive, and larger than the digit 55). Check: 16+23=39=36+316 + 23 = 39 = 36 + 3. ✓

Digit Problems

Concept
Digits as unknowns

A two-digit number with digits a,ba, b is 10a+b10a + b; reversing gives 10b+a10b + a; their difference is 9(a−b)9(a - b). Writing the number in terms of its digits turns a digit puzzle into an equation with small integer unknowns, solvable by bounding and casework.

The payoff is that digits are tightly bounded — 1≤a≤91 \le a \le 9 for a leading digit, 0≤b≤90 \le b \le 9 otherwise — so an equation with infinitely many real solutions often has only a handful of digit solutions, found by checking a short list. Bound first, then test: the equation tells you which way to squeeze.

Example
Four times the digit sum

A two-digit number is 44 times the sum of its digits. Which? 10a+b=4(a+b)10a + b = 4(a + b) gives 6a=3b6a = 3b, so b=2ab = 2a. With b≤9b \le 9, a≤4a \le 4: the numbers are 12,24,36,4812, 24, 36, 48. Each checks: 36=4⋅936 = 4\cdot9.

Example
A reversal puzzle

A two-digit number exceeds its reversal by 5454, and its digits sum to 1212. Find it. The difference is 9(a−b)=549(a - b) = 54, so a−b=6a - b = 6; with a+b=12a + b = 12, adding gives 2a=182a = 18: a=9a = 9, b=3b = 3. The number is 9393, and 93−39=5493 - 39 = 54. ✓

Example
Bounding a three-digit number

Find every three-digit number equal to 1212 times the sum of its digits. 100a+10b+c=12(a+b+c)100a + 10b + c = 12(a + b + c) simplifies to 88a=2b+11c88a = 2b + 11c. The right side is at most 18+99=11718 + 99 = 117, so a=1a = 1 and 2b+11c=882b + 11c = 88. Then 11c11c must be even and at most 8888, so c∈{0,2,4,6,8}c \in \{0, 2, 4, 6, 8\}, which leaves 2b=88,66,44,22,02b = 88, 66, 44, 22, 0 — only c=8c = 8 gives a digit, b=0b = 0. The one answer is 108=12⋅9108 = 12\cdot9.

Tip
Digit sums and 99

A number and its digit sum are congruent mod 99. Repeatedly taking digit sums (the "digital root") gives n mod 9n \bmod 9, with 99 in place of 00.

Side note
Where it goes wrong

Forgetting the digit range: leading digits are 11–99, others 00–99. In the three-digit example, c=6c = 6 gives 2b=222b = 22, b=11b = 11, which solves the equation but is not a digit. Treat the range as part of the equation.

Try it
Try it: digital root

Find the digital root of 220=10485762^{20} = 1048576.

Show the answer

Digit sum 1+0+4+8+5+7+6=311+0+4+8+5+7+6 = 31, then 3+1=43 + 1 = 4. Check without the digits: 26=64≡1(mod9)2^6 = 64 \equiv 1 \pmod 9, so 220=(26)3⋅22≡42^{20} = (2^6)^3\cdot2^2 \equiv 4. The digital root is 4.

Why It Works

Suppose nn has two representations and subtract them: 0=ckbk+⋯+c1b+c00 = c_kb^k + \cdots + c_1b + c_0 with each ci=di−eic_i = d_i - e_i satisfying ∣ci∣<b|c_i| < b. Then bb divides c0c_0 (everything else is a multiple of bb), and ∣c0∣<b|c_0| < b forces c0=0c_0 = 0. Divide by bb and repeat: c1=0c_1 = 0, then c2=0c_2 = 0, and so on. Every digit agrees. Existence is the repeated division, which stops because the quotients strictly decrease.

For two digits, (10a+b)−(10b+a)=9a−9b(10a + b) - (10b + a) = 9a - 9b. For three, (100a+10b+c)−(100c+10b+a)=99(a−c)(100a + 10b + c) - (100c + 10b + a) = 99(a - c): the middle digit cancels and the difference is a multiple of 9999. In general, a number and ANY rearrangement of its digits have the same digit sum, hence the same remainder mod 99, so their difference is a multiple of 99.