Number Theory · Chapter 27

Bases

Every base is a regrouping rule: expand a numeral into powers of its base, then solve for digits or take a mod to read off remainders.

What's this chapter about?

27.0 Place Value in Any Base
27.1 Practice Problems

You'll need

open on YouTube

27.00%

Place Value in Any Base

In this section you will be able to read a numeral in any base as a polynomial in the base, convert both ways, and get remainders without converting.

Is $27{,}006{,}000{,}052_{9}$ divisible by $5$ ? You don’t need to convert all eleven digits. You only need to know what $9$ is mod $5$ .

A base is a regrouping rule. Base 10 carries at ten; base $b$ carries at $b$ . So each place is worth a power of $b$ , and a numeral is a polynomial in $b$ : $(a_2 a_1 a_0)_b = a_2 b^2 + a_1 b + a_0$ .

Two moves solve most contest problems. Expand the numeral into its polynomial and solve for the digits. Digits are whole numbers from $0$ to $b - 1$ , which is a strong condition. Or reduce the base mod $m$ to find remainders without converting.

Look:

$b \equiv 1 \pmod{b - 1}$ , so a base- $b$ number leaves the same remainder mod $b - 1$ as its digit sum. That is the “divisible by 9” rule, in any base.

Exploreplay first, formulas later

Try this: You are at 44 in base 5. Press ▲ on the rightmost wheel. What happens to the other wheels, and to the base-10 value?
Try this: Change base b with the stepper. The base-10 value stays put, but the digits change. Which base makes 25 look like 100?
Try this: Set base 9 and mod 5. Each place value now shows its remainder: 1 or 4 (and 4 ≡ −1). How do the digits give the remainder of the whole number?
Try this: Press Show me on Concept 27.0.3, then change the base until 0.(23) repeating equals 7/51.

Name it

Definition 27.0.1 · Bases

A number expressed in base- $n$ is similar to base $10$ , except that instead of regrouping to a new place value every $10$ , we regroup every $n$ .

Concept 27.0.2 · Place Value in Base $n$

A number in base $n$ with digits $a_m, a_{m-1}, \ldots, a_2, a_1, a_0$ can be written as

\left(a_m a_{m-1} \ldots a_2 a_1 a_0\right)_n.

This number can be evaluated as

a_m n^m + a_{m-1} n^{m-1} + \cdots + a_2 n^2 + a_1 n^1 + a_0 n^0.

Concept 27.0.3 · Base-$n$ Fractions

We can also have bases with decimals, both repeating and terminating.

A number in base $n$ with digits $a_m, a_{m-1}, \ldots, a_1, a_0$ before the point and digits $a_{-1}, a_{-2}, \ldots, a_{-q}$ after the point can be written as

\left(a_m a_{m-1} \ldots a_1 a_0 \,.\, a_{-1} a_{-2} \ldots a_{-q}\right)_n.

This number can be evaluated as

a_m n^m + a_{m-1} n^{m-1} + \cdots + a_1 n^1 + a_0 n^0 + a_{-1} n^{-1} + a_{-2} n^{-2} + \cdots + a_{-q} n^{-q}.

Watch itpredict, then reveal

Example 27.1

AMC 10/12

The base-nine representation of the number $N$ is $27{,}006{,}000{,}052_{\text{nine}}$ . What is the remainder when $N$ is divided by $5$ ?

1
Converting all eleven digits is slow. Instead: what is the remainder of $9$ when divided by $5$ ?

Predict first:
Your prediction

open on YouTube

Example 27.2

AIME

Find the three-digit positive integer $\underline{a}\,\underline{b}\,\underline{c}$ whose representation in base nine is $\underline{b}\,\underline{c}\,\underline{a}_{\,\text{nine}}$ , where $a$ , $b$ , and $c$ are (not necessarily distinct) digits.

1
Expand both numerals by place value. What is $\underline{b}\,\underline{c}\,\underline{a}_{\,\text{nine}}$ worth?

Predict first:
Click a choice or type its letter (A–E).

open on YouTube

Example 27.3

AMC 10

A base-10 three-digit number $n$ is selected at random. Which of the following is closest to the probability that the base-9 representation and the base-11 representation of $n$ are both three-digit numerals?

(A) $0.3$
(B) $0.4$
(C) $0.5$
(D) $0.6$
(E) $0.7$

1
Which numbers have exactly three digits in base $9$ ? Give the largest.

Predict first:
Your prediction

open on YouTube

Example 27.4

AMC 12

For some positive integer $k$ , the repeating base- $k$ representation of the (base-ten) fraction $\frac{7}{51}$ is $0.\overline{23}_k = 0.232323\ldots_k$ . What is $k$ ?

1
By Concept 27.0.3, what is the first block $0.23_k$ worth?

open on YouTube

Try it

Problem 27.1.1

AMC 10

In base $10$ , the number $2013$ ends in the digit $3$ . In base $9$ , on the other hand, the same number is written as $(2676)_{9}$ and ends in the digit $6$ . For how many positive integers $b$ does the base- $b$ representation of $2013$ end in the digit $3$ ?

Problem 27.1.5

AMC 10

For which of the following integers $b$ is the base- $b$ number $2021_b - 221_b$ not divisible by $3$ ?

Problem 27.1.6

AMC 10

Let $n$ be a positive integer and $d$ be a digit such that the value of the numeral $\underline{32d}$ in base $n$ equals $263$ , and the value of the numeral $\underline{324}$ in base $n$ equals the value of the numeral $\underline{11d1}$ in base six. What is $n + d$ ?

Contest cornerreal contest problems

Problem 27.1.2

AMC 10

Hexadecimal (base-16) numbers are written using numeric digits $0$ through $9$ as well as the letters $A$ through $F$ to represent $10$ through $15$ . Among the first $1000$ positive integers, there are $n$ whose hexadecimal representation contains only numeric digits. What is the sum of the digits of $n$ ?

Problem 27.1.4

AIME

A positive integer $N$ has base-eleven representation $\underline{a}\,\underline{b}\,\underline{c}$ and base-eight representation $\underline{1}\,\underline{b}\,\underline{c}\,\underline{a}$ , where $a$ , $b$ , and $c$ represent (not necessarily distinct) digits. Find the least such $N$ expressed in base ten.

Problem 27.1.11(additional)

AIME

The number $n$ can be written in base $14$ as $\underline{a}\,\underline{b}\,\underline{c}$ , can be written in base $15$ as $\underline{a}\,\underline{c}\,\underline{b}$ , and can be written in base $6$ as $\underline{a}\,\underline{c}\,\underline{a}\,\underline{c}$ , where $a > 0$ . Find the base-10 representation of $n$ .

Problem 27.1.12(additional)

AIME

Call a positive integer $N$ a $\textit{7-10 double}$ if the digits of the base- $7$ representation of $N$ form a base- $10$ number that is twice $N$ . For example, $51$ is a 7-10 double because its base- $7$ representation is $102$ . What is the largest 7-10 double?

Problem 27.1.13(additional)

AIME

Let $N$ be the number of positive integers that are less than or equal to $2003$ and whose base- $2$ representation has more $1$ 's than $0$ 's. Find the remainder when $N$ is divided by $1000$ .

Problem 27.1.15(additional)

AIME

Find the number of positive integers less than or equal to $2017$ whose base-three representation contains no digit equal to $0$ .

Checkpoint for section 27.0

Get 2 of 3 right to master this section. One try each, no hints.

27.1

Practice Problems

In this section you will be able to combine place value, digit limits and mods on harder base problems.

Time to mix the moves. Each problem hides a polynomial in some base: expand it, use the digit limits, or take a mod. Every problem has three hints if you get stuck.

Want every problem from this chapter on one page? Open the problem set.

Mixed practice

Problem 27.1.7(additional)

AMC 10

This problem also appears in the book as 27.1.6.

Problem 27.1.8(additional)

AMC 10

This problem also appears in the book as 27.1.5.

For which of the following integers $b$ is the base- $b$ number $2021_b - 221_b$ not divisible by $3$ ?

Problem 27.1.9(additional)

AMC 10

What is the greatest possible sum of the digits in the base-seven representation of a positive integer less than $2019$ ?

Problem 27.1.10(additional)

AMC 12

In the equation below, $A$ and $B$ are consecutive positive integers, and $A$ , $B$ , and $A + B$ represent number bases:

132_A + 43_B = 69_{A+B}.

What is $A + B$ ?

Contest cornerreal contest problems

Problem 27.1.3

AIME

For each positive integer $n$ , let $f(n)$ be the sum of the digits in the base-four representation of $n$ and let $g(n)$ be the sum of the digits in the base-eight representation of $f(n)$ . For example, $f(2020) = f(133210_{\text{4}}) = 10 = 12_{\text{8}}$ , and $g(2020) = \text{the digit sum of } 12_{\text{8}} = 3$ . Let $N$ be the least value of $n$ such that the base-sixteen representation of $g(n)$ cannot be expressed using only the digits $0$ through $9$ . Find the remainder when $N$ is divided by $1000$ .

Problem 27.1.14(additional)

AIME

A rational number written in base eight is $\underline{a}\,\underline{b}\,.\,\underline{c}\,\underline{d}$ , where all digits are nonzero. The same number in base twelve is $\underline{b}\,\underline{b}\,.\,\underline{b}\,\underline{a}$ . Find the base-ten number $\underline{a}\,\underline{b}\,\underline{c}$ .

Problem 27.1.16(additional)

AIME

This problem also appears in the book as 27.1.11.

Problem 27.1.17(additional)

AIME

Find the sum of all positive integers $b < 1000$ such that the base- $b$ integer $36_b$ is a perfect square and the base- $b$ integer $27_b$ is a perfect cube.

Problem 27.1.18(additional)

AIME

This problem also appears in the book as 27.1.4.

Problem 27.1.19(additional)

AIME

There exist $r$ unique nonnegative integers $n_1 > n_2 > \cdots > n_r$ and $r$ unique integers $a_k$ ( $1 \le k \le r$ ) with each $a_k$ either $1$ or $-1$ such that

a_1 3^{n_1} + a_2 3^{n_2} + \cdots + a_r 3^{n_r} = 2008.

Find $n_1 + n_2 + \cdots + n_r$ .

Problem 27.1.20(additional)

AIME

This problem also appears in the book as 27.1.3.

Problem 27.1.21(additional)

AMC 10Challenge

Bernardo chooses a three-digit positive integer $N$ and writes both its base- $5$ and base- $6$ representations on a blackboard. Later LeRoy sees the two numbers Bernardo has written. Treating the two numbers as base- $10$ integers, he adds them to obtain an integer $S$ . For example, if $N = 749$ , Bernardo writes the numbers $10{,}444$ and $3{,}245$ , and LeRoy obtains the sum $S = 13{,}689$ . For how many choices of $N$ are the two rightmost digits of $S$ , in order, the same as those of $2N$ ?