Divisibility tests and proofs

5 For integers \(a\) and \(b\), with \(a \geqslant 0\) and \(0 \leqslant b \leqslant 99\), the numbers \(M\) and \(N\) are such that $$M = 100 a + b \text { and } N = a - 9 b .$$

1. By considering the number \(M + 2 N\), show that \(17 \mid M\) if and only if \(17 \mid N\).
2. Demonstrate step-by-step how an algorithm based on the result of part (i) can be used to show that 2058376813901 is a multiple of 17 .

4 Let \(\mathrm { N } = 10 \mathrm { a } + \mathrm { b }\) and \(\mathrm { M } = \mathrm { a } + 3 \mathrm {~b}\), where \(a\) and \(b\) are integers such that \(a \geqslant 1\) and \(0 \leqslant b \leqslant 9\).

1. Prove that \(29 \mid N\) if and only if \(29 \mid M\).
2. Use an iterative method based on the result of part (a) to show that 899364472 is a multiple of 29 .

3 In this question, \(N\) is the number 26132652.

1. Without dividing \(N\) by 13, explain why 13 is a factor of \(N\).
2. Use standard divisibility tests to show that 36 is a factor of \(N\). It is given that \(N = 36 \times 725907\).
3. Use the results of parts (a) and (b) to deduce that 13 is a factor of 725907.

4 Let \(N\) be the number 15824578 .

1. 1. Use a standard divisibility test to show that \(N\) is a multiple of 11 .
   2. A student uses the following test for divisibility by 7 . \begin{displayquote} 'Throw away' multiples of 7 that appear either individually or within a pair of consecutive digits of the test number.
      Stop when the number obtained is \(0,1,2,3,4,5\) or 6 .
      The test number is only divisible by 7 if that obtained number is 0 . \end{displayquote} For example, for the number \(N\), they first 'throw away' the " 7 " in the tens column, leaving the number \(N _ { 1 } = 15824508\). At the second stage, they 'throw away' the " 14 " from the left-hand pair of digits of \(N _ { 1 }\), leaving \(N _ { 2 } = 01824508\); and so on, until a number is obtained which is \(0,1,2,3,4,5\) or 6 .
      • Justify the validity of this process.
2. Continue the student's test to show that \(7 \mid N\).
   (iii) Given that \(N = 11 \times 1438598\), explain why 7| 1438598 .
3. Let \(\mathrm { M } = \mathrm { N } ^ { 2 }\).
   1. Express \(N\) in the unique form 101a + b for positive integers \(a\) and \(b\), with \(0 \leqslant b < 101\).
   2. Hence write \(M\) in the form \(\mathrm { M } \equiv \mathrm { r } ( \bmod 101 )\), where \(0 < r < 101\).
   3. Deduce the order of \(N\) modulo 101.

1

1. The number \(N\) has the base-10 form \(\mathrm { N } = \operatorname { abba } a b b a \ldots a b b a\), consisting of blocks of four digits, as shown, where \(a\) and \(b\) are integers such that \(1 \leqslant a < 10\) and \(0 \leqslant b < 10\). Use a standard divisibility test to show that \(N\) is always divisible by 11 .
2. The number \(M\) has the base- \(n\) form \(\mathrm { M } = \operatorname { cddc } c d d c \ldots c d d c\), where \(n > 11\) and \(c\) and \(d\) are integers such that \(1 \leqslant \mathrm { c } < \mathrm { n }\) and \(0 \leqslant \mathrm {~d} < \mathrm { n }\). Show that \(M\) is always divisible by a number of the form \(\mathrm { k } _ { 1 } \mathrm { n } + \mathrm { k } _ { 2 }\), where \(k _ { 1 }\) and \(k _ { 2 }\) are integers to be determined.

1. In this question you must show detailed reasoning.

Without performing any division, explain why \(n = 20210520\) is divisible by 66

1 Use standard divisibility tests to show that the number $$N = 91039173588$$

• is divisible by 9
• is divisible by 11
• is not divisible by 8 .