Track / Stage 6 / 94 of 400 #1094 of 2000

Problem 1094

National olympiad, first round

Number theory Difficulty 6.1 Prove it

\section*{Exercise 3A - 291043A}

Prove the following statement:

The sequence $(2 n-1)(n=1,2,3, \ldots)$ contains, for any arbitrary number $z$ , a segment whose length is greater than $z$ and in which no prime number occurs.

Hint:

If $\left(a_{n}\right)(n=1,2,3, \ldots)$ is a sequence and $k \geq 1$ and $m$ are natural numbers, then the $k$ -tuple $\left(a_{m+1}, a_{m+2}, \ldots, a_{m+k}\right)$ is called a segment of the sequence $\left(a_{n}\right)$ and $k$ is its length.

This one wants a proof. Work it on paper, read the official solution, then mark yourself honestly — the ladder only means something if the record is true.

Official solution

}

1. For every natural number $n$ : If $n$ is composite, then $2^{n}-1$ is not a prime number.

Proof: Let $n=p q$ with natural numbers $p, q>1$ . Then, with $x=2^{p}$ , the number

$2^{n}-1=x^{q}-1=(x-1)\left(x^{q-1}+\ldots+x+1\right)$

is composite because $x+1>1$ and $x^{q-1}+\ldots+x+1 \geq x+1>1$ . 2. For every natural number $N>1$ , none of the $N-1$ numbers

$n \in\{N!+2 ; N!+3 ; \ldots ; N!+N\}$

is a prime number, because these numbers are each divisible by $2,3, \ldots, N$ and are greater than the mentioned divisors. If one chooses an $N>1$ with $N>z+1$ , then the segment of the sequence elements $2^{n}-1$ formed with the numbers $n$ from (1) has the length $N-1>z$ and, due to 1., there is no prime number in this segment.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.