Library / Estonian Math Competitions /80 of 148

Estonian Math Competitions

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,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

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