8.02b Divisibility tests: standard tests for 2, 3, 4, 5, 8, 9, 11

1 In decimal (base 10) form, the number \(N\) is 15260.

1. Express \(N\) in binary (base 2) form.
2. Using the binary form of \(N\), show that \(N\) is divisible by 7 .

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.
      • Continue the student's test to show that \(7 \mid N\).
        (iii) Given that \(N = 11 \times 1438598\), explain why 7| 1438598 .
      • 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. (i) Determine all the possible integers \(a\), where \(a > 3\), such that

$$15 \equiv 3 \bmod a$$ (ii) Show that if \(p\) is prime, \(x\) is an integer and \(x ^ { 2 } \equiv 1 \bmod p\) then either $$x \equiv 1 \bmod p \quad \text { or } \quad x \equiv - 1 \bmod p$$ (iii) A company has \(\pounds 13940220\) to share between 11 charities. Without performing any division and showing all your working, decide if it is possible to share this money equally between the 11 charities.

1. 1. Making your reasoning clear and using modulo arithmetic, show that

$$214 ^ { 6 } \text { is divisible by } 8$$ (ii) The following 7-digit number has four unknown digits $$a 5 \square b \square a b 0$$ Given that the number is divisible by 11

1. determine the value of the digit \(a\). Given that the number is also divisible by 3
2. determine the possible values of the digit \(b\).

1. (i) Without performing any division, explain why 8184 is divisible by 6
   (ii) Use the Euclidean algorithm to find integers \(a\) and \(b\) such that

$$27 a + 31 b = 1$$

1. In this question you must show detailed reasoning.

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

1. 1. The polynomial \(\mathrm { F } ( x )\) is a quartic such that

$$\mathrm { F } ( x ) = p x ^ { 4 } + q x ^ { 3 } + 2 x ^ { 2 } + r x + s$$ where \(p , q , r\) and \(s\) are distinct constants.
Determine the number of possible quartics given that

1. the constants \(p , q , r\) and \(s\) belong to the set \(\{ - 4 , - 2,1,3,5 \}\)
2. the constants \(p , q , r\) and \(s\) belong to the set \(\{ - 4 , - 2,0,1,3,5 \}\) (ii) A 3-digit positive integer \(N = a b c\) has the following properties
   • \(N\) is divisible by 11
   • the sum of the digits of \(N\) is even
   • \(N \equiv 8 \bmod 9\)
   • Use the first two properties to show that
   $$a - b + c = 0$$
3. Hence determine all possible integers \(N\), showing all your working and reasoning.

4

1. (a) Find all the quadratic residues modulo 11.
   (b) Prove that the equation \(y ^ { 5 } = x ^ { 2 } + 2017\) has no solution in integers \(x\) and \(y\).
2. In this question you must show detailed reasoning. The numbers \(M\) and \(N\) are given by $$M = 11 ^ { 12 } - 1 \text { and } N = 3 ^ { 2 } \times 5 \times 7 \times 13 \times 61$$ Prove that \(M\) is divisible by \(N\).

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 .

7

1. Let \(f ( n ) = 2 ^ { 4 n + 3 } + 3 ^ { 3 n + 1 }\). Use arithmetic modulo 11 to prove that \(\mathrm { f } ( n ) \equiv 0 ( \bmod 11 )\) for all integers \(n \geqslant 0\).
2. Use the standard test for divisibility by 11 to prove the following statements.
   1. \(10 ^ { 33 } + 1\) is divisible by 11
   2. \(10 ^ { 33 } + 1\) is divisible by 121