II. Arithmetic

A child of the new generation Refused to learn multiplication He said, “Don’t conclude That I’m stupid,, or rude. I am simply without motivation.”

Joel Henry Hildebrand (1881–1983)

Many important aspects of serious mathematics have their roots in the world of arithmetic. This is a world everyone can enjoy and master. In this chapter we re-visit, or maybe meet for the first time, key aspects of arithmetic that are often overlooked – ending with an introduction to the basic result on the distribution of primes.

The place of arithmetic in elementary mathematics can only be understood if one realises that, from upper primary school onwards, mathematics should no longer focus on more and more complicated calculations. Rather it moves beyond a set of procedures for grinding out answers, and should become a structural laboratory, where we gain insight into simple phenomena, and where we begin to appreciate how calculation can be managed, or tamed. The focus on structure leads in the main to matters which can be best expressed algebraically. This chapter concentrates mainly on structural aspects of number that are strictly arithmetical (e.g. related to numerals and place value), or where the relevant structural approach is “pre-algebraic” – with occasional forays into the world of algebra.

We repeat the observation that the “essence of mathematics” in the title is mostly left implicit in the problems. And while there is some discussion of this “essence” in the text between the problems, most of the relevant observations that we make are to be found in the solutions, or in the Notes which follow many of the solutions.

2.1. Place value and decimals: basic structure

Problem 40 Without using a calculator:

(a) Work out

(i) 12 345 679 × 9

(ii) 7 × 9 × 11 × 13.

(b) Divide

(i) 123 123 123 by 123

(ii) 111111111 by 111

(iii) 111111111 by 37.

Problem 41 Work out in your head (i) 11² (ii) 11³ (iii) 101².

Problem 42 Try to answer the following questions using only mental arithmetic:

(a) (i) What is the largest and the smallest possible number of digits in the answer when you multiply a 3-digit integer by a 5-digit integer?

(ii) What if we multiply an m-digit integer by an n-digit integer?

(b) (i) How many (base 10) digits are there in the evaluated form of 2²⁰?

(ii) Estimate to 6 decimal places.

(c) Can a natural number (i.e. a positive integer) be smaller than the product of its (base 10) digits?

(d) Work out how many zeros there are on the end, and work out the last non-zero digit of (i) 2¹⁵ × 5³ (ii) 20!.

Problem 43 Imagine the sequence of positive integers from 1 to 60 written in a single row as the digits of a very large integer:

1234567891011121314151617181920212223···5960.

You have to cross out 100 of these digits.

(a) Suppose you want to make the remaining number as small as possible. What number is left?

(b) Now suppose that you want to make the remaining number as large as possible. What number is left?

2.2. Order and factors

Problem 44 Find the remainder when we divide

1111 · · · 1111 (with 1111 digits 1)

by 1111.

Problem 45 Which of the numbers

is bigger?

Problem 46 Show that the integer

100 000 000 003 000 000 000 000 700 000 000 021

is not prime.

Problem 47 How many prime numbers are there in each of these sequences? (Can you identify infinitely many primes in either sequence? Can you identify infinitely many non-primes?)

(a) 1, 11, 111, 1111, 11111, 111111, 1111111, ...

(b) 11, 1001, 100001, 10000001, ...

2.3. Standard written algorithms

Problem 48 Use standard column arithmetic (i.e. long multiplication) to evaluate 9009 × 37. Why should you have foreseen the outcome?

Problem 49 In the long division shown here, all the digits are missing.

But the “shape” of the constituent numbers is clear.

Can you work out all possibilities for the two-digit divisor?

Problem 50 (For those readers who can write simple computer code.) In these problems you may choose your favourite programming language, and a device of your choice.

(a) Two non-negative integers m and n are to be entered in base 10, digit by digit, via a keyboard. Write computer code to implement the standard algorithms of column arithmetic in order to output to the screen (in the same format):

(i) m + n

(ii) m − n

(iii) m × n

(iv) (if n is a divisor of m) m ÷ n

(v) (if n is not a divisor of m) the integer part q of the quotient m ÷ n and the remainder r.

(b) Repeat the challenge of part (a), but this time try to write shorter code by using recursion (or other programming tricks).

(c) Repeat the challenge of parts (a) and (b), but this time with inputs and outputs in the binary numeral system (see Section 2.8).

2.4. Divisibility tests

An integer written in base 10:

is divisible by 10 precisely when the units digit is 0.

Because 10 = 2 × 5, it follows that an integer (in base 10):

is divisible by 5 precisely when the units digits is 0 or 5 (i.e. a multiple of 5); and

is divisible by 2 precisely when the units digit is 0, 2, 4, 6, or 8 (i.e. a multiple of 2).

Because 100 = 4 × 25, it follows that an integer:

is divisible by 4 precisely when the integer formed by its last two digits is a multiple of 4; and

is divisible by 25 precisely when its last two digits are 00, 25, 50, or 75 (that is, a multiple of 25).

Because 1000 = 8 × 125, it follows that an integer:

is divisible by 8 precisely when the integer formed by its last three digits is a multiple of 8.

Hence simple tests for divisibility by 2, by 4, by 5, by 8, and by 10 all follow easily from the way we write numbers in base 10.

Problem 51

(a) Prove that, when an integer is written in base 10, the remainder when it is divided by 9 is equal to the remainder when its “digit-sum” is divided by 9. Conclude that the remainder when an integer is divided by 3 is equal to the remainder when its “digit-sum” is divided by 3.

(b) Explain why an integer is divisible by 6 precisely when it is divisible both by 2 and by 3.

Problem 52

(a) What can you say about an integer N which is divisible by three times the sum of its base 10 digits?

(b) Find all integers which are equal to three times the sum of their base 10 digits.

(c) Find the smallest positive multiple of 9 with no odd digits.

Problem 53 Prove than an integer written in base 11 is divisible by ten precisely when its digit-sum is divisible by ten.

2.5. Sequences

We have already met

• the sequence of natural numbers (1, 2, 3, 4, 5, ...),
• the sequence of squares (1, 4, 9, 16, 25, ...),
• the sequence of cubes (1, 8, 27, 64, 125, ...),
• the sequence of prime numbers (2, 3, 5, 7, 11, 13, 17, ...),
• the sequence of powers of 2 (1, 2, 4, 8, 16, 32, ...), and the sequence of powers of 4 (1, 4, 16, 64, 256, ...).

We have also considered

• the sequence of units digits of the powers of 4 (1, 4, 6, 4, 6, 4, 6, ...),
• the sequence of leading digits of the powers of 4 (1, 4, 1, 6, 2, 1, 4, ...).

2.5.1 Triangular numbers

Problem 54

(a) Evaluate the first twelve terms of the sequence of triangular numbers:

(b) Find and prove a formula for the n^th triangular number

(c) Which triangular numbers are also (i) powers of 2? (ii) prime? (iii) squares? (iv) cubes?

2.5.2 Fibonacci numbers

The Hindu-Arabic numeral system emerged in the Middle East in the 10^th and 11^th centuries. Fibonacci, also known as Leonardo of Pisa, is generally credited with introducing this system to Europe around 1200 – especially through his book Liber Abaci (1202). One of the problems in that book introduced the sequence that now bears his name.

The sequence of Fibonacci numbers begins with the terms F₀ = 0, F₁ = 1, and continues via the Fibonacci recurrence relation:

The sequence was introduced through a curious problem about breeding rabbits; but to this day it continues to feature in many unexpected corners of mathematics and its applications.

Problem 55

(a) (i) Generate the first twelve terms of the Fibonacci sequence:

(ii) Use this to generate the first eleven terms of the sequence of “differences” between successive Fibonacci numbers. Then generate the first ten terms of the sequence of “differences between successive differences”.

(iii) Find an expression for the m^th term of the k^th sequence of differences.

(b) (i) Generate the first twelve terms of the sequence of powers of 2:

(ii) Use this to generate the first eleven terms of the sequence of “differences” between successive powers of 2. Then generate the first ten terms of the sequence of “differences between successive differences”.

(iii) Find an expression for the m^th term of the k^th sequence of differences.

The sequence of differences between successive terms in the sequence of triangular numbers is just the sequence of natural numbers (starting with 2):

and the sequence of “second differences” is then constant:

The sequences of powers of 2 and the Fibonacci numbers behave very differently from this, in that taking differences reproduces something very like the initial sequence. In particular, taking differences can never lead to a constant sequence.

Logically the next four problems should wait until Chapter 6, where we address the delicate matter of “proof by mathematical induction”. However, that would deprive us of the chance to sample the kind of surprises that lie just beneath the surface of the Fibonacci sequence, and to experience the process of fumbling our way towards a structural understanding of the apparent patterns that emerge. Of course, each time we think we have managed to guess what seems to be true, we face the challenge of proof. Those who have not yet mastered “proof by induction” are encouraged to get what they can from the solutions, and to view this as an informal introduction to ideas that will be squarely addressed in Chapter 6.

Problem 56

(a) (i) Generate the sequence of partial sums of the sequence of powers of 2:

(ii) Prove that each partial sum is 1 less than the next power of 2.

(b) (i) Generate the sequence of partial sums of the Fibonacci sequence:

(ii) Prove that each partial sum is 1 less than the next but one Fibonacci number.

Problem 56(b) starts out with the observation that

which is a consequence of the first two instances of the fundamental recurrence relation

and derives a surprising value for the n^th partial sum:

Fibonacci numbers make their mathematical presence felt in a quiet way – partly through the almost spooky range of unexpected internal relations which they satisfy, as illustrated in Problem 56(b) and in the next few problems.

Problem 57

(a) Note that

(i) Evaluate the succession of terms:

(ii) Guess a simpler expression for the product . Prove your guess is correct.

(b) Let .

(i) Show that the parallelogram OABC spanned by the origin O, and the points and their sum has area .

(ii) Find the area of the first parallelogram in the sequence of “Fibonacci parallelograms”, spanned by the origin O, and the points , .

(iii) Show that the n^th parallelogram OACB in this sequence, spanned by the origin O, and the points and , and the parallelogram OBDC spanned by the origin O, and the points and overlap in the triangle OBC, which is exactly half of each parallelogram.

Conclude that every such parallelogram has area 1. Relate this to the conclusion of (a)(ii).

The basic recurrence relation for Fibonacci numbers specifies the next term as the sum of two successive terms. We now consider what this implies about the sum of the squares of two successive terms.

Problem 58

(a) Evaluate the first few terms of the sequence

(b) Guess a simpler expression for the sum . Prove your guess is correct.

Problem 59

(a) Note that

(i) Evaluate the succession of terms:

(ii) Guess a simpler expression for the product . Prove your guess is correct.

(b) (i) Evaluate the succession of terms:

(ii) Guess a simpler expression for the product . Prove your guess is correct.

2.6. Commutative, associative and distributive laws

In this short section we re-emphasise the shift away from blind calculation, and towards consideration of the structure of arithmetic, which was already implicit in Problems 7—10, and Problems 16—17 in Chapter 1.

Problem 60 Each of two positive numbers a and b is increased by 10%.

(i) What is the change of their sum ?

(ii) What is the percentage change of their product ?

(iii) What is the percentage change in their quotient ?

Problem 61 The numbers a, b, c, d, e, f are positive. How will the value of the expression

change if the value of f is doubled?

Problem 62 In Problem 17 we saw that it is no accident that the sum of entries in the 4 by 4 ‘multiplication table’ is equal to 100.

(a) Go back to the proof that the total is equal to and see how this depends on the distributive law.

(b) The total of all entries in the multiplication square can be broken down into a succession of “reverse L-shapes”, such as the one formed by the bottom row and right hand column (shown above in bold).

(i) Work out the subtotal in each of the four reverse L-shapes in the 4 by 4 multiplication table. What do you notice about these four subtotals?

(ii) Use the formulae for the k^th and (k — 1)^th triangular numbers T_k and T_k-₁ to prove that, in the n by n multiplication table, the k^th reverse L-shape always gives rise to a subtotal k³.

Conclude that

Hence find a simple formula for the sum C_n of the first n cubes.

Now that we have a compact formula

• for the sum T_n of the first n positive integers, and
• for the sum Cn of the first n positive cubes,

we would naturally like to find a similar formula

• for the sum S_n of the first n squares:

  (that is, the sum of the entries on the leading diagonal of the n by n multiplication square).

This can be surprisingly elusive. But one way of obtaining it is to look instead for the sum of the entries in the sloping diagonal 2, 6, 12, 20, ... just above the main diagonal in the n by n multiplication square.

Problem 63 Consider the n by n multiplication square.

(a) Express the r^th term in the sloping diagonal just above the main diagonal in terms of r. Hence show that the sum of entries in this sloping diagonal is equal to .

(b) Multiply by 3 each of the terms in the sloping diagonal just above the main diagonal.

(i) Guess a formula for the successive sums of these terms (6, 6 + 18, 6 + 18 + 36, ...), and prove that your formula is correct.

(ii) Hence derive a formula for the sum of the first n squares.

2.7. Infinite decimal expansions

The standard written algorithms for calculating with integers extend naturally to terminating decimals. But how is one supposed to calculate exactly with decimals that go on for ever?

Problem 64 The decimals listed here all continue forever, recurring in the expected way. Calculate:

(a)

(b)

(c)

(d)

(e)

Problem 65

(a) Show that any decimal that terminates can be written as a fraction with denominator a power of 10.

(b) Show that any fraction that is equivalent to a fraction with denominator a power of 10 has a decimal that terminates.

(c) Conclude that a fraction , for which HCF(p,q) = 1, has a decimal that terminates precisely when q divides some power of 10 (that is, when for some non-negative integers a, b).

(d) Prove that any fraction , for which HCF(p,q) = 1, and where q is not of the form , has a decimal which recurs, with a recurring block of length at most q – 1.

(e) Prove that any decimal which recurs is the decimal of some fraction.

Problem 66

(a) Find the fraction equivalent to each of these recurring decimals:

(i) 0.037037037···

(ii) 0.370370370 ···

(iii) 0.703703703 ···

(b) Let a, b, c be digits ().

(i) Write the recurring decimal “0.aaaaa · · · “ as a fraction.

(ii) Write the recurring decimal “0.ababababab · · · “ as a fraction.

(iii) Write the recurring decimal “0.abcabcabcabcabc · · · “ as a fraction.

Problem 67 Find the lengths of the recurring blocks for:

(a)

(b)

(c)

(d)

Problem 68 Decide whether each of these numbers has a decimal that recurs. Prove each claim.

(a)

(b)

(c)

Problem 69 For which real numbers x is the decimal representation of x unique?

Problem 68 raises the question as to whether one person, who has total control, can specify the digits of a decimal so as to be sure that it neither terminates nor recurs: that is, so that it represents an irrational number. The next problem asks whether one person can achieve the same outcome with less control over the choice of digits.

Problem 70 Players A and B specify a real number between 0 and 1. The first player A tries to make sure that the resulting number is rational; the second player B tries to make sure that the resulting number is irrational. In each of the following scenarios, decide whether either player has a strategy that guarantees success.

(a) Can either player guarantee a “win” if the two players take turns to specify successive digits: first A chooses the entry in the first decimal place, then B chooses the entry in the second decimal place, then A chooses the entry in the third decimal place, and so on?

(b) Can either player guarantee a win if A chooses the digits to go in the odd-numbered places, and (entirely separately) B chooses the digits to go in the even-numbered places?

(c) What if A chooses the digits that go in almost all the places, but allows B to choose the digits that are to go in a sparse infinite collection of decimal places (e.g. the prime-numbered positions; or the positions numbered by the powers of 2; or ...)?

(d) What if A controls the choice of all but a finite number of decimal digits?

2.8. The binary numeral system

There are all sorts of reasons why one should give thought to numeral systems using bases different from the familiar base 10. This is especially true of base 2, which is the simplest system of all, and is also (in some sense) the most widely used. What follows is only intended to offer a restricted glimpse into this alternative universe.

Problem 71 The numbers in this item are all written in base 2.

(a) Carry out the addition

without changing the numbers into their base 10 equivalents – simply by applying the rules for base 2 column addition and “carrying”.

(b) Carry out these long multiplications without changing the numbers into their base 10 equivalents – simply by applying the rules for base 2 column multiplication.

(i)

(ii)

(iii)

(c) Try to add these fractions (where the numerators and denominators are numerals written in base 2) without changing the fractions into more familiar base 10 form.

The next problem invites you to devise divisibility tests for integers written in base 2 like those for base 10 (that is, tests which implement some check involving the base 2 digits in place of carrying out the actual division).

Problem 72 Let N be a positive integer written in base 2. Describe and justify a simple test, based on the digits of N_base2:

(i) for N to be divisible by 2

(ii) for N to be divisible by 3

(iii) for N to be divisible by 4

(iv) for N to be divisible by 5.

Problem 73 A mathematical merchant has a pair of scales and an infinite set of calibrated integral weights with values (where ), but with only one weight of each value.

(a) Suppose that, for each object of positive integer weight w whose weight is to be determined, when the object is placed in one scale pan, the merchant is able to select some combination of his weights to put in the other scale pan to balance, and hence to determine the weight of, the object to be weighed.

(i) If for each weight w there is a unique choice of weights w_i that balance w, prove that the collection of weights must consist of all the powers of 2.

(ii) If every object of unknown integral weight w can be balanced by some collection of the weights w_i, but some weights w can be balanced, or “represented”, in more than one way, is it true that the merchant’s collection of weights has to include all the powers of 2?

(b) What can you prove if the merchant’s set of weights allow him to balance every unknown integer weight w in exactly one way by varying his weighing procedure, so that he can place his “known weights” in either scale pan (either in the same scale pan as the unknown weight to add to its weight, or in the opposite scale pan to balance it)?

Problem 74 Explain how to express any fraction

where as a sum of distinct unit fractions with denominator a power of 2.

You may have heard of an algorithm (a bit like long division) which allows one to compute by hand the square root of any number N given in base 10. The algorithm starts by grouping the digits of N in pairs, starting from the decimal point. It then extracts the square root, digit by digit, with the square root having one digit for each successive pair of digits of N, starting with the left-most pair (which may be a single digit).

We all know how to start the process. For example, if the left most pair of digits in N is “12”, then we know that the square root starts with a “3”. Successive digits are then identified using the algebraic identity

where x is the sequence of leading digits in the “partial square root” extracted so far (followed by an appropriate string of 0s), and y stands for the residual part of the required square root.

The key is to concentrate each time on the leading digit Y of the residue ““, and at each stage to choose the leading digit Y of y so that does not exceed . This sequence of steps is traditionally (and helpfully) laid out in much the same way as long division, where at each stage we subtract the square of the current approximate square root x, from the original number N, and “bring down” the next pair of digits, and then choose the next digit Y in the square root (the leading digit of y) so that ““ does not exceed the residue .

In base 10 each stage requires one to juggle possibilities to decide on the next digit in the partial square root. However, in base 2 the process should be simpler, since at each stage we only have to decide whether the next digit is a 1 or a 0.

Problem 75 Work out how to calculate the square root of any square given in base 2.

2.9. The Prime Number Theorem

We have already observed that there are 4 primes less than 10, 25 primes less than 100, and 168 primes less than 1000. And there are 78 498 primes less than 10⁶. So

40% of integers < 10 are prime;

25% of integers < 100 are prime;

16.8% of integers < 1000 are prime; and

7.8498% of integers < 10⁶ are prime.

In other words, the fraction of integers which are prime numbers diminishes as we go up.

The first question to ask is whether prime numbers themselves “run out” at some stage, or whether they go on for ever. The answer is very like that for the counting numbers, or positive integers 1, 2, 3,4, 5,...:

the counting process certainly gets started (with 1); and no matter how far we go, we can always “add 1” to get a larger counting number.

Hence we conclude that the counting numbers “go on for ever”.

Problem 76

(a) (i) Start the process of generating prime numbers by choosing your favourite small prime number and call it p₁.

(ii) Then define .

(b) (i) Since , n₁ must be divisible by some prime. Explain why p₁ is not a factor of n₁. (What is the remainder when we divide n₁ by p₁?)

(ii) Let p₂ be the smallest prime factor of n₁.

(iii) Define

(c) (i) Since n₂ > 1, n₂ must be divisible by some prime. Explain why p₁ and p₂ are not factors of n₂. (What is the remainder when we divide n₁ by p₁, or by p₂?)

(ii) Let p₃ be the smallest prime factor of n₂.

(iii) Define

(d) Suppose we have constructed k distinct prime numbers p₁, p₂, p₃, ... , p_k. Explain how we can always construct a prime number p_k+1 different from .

(e) Apply the above process with p₁ = 2 to find p₂, p₃, p₄, p₅.

Once we know that the prime numbers go on for ever, we would like to have a clearer idea as to the frequency with which prime numbers occur among the positive integers. We have already noted that

• there are 4 primes between 1 and 10,
• and again 4 primes between 10 and 20;
• but there is only 1 prime in the 90s;
• and then 4 primes between 100 and 110.
• And there are no primes at all between 200 and 210.

In other words, the distribution of prime numbers seems to be fairly chaotic. Our understanding of the full picture remains fragmentary, but we are about to see that the apparent chaos in the distribution of prime numbers conceals a remarkable pattern just below the surface.

The next item is only an experiment; but it is a very suggestive experiment. It is artificial, in that what you are invited to count has been carefully chosen to point you in the right direction. The resulting observation is generally referred to as the Prime Number Theorem. The result was conjectured by Legendre (1752–1833) and by Gauss (1777–1855) in the late 1790s – and was proved 100 years later (independently and almost simultaneously) in 1896 by the French mathematician Hadamard (1865–1963) and by the Belgian mathematician de la Vallée Poussin (1866–1962). You will need to access a list of prime numbers up to 5000 say.

Problem 77 Let denote the number of prime numbers : so , , , . You are invited to count the number of primes up to certain carefully chosen numbers, and then to study the results. The pattern you should notice works just as well for other numbers – but is considerably harder to spot.

The special values we choose for “x” are

the next integer above successive powers of the special number e,

where e is an important constant in mathematics – an irrational number whose decimal begins 2.7182818 · · ·, and which has its own button on most calculators (see Problem 248).

(a) Complete the following table.

n	en	next integer N	π(N)
1	2.718⋯	3	2
2	7.389⋯
3	20.08⋯
4	54.59⋯
5	148.41⋯
6	403.42⋯
7	1096.63⋯
8	2980.95⋯
9	8103.08⋯		1019

(b) Find an expression that seems to specify as a function of n. Hence conjecture an expression for in terms of x.

Durch planmassiges Tattonieren.

[Through systematic fumbling.]

Carl Friedrich Gauss (1777-1855),

when asked how he came to make so many profound discoveries in mathematics.

2.10. Chapter 2: Comments and solutions

40.

(a) (i) 111111111

(ii) 9009 (1001 = 7 × 11 × 13 is a factorisation that is worth remembering for all sorts of reasons: for example, it incorporates 91 = 7 × 13; and it lies behind certain tests for divisibility by 7).

(b) (i) 1001001; (ii) 1001001; (iii) 3 003 003 (since 111 = 3 × 37)

41.

(i) ;

(ii) ;

(iii)

42.

(a) (i) Largest 8, smallest 7. (The smallest 3-digit number is 100 and the smallest 5-digit number is 10 000, so the smallest possible product is - and so has 7 digits. The largest 3-digit number is just less than 1000 and the largest 5-digit number is just less than 100 000, so the largest possible product is just less than – and so has 8 digits.)

(ii) Largest , smallest . (The smallest m-digit number is and the smallest n-digit number is , so the smallest possible product is – and so has digits. The largest m-digit number is just less than 10^m and the largest n-digit number is just less than 10ⁿ, so the largest possible product is just less than – and so has digits.)

(b) (i) is very slightly larger than 10³. Hence is very slightly larger than 10⁶, so has 7 digits.

(ii) 2²⁰ is very slightly larger than 10⁶. In fact

is its reciprocal, so is slightly smaller than , so it starts with six 0s after the decimal point and rounds up to 0.000001 (to 6 d.p.).

(c) No. (It can be equal to the product of its digits if it has just 1 digit. If a number N has k digits, with leading digit = m, then , but the product of its digits is at most .)

(d) (i) 3, 6. ()

(ii) 4, 4. (Most of us will need some rough work to supplement mental arithmetic here.

So 20! ends in 4 zeros, and its last non-zero digit is equal to the units digit of . If we work “mod 10” this is equal to the units digit of .)

Note: The reader may notice that we have used “congruences”, or “modular arithmetic” (mod 10) here and at several points in Chapter 1 (e.g. in the solutions to Problem 2(d), Problem 13, Problem 16(b)).

In all these contexts one only needs to know that, if we fix the divisor n, then the remainders on division by n can be added and multiplied like ordinary numbers, since

and

Division is more delicate. We leave the reader to look up the details in any book on elementary number theory.

43. (a) 00 000123450 (b) 99 999 785 960

The initial number has digits. Hence we are left with a number having exactly 11 digits.

For the smallest integer, we delete digits to leave the smallest initial digits (preferably 0s).

For the largest integer, we delete digits to leave as many 9s at the front as possible (and then sort out the tail).

44.

In much the same way

(with 1108 1s and three 0s) is exactly divisible by 1111. So the remainder is 111.

45. Compare and .

The second is bigger than the first, so the second fraction is bigger than the first.

46. The fact that , and the position of the zeros, suggests that we express the integer as:

Note: If you feel you should have been “given a hint”, then pause for a moment. There is nothing misleading here. We have no standard techniques for analysing such large numbers. The very size of the number forces you to think whether there is anything familiar about it that you might use. And the number is so simple that the only thing that can possibly stand out is the 3, 7, and 21. The rest is up to you.

47.

(a) 11 is prime. And 111 is a multiple of 3: . You should also be able to see that 1111 is a multiple of 11: .

It is unclear whether 11111 is prime or not. The Square Root Test says that to decide, we only need to check possible prime factors up to . We can eliminate 2, 3, 5, 7, 11 mentally, with very little effort. And with a calculator, it is easy to check 13, 17, 19, 23, 29, 31, 37, 41, ... and to discover that .

Clearly .

So the sequence does not look too promising. All the even-numbered terms are divisible by 11; every third term is divisible by 111 (and of course, by 3); every fourth term is divisible by 1111 (and hence by 101); and so on. So the only possible candidates for primes are the second, third, fifth, seventh, eleventh, ... terms: that is the terms in prime positions.

Each of these terms is equal to the second bracket in the factorisation:

where p is a prime number.

We have seen that , and that , which is not very encouraging. The 7^th, 11^th, 13^th, and 17^th terms are also not prime. But the 19^th term and the 23^rd terms are prime.

So primes seem scarce, but 11 is not the only prime in the sequence.

Note: Again, if you feel the problem was misleading, then pause for a moment. Part of “the essence of mathematics” is learning that some problems have a tidy solution, while others open up a rather different agenda. The only obvious way to begin to recognise this distinction is occasionally to be left to struggle to solve something that is presented as if it were a closed problem (with a tidy solution), only to discover that it is messier than one expected.

(b) We have already seen that .

Another reason for remembering this is that it is a simple instance of the standard factorisation:

Because the signs in the second bracket are alternately “+” and “-”this factorisation extends to all odd powers of 10: for example,

So this time, 11 is the only prime in the list.

Note: The missing “odd” terms

are slightly different – each being of the form .

The fact that there is an algebraic factorisation of

implies that has to factorise. But the lack of an algebraic factorisation of does not prevent any particular number of the form from factorising: for example, , and both factorise; but , , and do not.

One may be forgiven for not knowing that But one should realize that

48. The prime factorisation is worth remembering. If this is second nature, then one can do better in this problem than merely grind out the answer using long multiplication, by seeing how the output to the calculation simply positions “333 thousands” and “333 units” next to each other:

, so .

Hence .

Note: The prime factorisation of 1001 is not needed here. But it is important elsewhere.

49. The very first step shows that the leading digit of the dividend must be 1; and since “three-digit minus two-digit leaves one-digit (d say)” the divisor has a multiple in the 90s.

The very next stage again gives “three-digit minus two-digit leaves one-digit”, and the remainder from the first division is now the hundreds digit, so d = 1. Hence the two-digit divisor has 99 as a multiple (at the first step of the long division) – so the divisor must be 11, 33, or 99.

The next division shows that the divisor has a two-digit multiple, which when subtracted from a two-digit number leaves a two-digit remainder, so the divisor cannot be 99.

The final stage shows that the divisor has a three-digit multiple, so it cannot be 11.

Hence the divisor must be 33.

50. Your solution will depend on the programming language used. We use this problem to attract the reader’s attention to some not so frequently discussed issues:

• The “formal written algorithms” of arithmetic are not entirely obvious.
• Their practical use is not really “formal”, it uses a number of unstated conventions. For example, it requires from the user an intuitive feel for the “data structures” involved and starts by writing one base 10 integer under another keeping digits in the same decimal position aligned in a column (a computer scientist would call it “parsing the input”).
• Base 10 integers contain different numbers of digits and shorter ones may need to be padded with zeroes (mentally, in calculations on paper, or explicitly, as may be necessary when writing code), that is, has to be treated as .
• Digits in the number are read and used from right to left, the opposite way to reading text. (This may be a piece of fossilised history: our decimals are Arabic, and Arabs write from right to left.)

51.

(a) This exploits the fact that

and so is divisible by (a fact which is obvious when we write , , , etc.). For example:

If the LHS is divided by 9, the remainder from the first bracket on the RHS is zero, so the overall remainder is the same as the remainder from dividing the digit sum by 9.

Since 9 is a multiple of 3, the first bracket is exactly divisible by 3. Hence if the LHS is divided by 3, the remainder from the first bracket on the RHS is zero, and the overall remainder is the same as the remainder from dividing the digit sum by 3.

Note: If we were only interested in “divisibility by 9”, then we could have managed without appealing to the algebraic factorisation

since

are all visibly “multiples of 9”. However, the structure of the above solution extends naturally to prove that, when an integer is written in base b, the remainder on division by is the same as the remainder on dividing the base b “digit sum” by .

(b) If an integer N is divisible by 6, then we can write for some integer m.

Hence , so N is a multiple of 2; and , so N is a multiple of 3.

If an integer N is divisible by 2, then we can write for some integer k. If N is also divisible by 3, then 3 divides exactly into 2k. But HCF(2, 3) = 1, so the 3 must go exactly into the second factor k, so for some integer m, and is divisible by 6.

Note: It is crucial that HCF(2, 3) = 1. (E.g. 12 is divisible by 6 and by 4; but 12 is not divisible by .)

52.

(a) N is divisible by 3. Hence its digit-sum is divisible by 3.

But then “three times the sum of its digits” is a multiple of 9: hence the integer is divisible by 9, and so the sum of its digits is divisible by 9.

But then it is divisible by “three time a multiple of 9” – that is divisible by 27. So , or 54, or 81, or 108, or .... (However, you soon come to the first multiple of 27 that is not “divisible by 3 times the some of its digits”.)

(b) 27. (Suppose the integer N has k digits. Then , and its digit-sum is at most 9k. If N is equal to “three times the sum of its digits”, then which means . And from part (a) we know that N is a multiple of 27.)

(c) 288. (If the digit sum is equal to 9 (or any odd multiple of 9), then at least one digit must be odd; so we only need to worry about integers with digit-sum equal to 18, or 36, or .... The only such multiple of 9 up to 100 is 99. All multiples of 9 between 100 and 200 have an odd hundreds digit. In the 200s, the first integer with digit-sum 18 is 279 – with two odd digits. The next is 288.)

53. (a) This exploits the fact that

and so is divisible by (11 — 1) – a fact which is obvious if we introduce a new digit X in base 11 to stand for “ten”, and then notice that

For example:

If the LHS is divided by ten, the remainder from the first bracket on the RHS is zero, so the overall remainder is the same as the remainder from dividing the digit sum by ten.

54.

(a) 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78.

(b) Combine two copies of the required sum. If we do this algebraically, we get

and observe that each of the n vertically aligned columns adds to n+1.

Hence

If we do the same geometrically, then we can combine two “staircases”

of dots (one of which is inverted) into an n by array of dots (either with n columns and dots in each column, or with columns and n dots in each column).

Note: The n^th triangular number is defined by the “formula”

But this “formula” has serious limitations: in particular, there is no way to calculate Tioo without first calculating T₁, then T₂, then T₃, ... all the way up to Tgg. Hence it is just a “recurrence relation”, which tells us how to find T_n once we know T_n-1 (just “add n”).

The formula

derived in part (b) is much more useful, in that it allows us to work out the value of T_n as soon as we know the value of n. This is what we call a “closed formula”. (The language may seem strange, but it refers to the fact that the calculation is direct, and that the formula involves a small, fixed number of operations – whereas using the recurrence requires more and more work as n gets larger.)

(c) Note: There are two reasons why these questions are worth asking. The first is that whenever we focus attention on certain special classes of objects, it is always good practice to consider whether the notions we have defined are completely separate, and to try to identify any overlaps. The second reason is less obvious, but can be surprisingly fruitful: sometimes two ideas may be interesting, yet have nothing to do with each other; but at other times, the two ideas may not only be interesting in their own right, but may “combine” in a way that gives rise to surprising subtleties. Here two of the combinations are routine and uninteresting; but two combinations generate more interesting mathematics than we have a right to expect.

(i) We know that one of the two factors n and in the numerator is odd, and the other is even. If the triangular number

is to be a power of 2, then any odd factor of T_n must be equal to 1, so does not give a power of 2. Hence , and is the only triangular number which is also a power of 2.

(ii) If the triangular number T_n is to be prime, then either

* n is odd and one of n, is equal to 1 (so and is not prime), or

* n is even and one of , is equal to 1, so , and is the only triangular number which is also prime.

(iii) The only immediately obvious “square triangular numbers T_n“ are the first and the eighth – namely and . But what seems obvious is rarely the whole truth. There are in fact infinitely many such “square triangular numbers” (e.g. , , , ...). This is a consequence of the formula in part (b). For example:

When n is even, we notice that and are integers with no common factors. We want their product to be a square. Because , this occurs precisely when both and are both squares. So we see that solutions correspond to pairs of integers b, c which satisfy the Pell equation . Notice that , is one solution, and that they satisfy the equation .

We have already met

as the norm (or square of the length) of the complex number (Problem 25). In a similar way, we can “factorise”

So once we have one solution of the equation , we can take powers to get more solutions:

Hence, for example,

gives rise to the solution , -- corresponding to , .

Similarly

gives rise to the solution , , corresponding to (), .

Note: If you are not yet familiar with complex numbers, or with the idea of a norm, don’t worry. Make a note of it as something that seems to be powerful and is worth learning. It will reappear later.

(iv) The only obvious cube triangular number is the first one – namely . Basic algebra leads quickly to an equation as in part (i):

which is equivalent to

So and are consecutive integers that are both proper powers. Catalan (1814–1894) conjectured in 1844 that and are the only consecutive powers (other than 0 and 1). This simple-sounding conjecture was finally proved only in 2004. It follows that is the only triangular number that is also a cube.

55.

(a)(i) 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89

(ii) 1, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34; 1, 1, 0, 1, 1, 2, 3, 5, 8, 13

(iii) m^th term of k^th sequence of differences

(b) (i) 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048

(ii) 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024; 1, 2, 4, 8, 16, 32, 64, 128, 256, 512

(iii) m^th term of k^th sequence of differences

56.

(a) (i) 1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, ...

(ii) .

When , the first factor on the RHS (, so

[Alternatively:

(b) (i) 0, 1, 2, 4, 7, 12, 20, 33, 54, 88, ...

(ii)

Claim:

holds for all .

Proof: When , the .

We proved the next few case , , above.

Suppose we have already proved the required relation holds all the way up to the equation:

Then the equation follows like this:

So we have shown

* that the identity holds for the first few values, and

* that whenever we know it is true up to the identity, it also holds for the identity.

Hence the identity holds for all                    QED

Alternatively:

Note: In 56(a)(ii) we appealed directly to the factorisation of as though this were a “known fact” which is easy to prove. And in the “alternative” proof, we repeatedly combined ““ to make , inserting dots “... “ to indicate that this replacement operation is repeated times. Both of these involved thinly veiled applications of the principle of Mathematical Induction, which is addressed in detail in Chapter 6. In 56(b)(ii) we had no way of concealing the use of “proof by Mathematical Induction “, which is likely to be lurking whenever we have

a proposition, or statement, P(n) involving the parameter n and

and

we wish to prove the infinite collection of assertions:

“P(n) is true for every ”

The standard way of achieving this apparent miracle of proving infinitely many things at once is:

to check that holds (that is, to check that is true when );

then

to suppose that we have checked all of the instances P(1), P(2), …, up to P(k) for some ,

and

to show that the next instance must then also be true.

We then conclude that P(n) is true for all .

57.

(a) (i) 0, 2, 3, 10, 24, 65, 168, ...

(ii) Guess:

Proof: By part (i), this identity holds for .

Suppose we have checked it as far as the instance:

Then the next instance follows, since

So we have shown that the identity holds for the first few values of n, and whenever we know it is true up to the k^th identity, it also holds for the identity. Hence the identity holds for all .                   QED

(b)(i) We suppose that

(if the inequality is reversed, the expression for the area is multiplied by “−1”).

The lines , , , form a rectangle of area , which surrounds the parallelogram.

To get from this to the area of the parallelogram, we must subtract

* the two external corner rectangles (top left, and bottom right) – each of area bc; and

* the four external right angled triangles–which fit together in pairs to make rectangles of areas ab and cd. Hence

(ii) 1

(iii) Half of the 2^nd parallelogram is equal to half of the 1^st – so both have the same area, namely 1.

Half of the 3^rd parallelogram is equal to half of the 2^nd – so they both have the same area, namely 1.

And so on. Hence the area of the n^th parallelogram is equal to

Part (a)(ii) is more precise in that it says that : this says that the relative positions of the generators (a, b), (c, d) for successive Fibonacci parallelograms alternate, with first , and then . (In fact the gradient of successive versions of the line OA, or the ratio of successive Fibonacci numbers, converges to the Golden Ratio , with successive Fibonacci points alternately above and below the line with equation .)

58.

(a) 1, 2, 5, 13, 34, ...

(b) Guess:

Note: When part (a) gives rise unexpectedly to “the odd-numbered terms of the Fibonacci sequence”, it is almost impossible to believe that this is an accident. Yet the attempt to prove that this “Guess” is correct may well prove elusive – for it is hard to see how to relate the and terms to the term.

One approach is to

“try to prove something stronger than what seems to be required”.

Claim: For each , both of the following are true:

Proof: We have already checked that the first relation holds for n = 1,2, 3,4, 5.

And it is easy to check that

So both identities hold for the first few values of n.

Now suppose we have checked that both relations hold all the way up to the pair of relations.

Then simply adding the two relations in the pair gives the first relation of the next pair:

To see that the second relation of the next pair also follows, consider

So we have shown

– that the identities hold for the first few values of n, and

– that whenever we know the k^th pair of identities hold, the pair also hold.

Hence the two identities hold for all .                   QED

59.

(a) (i) 0, 5, 8, 26, 63,...

(ii) Guess: .

Proof: By part (i), this identity holds for n = 2, 3,4, 5, 6.

Suppose we have checked it as far as the k^th instance:

Then the next instance follows using 57, since

(b) (i) 0,13, 21, 68,...

(ii) Guess:

This suggests that we should reinterpret our previous guesses, and that the “correction terms” on the RHS:

* in Problem 57(a) should have been written as “”,

* in Problem 57(a)(ii) should have been written as ““, and

* in Problem 59(a)(ii) should have been written as “”.

We leave the proof (or otherwise) of this conjecture as an exercise for the reader.

60.

(i) 10%

(ii) 21% – notice that

(iii) 0% – notice that

61. If x is doubled in the expression “x”, then the value of the expression doubles.

If y is doubled in the expression , then the value of the expression is halved.

If z is doubled in the expression , then the bracket is halved, and the expression is doubled.

Replacing “x, y, z” by “d, e, f” we see that, if the value of f is doubled, the value of the bracket is also doubled.

If we now take , , , then, when f is doubled, z is doubled, and the value of is doubled.

Hence the value of the whole expression

is halved.

62.

(a) The fact that one can add the entries in any order depends on the commutative and associative laws of addition. Expressing the subtotal in the second row as uses the distributive law. And expressing the overall sum

as uses the distributive law again.

(b) (i) , , , .

(ii) . Similarly, the k^th reverse L-shape has sum

Hence

63.

(a) The terms are , , , etc,; so the term is r(r+1), and the last term is .

The term can be expressed as “”, so the sum

can be expressed as

(b) (i) * .

* .

* .

Guess: .

Proof: This is true for .

Suppose we have checked the claim for all values up to

Then

Hence our guess is true for all .

(ii)

so

64. If one tries to apply the usual algorithms for decimals, then one is likely to get in something of a mess. But if we re-interpret each decimal as a fraction, then things are much easier.

(a) .

(b) ; .

(c)

(d) .

(e) .

65.

(a) Such a decimal is by definition equal to the fraction with numerator

(an integer with decimal digits) and with and denominator 10^k.

(b) If is equivalent to a fraction with numerator

and denominator 10^k, then m has decimal representation

(c) Parts (a) and (b) show that fractions with , whose decimals terminate are precisely those which are equivalent to fractions having denominator a power of 10: that is, those for which the denominator q is a factor of some integer of the form .

(d) If q does not divide some power of 10, then its decimal does not terminate. Hence, when carrying out the division of p by q we never get remainder 0. So the only possible remainders are 1, 2,... ,q — 1. The first remainder after the decimal point is equal to p (mod q)). In the ensuing q decimal places, there are just q – 1 distinct possible remainders, so some remainder (say r) must occur for the second time by the q^th step, and the outputs (and remainders) thereafter will then be the same as they were the first time that the remainder r occurred.

(e) Suppose d has a decimal with a repeating block of length b starting in the decimal place. (e.g. has , ). Then the infinite decimal tails cancel when we subtract , and the difference M becomes an integer N if we multiply by . Hence , and d is equal to a fraction with denominator .

66.

(a) (i) ; (ii) ; (iii)

(b) (i) ; (ii) ; (iii)

67.

(a) (block length 1); (block length 1)

(b) All have block length 6:

Note: The repeating blocks are all cyclically related: e.g. the block for is the same as for , but starting at “2” instead of at “1”.

(c) All have block length 2:

Note: The repeating blocks are not all cyclically the same, but fall into five pairs:

– and are cyclically related;

– as are those for and ;

– and those for and ;

– and those for and ;

– and those for and .

(d) All have block length 6.

Note: They fall into two families of six, where each family is cyclically related :

and

68.

(a) Does not recur. (If it did, it would have a recurring block of length b say. But by the time the counting sequence 1, 2, 3,. .. reaches 10^2b the decimal will contain a periodic block of 2b zeros, so the recurring block must consist of 0s, in which case the decimal terminates.)

(b) Does not recur. (Similar to part (a).)

(c) Does not recur. (If it did recur, then would be a rational number: see Problems 267, 268, 270.)

69. Claim Decimal fractions have two decimal representations. All other numbers have exactly one decimal representation.

Proof: Every “decimal fraction” (that is, any fraction which can be written with denominator a power of 10) has two representations – one that terminates and one that ends with an endless string of 9s: if the last non-zero digit of the terminating decimal is k, then the second representation of the same number is obtained by changing the “k” to “k — 1” and following it with an endless string of 9s.

Consider an unknown number with two different decimal representations and . Since they are “different”, and must differ in at least one position. Suppose the first, or left-most, position in which they differ is that in the decimal place (corresponding to ), and that the two digits in that position are (for ) and (for ).

We may suppose that . Then (otherwise , and , so ).

Moreover, since is not larger than , the digits following must all be equal to 0, and the digits following must all be equal to 9.                   QED

70. In case (d), A only has to choose a recurring block (such as ““, or ““, or ““) for his/her positions – no matter where they are. B’s control terminates at some stage, after which A’s recurring block guarantees that the resulting number is rational.

The other parts all offer a guaranteed strategy for B. Let the positions chosen by B be numbered

Now exploit the fact that the positive rationals are countable – that is, can be included in a single list. To see this we can use Cantor’s (1845-1918) diagonal enumeration

which lists all rationals with

• first those with ,
• then those with ,
• then those with ,

and so on.

All B needs to do is to make sure that the resulting decimal is not the decimal of any number in this list, and s/he can do this by choosing a digit in the position which is different from the digit which the k^th rational in the above list has in that position. The resulting real number is then different from every number in the list – and hence must be irrational.

71.

(a) 101 010 (in each column (i) , (ii) , (iii) “0 and carry 1”).

(b) (i) 1010100 (ii) 101010 (iii) 101010

(c) 2

Note: Trying to do this should make it clear how easily we confound “the fourteenth positive integer” with its familiar base 10 representation. It takes time and effort to learn to see “14_base 10” as “2 × 7”, and “21_base 10” as 3 × 7, and hence to spot the common multiple “42_{base 10}“. In base 2 the same numbers evoke no such familiar echoes.

72. Let .

(i) N is divisible by 2 precisely when the units digit is equal to 0.

(ii) N is divisible by 3 precisely when the alternating sum

is divisible by 3.

Proof

For each odd suffix m, increase the coefficient 2m by 1: then

has 3 as a factor.

For each even suffix , decrease the coefficient by 1: then

has 3 as a factor.

Hence

(iii) N is divisible by 4 precisely when the last two digits a₁ and a₀ are both equal to 0.

(iv) N is divisible by 5 precisely when the alternating sum

is divisible by 5.

Proof:

73.

(a) To weigh an object with weight 1, we must have w₀ = 1.

To weigh an object with weight 2, we must have w₁ = 2. We can then weigh any object of weight 3, but not one of weight 4.

(i) Now assume each positive weight w can be balanced in exactly one way. Then we cannot have w₂ = 3, so w₂ = 4.

Suppose that, continuing in this way, we have deduced that for each .

Then the binary numeral system reveals precisely that every weight w from 0 up to

can be uniquely represented, but cannot. Hence

The result follows by induction.

(ii) If the representation of each integer is not unique, then the sequence

need not include the powers of 2. For example, it could begin

(b) If each integer w is to be weighed in this way, then w has to be represented in the form

where each coefficient (if the weight is not used to weigh w), or = 1 (if the weight is used to balance w), or = −1 (if the weight is used to supplement w).

If each representation is to be unique, then one can prove as in (a)(i) that the sequence of weights must be the successive powers of 3.

74. Write m in “base 2”:

where each or 1. Then

That is,

75. We give an example, starting with .

Write N, and pair off the digits, starting at the units digit.

1 || 10 || 11 || 10 || 01

The left-most digit stands for 2⁸, so the square root is at least 2⁴ (and less than 2⁵). Hence the required square root has five digits (one for each “pair” of digits of N), and starts with a 1.

Root 1 || ? || ? || ? || ?

[We can also see that the final units digit will have to be a “1”. But this is not the time to add such information.]

Let x = 10 000, and subtract x² = 100 000 000 from N:

1 00 00 00 00
|| 10 || 11 || 10 || 01

This residue has to be equal to “”. However, as with long division, our immediate interest is in determining the next digit of our “partial square root”.

If the next digit is a 1 (contributing ), then , which would spill over and change the digit we have already determined. Hence the next digit is a 0.

Root 1 || 0 || ? || ? || ?

So we can again let x = 10 000 giving the same remainder, which has to be equal to ““, but this time has at most three digits.

The remainder

|| 10 || 11 || 10 || 01

is greater than , so and the next digit must be a “1”.

Root 1 || 0 || 1 || ? || ?

Now let , and subtract from N, leaving

|| 10 || 0 || 01

This residue has to equal , with .

If the next digit in the square root is 1, then .

Hence the next digit is 0, and the last digit is then 1.

Hence the required square root is equal to:

Root 1 || 0 || 1 || 0 || 1

76.

(b)(i) The fact that

says that

“ is equal to a multiple of with remainder = 1”.

(c)(i) The fact that

says that

“ is equal to a multiple of with remainder = 1”.

and that

“ is equal to a multiple of with remainder = 1”.

Hence neither p₁ nor p₂ are factors of n₂.

(d) The fact that

says that

“ is equal to a multiple of with remainder = 1”

for each suffix i, . Hence none of the primes is a factor of .

So the smallest prime factor of n_k always gives us a new prime .

(e) If we start with , then , so .

Then , so .

Then , so .

Then , so .

77.

(a) We write for the “first integer ”. Then

(b) The initial “doubling” is an accident of small numbers, which soon turns into “slightly more than doubling”.

The observation that should (eventually) jump out at you concerns the ratio , which seems to be surprisingly close to N − 1. This suggests the possible

Conjecture: (where ).