Applications: Number Theory

The days of the week repeat every 7 days and a 12-hour clock repeats every 12 hours. A whole number of full cycles brings the position back to where it started, so only the remainder after division by the length of the cycle matters. This is arithmetic modulo 7 and modulo 12.

1. The days of the week repeat every 7 days, so 7 days after a Wednesday is a Wednesday again. Only the remainder when 100 is divided by 7 changes the day.
2. Divide 100 by 7: 14 × 7 = 98, so 100 = 14 × 7 + 2. The 14 full weeks bring the ship back to a Wednesday, and 2 days are left over.
3. (a) Count 2 days on from Wednesday: Thursday, Friday. The ship arrives on a Friday.
4. A 12-hour clock repeats every 12 hours. Divide 50 by 12: 4 × 12 = 48, so 50 = 4 × 12 + 2. The 4 full turns of the hour hand change nothing, and 2 hours are left over.
5. (b) 9 + 2 = 11, so the clock shows 11 o'clock. Check: 9 + 50 = 59 and 59 = 4 × 12 + 11, which also gives 11 o'clock.

answer(a) Friday, because 100 = 14 × 7 + 2; (b) 11 o'clock

techniqueModular Arithmetic on a Clock Face

Write each digit over its weight, add the products that are known, and use a letter for the digit that is not known. A digit is one of 0 to 9, so the weighted sum can only lie in a short range, and only one multiple of 11 in that range can be reached.

1. Multiply each known digit by its weight and add: 6 × 4 + 5 × 0 + 4 × 7 + 3 × 3 + 2 × 5 = 24 + 0 + 28 + 9 + 10 = 71.
2. Let the check digit be c. Its weight is 1, so the weighted sum is 71 + c. Since c is a digit from 0 to 9, the sum lies from 71 to 80. The only multiple of 11 in that range is 77.
3. (a) 71 + c = 77, so c = 6. The full code is 407356.
4. Let the smudged digit be x. Its weight is 4, so the weighted sum is 6 × 2 + 5 × 5 + 4x + 3 × 1 + 2 × 8 + 1 × 4 = 12 + 25 + 4x + 3 + 16 + 4 = 60 + 4x.
5. Since x is a digit from 0 to 9, the sum lies from 60 to 96. The multiples of 11 in that range are 66, 77 and 88, which need 4x = 6, 4x = 17 or 4x = 28. Only 28 is a multiple of 4.
6. (b) 4x = 28, so x = 7. Check: 12 + 25 + 28 + 3 + 16 + 4 = 88 = 8 × 11.

answer(a) 6, which makes the weighted sum 77; (b) 7, which makes the weighted sum 88

techniqueModular Arithmetic on a Clock Face · Casting Out Nines to Check Arithmetic

examsGCSE Higher

Each of 10, 100, 1000 and so on leaves a remainder of 1 when it is divided by 9. So a number leaves the same remainder as the sum of its digits. Adding the digits again and again until one digit is left gives the digital root. The digital root of a product must agree with the product of the digital roots.

1. Reduce each factor to its digital root. For 347: 3 + 4 + 7 = 14 and 1 + 4 = 5. For 286: 2 + 8 + 6 = 16 and 1 + 6 = 7.
2. Multiply the digital roots and reduce again: 5 × 7 = 35 and 3 + 5 = 8. The correct product must have a digital root of 8.
3. (a) For 99242: 9 + 9 + 2 + 4 + 2 = 26 and 2 + 6 = 8, which agrees. For 99142: 9 + 9 + 1 + 4 + 2 = 25 and 2 + 5 = 7, which does not agree. So 99142 is wrong.
4. The number 92942 has the same digits as 99242 in a different order. Its digit sum is still 9 + 2 + 9 + 4 + 2 = 26, and its digital root is still 8. It passes the check, although it is not the product.
5. (b) No. Changing the places of two digits does not change the digit sum, so the digital root stays 8. The error is 99242 − 92942 = 6300 = 9 × 700, a multiple of 9, and casting out nines cannot see an error that is a multiple of 9.

answer(a) 99142 is wrong: its digital root is 7, and the product must have a digital root of 8; (b) no: 92942 still has the digit sum 26 and the digital root 8, because changing the places of two digits does not change the digit sum

techniqueCasting Out Nines to Check Arithmetic · Modular Arithmetic on a Clock Face

examsGCSE Higher

A terminating decimal is a fraction whose denominator is a power of 10, and 10 = 2 × 5. So a fraction in its lowest terms terminates exactly when the only prime factors of its denominator are 2 and 5. Any other prime factor can never be turned into a power of 10, and the decimal recurs.

1. Check that each fraction is in its lowest terms, then write each denominator as a product of prime factors: 40 = 2³ × 5, 12 = 2² × 3, 625 = 5⁴ and 15 = 3 × 5.
2. (a) The denominators 40 and 625 have no prime factors other than 2 and 5, so 740 and 9625 terminate. The denominators 12 and 15 have the prime factor 3, so 512 and 415 recur.
3. For 740, make the denominator a power of 10. Since 40 = 2³ × 5, two more factors of 5 are needed: 7 × 2540 × 25 = 1751000 = 0.175.
4. For 9625, four factors of 2 are needed, because 625 = 5⁴: 9 × 16625 × 16 = 14410000 = 0.0144.
5. (b) The number of decimal places is the larger of the two indices of 2 and 5 in the denominator: 0.175 has 3 decimal places and 0.0144 has 4. Check by division: 512 = 0.41666… and 415 = 0.2666…, which both recur.

answer(a) 740 and 9625 terminate, and 512 and 415 recur; (b) 740 = 0.175, with 3 decimal places, and 9625 = 0.0144, with 4 decimal places

techniqueWhy Every Fraction Terminates or Recurs

examsGCSE Higher

Two decimals with the same recurring part differ by a number whose decimal terminates. Multiplying by a power of 10 moves the digits without changing the recurring part, so a subtraction removes it and leaves an equation with whole numbers.

1. Let x = 0.272727… The repeating block has 2 digits, so multiply by 100 to move one full block: 100x = 27.272727…
2. Subtract x from 100x. The recurring parts are the same, so they cancel: 100x − x = 27.272727… − 0.272727…, which gives 99x = 27 and x = 2799.
3. (a) Divide the numerator and the denominator by 9: Aisha's share is 311. Check by long division of 3 by 11: the remainders are 3, 8, 3, 8 and so on, and the digits 2 and 7 repeat.
4. Let y = 0.1666… The digit 1 does not repeat, so two multiples are needed whose recurring parts are the same: 10y = 1.666… and 100y = 16.666…
5. (b) Subtract: 100y − 10y = 16.666… − 1.666…, which gives 90y = 15. So y = 1590 = 16, and Ben's share is 16. Check by long division of 1 by 6: the remainders are 1, 4, 4 and so on, and the digits are 1, then 6 repeating.

answer(a) 311; (b) 16

techniqueTurning Recurring Decimals into Fractions · Why Every Fraction Terminates or Recurs

examsGCSE Higher

A share of 5 loaves among 8 workers is 58 of a loaf. Written as unit fractions, the share becomes a few large pieces instead of many small ones, and every worker can see that all the shares are the same.

1. Each worker's share is 5 ÷ 8 = 58 of a loaf. A whole loaf is more than 58, and 12 = 48 is not more than 58, so the largest unit fraction that fits is 12.
2. Subtract it: 58 − 48 = 18. What is left is a unit fraction, so the method stops, and 58 = 12 + 18.
3. (a) Each worker receives half a loaf and one eighth of a loaf. Cut 4 loaves into halves to make 8 halves, and cut the fifth loaf into 8 eighths. Check: 4 + 1 = 5 loaves.
4. For 11 loaves among 12 workers the share is 1112. The largest unit fraction that fits is 12 = 612, and 1112 − 612 = 512 is left. Now 12 = 612 is too large, but 13 = 412 fits, and 512 − 412 = 112 is left.
5. (b) 1112 = 12 + 13 + 112. Cut 6 loaves into halves, 4 loaves into thirds and 1 loaf into twelfths, which makes 12 pieces of each size. Check: 6 + 4 + 1 = 11 loaves.

answer(a) 58 = 12 + 18: each worker receives half a loaf and one eighth of a loaf; (b) 1112 = 12 + 13 + 112: 6 loaves are cut into halves, 4 loaves into thirds and 1 loaf into twelfths

techniqueEgyptian Fractions and the Greedy Algorithm

A product of primes is a multiple of each of them, so one more than the product leaves a remainder of 1 for each. The new number has at least one prime factor, and that prime factor cannot be in the list. This is why no finite list of primes is ever complete.

1. N = 2 × 3 × 5 × 7 + 1 = 210 + 1 = 211. The number 210 is a multiple of each of 2, 3, 5 and 7, so 211 leaves a remainder of 1 when it is divided by any of them. No prime in the list divides N.
2. To decide whether 211 is prime, test the primes whose squares are not more than 211. Since 15² = 225 is more than 211, the primes to test are 2, 3, 5, 7, 11 and 13. The first four leave a remainder of 1, and 211 = 11 × 19 + 2 and 211 = 13 × 16 + 3.
3. (a) No prime up to 13 divides 211, so 211 is prime. It is a prime that is not in Mei's list.
4. For the longer list, 2 × 3 × 5 × 7 × 11 × 13 = 30030, so the new number is 30031. But 59 × 509 = 30031, so 30031 is not prime, and Mei's claim is false.
5. (b) Euclid's argument guarantees less than Mei claims, and it is still enough. Each of 2, 3, 5, 7, 11 and 13 leaves a remainder of 1 when it divides 30031, so every prime factor of 30031 is outside the list. The factors 59 and 509 are both prime, and both are new.

answer(a) 211 leaves a remainder of 1 when it is divided by each of 2, 3, 5 and 7, and it is prime; (b) the claim is false, because 30031 = 59 × 509, but 59 and 509 are primes that are not in the list

techniqueEuclid’s Proof That Primes Never Run Out

A continued fraction is found by dividing again and again: the whole part of each division is a term, and the fractional part is inverted and divided again. Stopping after the first few terms gives the convergents, which are the closest fractions to the number among all fractions with denominators of that size.

1. Write the ratio as a fraction in its lowest terms: 3.14 = 314100 = 15750. Divide: 157 = 3 × 50 + 7, so 15750 = 3 + 750. The first term is 3.
2. The fractional part 750 is 1 divided by 507. Divide again: 50 = 7 × 7 + 1, so 507 = 7 + 17, and the second term is 7. The last fractional part 17 is 1 divided by 7, so the third term is 7 and the division ends. The terms are 3, 7 and 7, written [3; 7, 7].
3. (a) Stop after each term in turn. The first convergent is 3. The second is 3 + 17 = 227. The third uses every term: 3 + 750 = 15750, the number itself.
4. Gears with 22 teeth and 7 teeth have fewer than 30 teeth each. Compare 227 with 15750 over the common denominator 350: 227 = 1100350 and 15750 = 1099350.
5. (b) The convergent 227 is 1100350 − 1099350 = 1350 more than 3.14. Check: 1350 is about 0.003, which is less than one thousandth of the ratio.

answer(a) 15750 = [3; 7, 7], and the convergents are 3, 227 and 15750; (b) 227, from gears with 22 teeth and 7 teeth, which is exactly 1350 more than 3.14

techniqueContinued Fractions

examsGCSE Higher

By Pythagoras' theorem the square of the diagonal is twice the square of the side. If both were whole numbers of tiles, the tile could be made as large as possible, so that a and b have no common factor. The even and odd argument then shows that a and b are both even, which cannot be.

1. Suppose a tiles fit along the side and b along the diagonal. Choose the largest tile that does this, so that a and b have no common factor. By Pythagoras' theorem, b² = a² + a² = 2a².
2. So b² is even. The square of an odd number is odd, so b is even. Write b = 2c. Then (2c)² = 2a², which is 4c² = 2a², so a² = 2c².
3. (a) Now a² is even, so a is even as well. Then a and b have the common factor 2, which contradicts the choice of the largest tile. So no tile fits both the side and the diagonal: ba = √2 is not a fraction.
4. (b) With a side of 12 tiles, the diagonal is d tiles, where d² = 2 × 12² = 288. Since 16² = 256 and 17² = 289, the diagonal lies between 16 and 17 tiles. It is 12√2 tiles exactly, and the last tile always has to be cut.

answer(a) It is impossible: b² = 2a² makes both a and b even, even after every common factor has been removed; (b) d² = 288, which lies between 16² = 256 and 17² = 289, so the diagonal is between 16 and 17 tiles long

techniqueThe Square Root of Two Is Irrational

The decimal 0.999… has nines that never end, and it is a second way of writing the number 1, just as 0.5 and 12 are two ways of writing one number. A calculator display is different: it ends after a fixed number of digits, so it shows slightly less than one third.

1. Let x = 0.999… Multiply by 10, which moves every digit one place: 10x = 9.999…
2. Subtract x from 10x. The recurring parts are the same, so they cancel: 10x − x = 9.999… − 0.999… = 9. So 9x = 9 and x = 1.
3. (a) 0.999… = 1 exactly, so the three pieces make 3 × 13 = 1 m and no ribbon is lost. A second reason: the difference 1 − 0.999… would have to be less than 0.1, less than 0.01, less than 0.001 and so on, and the only number that is not negative and is less than all of these is 0.
4. The calculator stops after 7 decimal places, so it shows 0.3333333, which is slightly less than 13. Multiply: 3 × 0.3333333 = 0.9999999.
5. (b) 1 − 0.9999999 = 0.0000001, so the product is 0.0000001 m less than 1 m. The difference comes from the digits that the display cut off, and not from the ribbon. With nines that never end, there is no difference at all.

answer(a) 9x = 9, so x = 0.999… = 1 exactly; (b) 3 × 0.3333333 = 0.9999999, which is 0.0000001 less than 1, because the display was cut off after 7 decimal places

techniqueWhy 0.999… Equals Exactly One · Turning Recurring Decimals into Fractions

examsGCSE Higher