Does anyone have an idea on how to prove this?
"There is no strictly monotonically increasing arithmetic sequence in which all elements are primes."
Any help appreciated! Thanks:)
Asked
Active
Viewed 142 times
3
-
1Well, write what it means to be a monotonically increasing arithmetic sequence. – Thomas Andrews Sep 17 '13 at 17:16
3 Answers
3
If $p$ is a polynomial with integer coefficients, and $k$ divides $p(n)$, then $k$ divides $p(mk+n)$ for any $m$.
In particular, this applies to $p$ a linear polynomial. Now note that terms in arithmetic progression are the consecutive values of a linear polynomial with integer coefficients: $a,a+b,a+2b,\dots$ are $p(0),p(1),\dots$ for $p(x)=a+xb$.
Andrés E. Caicedo
- 79,201
-
That sounds good, but how do I know that there is an element in the sequence that's equal to p(mk + n)? – nitrogenhurricane Sep 17 '13 at 17:21
-
-
In case you are confused about this: For any $N$, no matter how large, there is a strictly increasing arithmetic progression of length $N$ consisting solely of primes. The question is about infinite sequences, so no matter how large $k,n,m$ are, the sequence has an $(mk+n)$-th term. – Andrés E. Caicedo Sep 17 '13 at 17:25
-
Okay, it's clear now thanks, I just couldn't put the existence of element and that k divides it together:) Thanks! – nitrogenhurricane Sep 17 '13 at 17:26
2
Suppose the first term in the sequence is prime $p$. Then the $(p+1)$th term in the sequence is $p + pn$ for some positive integer $n$, since by assumption your sequence must be all integer-valued if it's all prime. Can this term $p + pn$ be prime?
user2566092
- 26,142
-
@nitrogenhurricane, in this answer the difference between two elements is $n$, not $p$. – Antonio Vargas Sep 17 '13 at 17:54
1
Consider the arithmetic sequence $a,a+d,a+2d,a+3d,\dots$. The sequence is increasing, so for some $k$ we have $a+kd\gt 1$.
Now consider $(a+kd)+ (a+kd)d$. This is in the sequence, for $$(a+kd)+(a+kd)d= a+(k+a+kd)d.$$ But $(a+kd)+(a+kd)d$ is not prime, since it is clearly divisible by $a+kd$, and greater than $a+kd$.
André Nicolas
- 507,029
-
Thanks for your answer, but as Andres was faster I think, so it's fair to accept his. Please anyone correct me if I'm wrong since I'm a newbie here. – nitrogenhurricane Sep 17 '13 at 17:27
-
In my opinion the solution by user2566092 is much cleaner and better. Mine is essentially the same, but hides the simplicity of the idea. So I think you should not accept mine. – André Nicolas Sep 17 '13 at 17:31
-
You should accept whichever answer you think best answers the question. It's okay for this to be a late answer (it's even okay to change your mind) – Ben Millwood Sep 17 '13 at 17:32