Competition problem — Number theory

Library / /84 of 158

Number theory Difficulty 5.8 AIME, harder Prove it Estonia

Let $n$ be a natural number such that $n + 1$ , $n + 3$ , $n + 7$ and $n + 9$ are prime numbers, and $n + 31$ , $n + 33$ , $n + 37$ and $n + 39$ are also prime numbers. Find the remainder of $n$ divided by 210.

Solution

Consider the remainders of $n$ when divided by 2, 3, 5, and 7. In the following tables the left column shows the remainder and the right column shows, which of the given eight numbers cannot be prime, if $n \ge 7$ :

n mod 2	divisible by 2	n mod 3	divisible by 3
1	$n + 1$	0	$n + 3$
		2	$n + 1$

n mod 5	divisible by 5	n mod 7	divisible by 7
1	$n + 9$	0	$n + 7$
2	$n + 3$	2	$n + 33$
3	$n + 7$	3	$n + 39$
4	$n + 1$	4	$n + 3$
		5	$n + 9$
		6	$n + 1$

Thus if

n \ge 7

then the remainder of

n

when divided by 2 and 5 is 0 and when divided by 3 and 7 is 1; hence

n - 1

is a multiple of 3 and 7. Consequently

n

is a multiple of 10 and

n - 1

is a multiple of 21. This implies that

n + 20

is a multiple of 21 and a multiple of 10, hence a multiple of 210. Consequently the remainder of

n

when divided by 210 is 190. The numbers

n = 1, 2, 3, 4, 5, 6

do not satisfy the conditions of the problem.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.