Find all (finite) increasing arithmetic progressions, consisting only of prime numbers, such that the number of terms is larger than the common difference.
Problem
Source: Tournament of Towns 2007 - Spring - Junior A-Level - P5
Tags: number theory, prime numbers, number theory unsolved
05.09.2011 09:26
let be the progression $ a+r,a+2r,...,a+rx $. so $ x>r $. then we'll have a number divisible by $ r $. then $ r=1 $ and that means the progression is $ 2,3 $ or $ r=p=prime $ and all the numbers will be divisible by $ p $ so the progression is $ p $.
08.10.2013 11:46
No. For one thing, with $\gcd(r,a)=1$ (needed, since the terms are prime), no term will be divisible by $r$. Let $n$ be the number of terms and $r$ be the common difference. The examples $\{2,3\}$ with $n=2>1=r$, and $\{3,5,7\}$ with $n=3>2=r$, will be shown to be the only possible (and if we also consider progressions with only one term, also $\{p\}$, with $n=1>0=r$ and $p$ prime must be taken). By a theorem of Thébault (featured on AoPS), if $p_k < n \leq p_{k+1}$, then $r$ is divisible by all $p_i$, $1\leq i \leq k$; moreover, if $n=p_{k+1}$ we will also have $p_{k+1} \mid r$, unless the first term is precisely equal to $n$. But by Bertrand's postulate, if $k>2$ we will then have $r\geq p_1p_2\cdots p_k > 2p_k > p_{k+1} \geq n$, so we need $k\leq 2$. For $k=0$ we have $n=1$, leading to $\{p\}$, or $n=2$, leading to $\{2,3\}$. For $k=1$ we have $n=3$, leading to $\{3,5,7\}$.
18.08.2021 19:14
Thebault's Theorem:- An increasing arithmetic progression of length $n>2$ consists of prime numbers then the common difference if divisible by all the primes less than $n$ Suppose that $a,a+d......,a+(n-1)d$ is the required sequence,with $n-1>d$. By Thebault's Theorem,if $p_k \ge n \ge p_{k+1}$ then $\prod{p_i}|d$. So suppose that $\prod{p_i}>2$,then $\prod{p_k}-1 \ge p_{k+1}$ since $\prod{p_k}-1$ must have a prime factor which can't be $p_1,p_2,p_3...,p_k$.So if $\prod{p_i}>2$ then $\prod{p_k}>p_{k+1}$ which contradicts(since $\prod{p_k} \ge d <n \ge p_{k+1}$) hence $k=1$ and $n\le 3$.So for $n=3$ we have the sequence $(3,5,7)$ as a unique possibility. (all others are ruled out by congruencies)