I was playing with the rules of Rowland's prime-generating sequence to learn how it works, and doing some tests I noticed that the following condition works as a primality condition, probably it is very easy to prove but I can not see the reason why it works:
$$p \ge 5 \in \Bbb P \Leftrightarrow \gcd(k,p+k)=1\ \forall k \in [3..p-1]$$
For instance $11$ is prime because for the intervals $[3,10]$ and $[14,21]$ holds: $$\gcd(3,14)=1,\gcd(4,15)=1,...,\gcd(10,21)=1$$
And for instance $25$ is not prime because $\gcd(3,28)=1,\gcd(4,29)=1$ (up to that point is fine) but then $\gcd(5,30)=5$, not $1$, so $25$ is not prime.
I would like to ask the following questions:
Is that observation correct or there is a counterexample?
What property of the prime numbers is behind that rule? I am sure this is quite simple but I really do not see it. Thank you!
In general, $\gcd(x,y)=\gcd(x,y-x)$ (this fact is the basis for the Euclidean algorithm). In particular, $\gcd(k,p+k)=\gcd(k,p)$. So your condition is just saying that no $k$ between $3$ and $p-1$ has a nontrivial common factor with $p$. If $p$ is prime, this is obviously true. Conversely, if your condition holds, then $p$ cannot have any factors between $3$ and $p-1$. The only nontrivial factor $p$ could have is $2$, but then $p/2$ is also a factor, so this is only possible if $p/2=2$ or $p/2=1$, which contradicts your assumption that $p\geq 5$.
More generally, by a similar argument, if $p>n^2$, then $\gcd(k,p+k)=1$ for $k=n,\dots,p-1$ iff $p$ is prime.