Number theory

Let N = 10 a + b and M = a - 3 b, where a and b are positive integers and 0 ⩽ b ⩽ 9.

By considering 3 N + M, prove that 31 | N if and only if 31 | M.

Use a procedure based on the result of part (a) to show that 31 | 7 167 758.

Let f(n) denote the base-n number 2121_n where n ⩾ 3.

For each n ⩾ 3, show that f (n) can be written as the product of two positive integers

greater than 1, a (n) and b (n), each of which is a function of n.

Deduce that f (n) is always composite.

Let h be the highest common factor of a (n) and b (n).

Prove that h is either 1 or 5.

Find a value of n for which h = 5.

Consider the integers a and b, where, for each integer n, a = 7 n + 4 and b = 8 n + 5.

Let h = hcf (a, b).

Determine all possible values of h.

Find all values of n for which a and b are not co-prime.

Let N be the number 15 824 578.

Use a standard divisibility test to show that N is a multiple of 11.

A student uses the following test for divisibility by 7.

‘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.

For example, for the number N, they first ‘throw away’ the “7” in the tens column, leaving the number N₁ = 15824508. At the second stage, they ‘throw away’ the “14” from the left-hand pair of digits of N₁, leaving N₂ = 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 | N.

Given that N = 11 × 1438598, explain why 7 | 1438598.

Let M = N².

Express N in the unique form 101 a + b for positive integers a and b, with 0 ⩽ b < 101.

Hence write M in the form M ≡ r (mod 101), where 0 < r < 101.

Deduce the order of N modulo 101.

In this question you must show detailed reasoning.

Express the number 41723₁₀ in hexadecimal (base 16).