Number theory path · N10

Before this lesson: Euclidean division and remainders, Modular arithmetic and congruences

Your goal: Translate a digit string into a polynomial in the base.

Start with the idea and one example. Take a break before the written task if you need it. The questions are original teaching exercises, not official past-paper questions.

Number Bases: Conversion and Digit Problems: the key idea

In base b≥2, digits lie in 0,…,b−1 and aₖ…a₁a₀ represents ∑aibi\sum a_{i}b^{i}, with aₖ≠0 for a multi-digit positive integer. To convert to decimal, expand the place values. To convert from decimal, repeatedly divide by b and read the remainders backwards. Since b≡1 mod b−1, a number is congruent to its digit sum modulo b−1. Since b≡−1 mod b+1, an alternating digit sum tests divisibility by b+1. State the base explicitly: the same written digits can represent different values.

A worked example

Convert (132)₅ to decimal and 42 to base 5.

(132)₅=1·25+3·5+2=42. Conversely 42=5·8+2, 8=5·1+3, 1=5·0+1; reading remainders backwards gives (132)₅.

Your turn: change one thing

Is (243)₇ divisible by 6?

Try this on paper before opening the explanation.

Compare your reasoning

Its digit sum is 2+4+3=9, congruent to 3 modulo 6, so it is not divisible by 6. Indeed its value is 129.

Pause and check

A trap to avoid: Allowing a digit at least as large as the base or a forbidden leading zero.

Practise and adjust the level

Foundation checks the language; Core applies the method; Stretch asks you to choose or justify an idea. These are levels within this lesson. A session selects six of the nine questions; unused questions allow the level to change. Advanced theory still needs written practice.

Interactive practice loads here. You can also use the complete question set below.

Write a complete argument

Prove the digit-sum congruence in base b.

Planning hint

List the assumptions and the exact conclusion. Identify the definition or theorem in this lesson that connects them. Explain why its conditions hold before using it.

Read the full solution after your attempt

Write N=∑aibiN=\sum a_{i}b^{i}. Modulo b−1, b≡1, so bi≡1b^{i}\equiv 1 for every i≥0. Hence N≡∑ai mod b−1N\equiv \sum a_{i} \bmod b-1. Thus the same remainder is obtained from the digit sum.

My proof notebook

Write on paper, or keep a draft here. Compare your reasoning with the solution only after a real attempt. The checklist is your own review, not an automatic mark.

All nine practice questions

Prefer paper or have JavaScript switched off? The complete question set, hints and solutions are here. Interactive practice uses these same questions in an order chosen from your answers.

1. Allowed digits in base b are what?

Foundation

  1. Any integer
  2. 0 through b−1
  3. 1 through b
  4. 0 through b
Hint

A digit must be smaller than the base.

Answer and reasoning

0 through b−1. The b possible digits represent the b possible remainders on division by b.

2. What does (10)₂ equal in decimal?

Foundation

  1. 2
  2. 10
  3. 1
  4. 0
Hint

Use place value.

Answer and reasoning

2. 1·2+0=2.

3. What is (132)₅ in decimal?

Core

  1. 32
  2. 47
  3. 132
  4. 42
Hint

Expand powers of 5.

Answer and reasoning

42. 25+15+2=42.

4. What is decimal 13 in binary?

Core

  1. 1110
  2. 1001
  3. 1101
  4. 1011
Hint

Use 13=8+4+1.

Answer and reasoning

1101. The coefficients of 8,4,2,1 are 1,1,0,1.

5. Digit sums in base b preserve the remainder modulo what?

Stretch

  1. b−1
  2. b
  3. b²
  4. b+2
Hint

Use b≡1.

Answer and reasoning

b−1. Every power of b becomes 1 modulo b−1.

6. Why does alternating digit sum work modulo b+1?

Stretch

  1. Every digit is odd
  2. The base is prime
  3. b≡−1 mod b+1
  4. b≡0 mod b+1
Hint

Powers of −1 alternate.

Answer and reasoning

b≡−1 mod b+1. Each successive place contributes alternating signs modulo b+1.

7. In base 5, is the digit 5 permitted?

Foundation

  1. Only as the first digit
  2. No
  3. Yes
  4. Only at the units position
Hint

Digits run from 0 to b−1.

Answer and reasoning

No. The allowed base-5 digits are 0,1,2,3,4.

8. Convert (1011)₂ to decimal.

Core

  1. 10
  2. 11
  3. 13
  4. 9
Hint

Expand 8+0·4+2+1.

Answer and reasoning

11. The value is 8+2+1=11.

9. Why read division remainders backwards when converting a positive integer to a base?

Stretch

  1. Division gives negative digits
  2. The base changes each step
  3. The first remainder is the units digit
  4. The first remainder is always zero
Hint

Successive divisions remove the lowest place.

Answer and reasoning

The first remainder is the units digit. They produce digits from least significant to most significant.

Choose your next step

Continue to Floor and ceiling functions. If this felt difficult, return to a prerequisite above. Every lesson stays open.

Open my revision list →

Original teaching material · IMOolympiad.com. Send a specific correction through our contact page. Learning progress is optional and stays in this browser.