For all $n\in\mathbb{N}$ with $n>1$ there exists an $m\in\mathbb{N}$ with $mI was using Python to explore some interesting lexicographically earliest sequences. I was looking into the sequence of numbers such that $a(1)=1$ and $a(n)$ is the smallest number such that $a(k)n+1$ is not prime for any $k<n$. 
After computing this sequence, it appeared to be exactly the odd integers. The absence of even integers interested me, as that suggested that for every even integer $n$ there exists an odd $m<n$ such that $mn+1$ is prime. After checking with Mathematica, this appeared to be true. In fact, this suggested the more general conjecture in the title: 
For all $n\in\mathbb{N}$ with $n>1$ there exists an $m\in\mathbb{N}$ with $m<n$ such that $mn+1$ is prime.
This doesn't sound too difficult, but then again there are plenty of nice-sounding prime conjectures that remain unsolved, so this could be one of those.
How could this be proven? And if its unsolved / really difficult, what is the name of the conjecture?

See https://en.wikipedia.org/wiki/Linnik%27s_theorem for some bounds on $a(n)$. It is not exactly what you want but at least it's a start.
