I'm working on disproving this statement but am having an issue figuring out where to start. I considered splitting it into cases, but so far from that I've only been able to prove the parity of the value, not whether it's composite or prime.
Any hints on how to outline this proof?
This statement is false. Let $n = a+2$, then $$na+1 = (a+2)a+1 = (a+1)^2$$
which is not a prime.
This problem was probably given to you as practice for negating statements which include quantifiers. The statement has the form:
$$ \exists a \mbox{ such that } \forall n \mbox{ Statement} $$
To negate it, you want to prove:
$$ \forall a \exists n \mbox{ such that } \mbox{ NOT Statement} $$
So the proof will start: Let $a$ be given. I will define an $n$ such that $an+1$ is not prime. (See the previous answer for an example of how to do this).
Suppose when $n=1$ we have prime as $a+1 = a\cdot 1 + 1 = p$
We can increase this by a multiple of $p$ by taking $n= 1+p$ for $$ a\cdot (1+p) + 1 = a + ap + 1 = (a+1) + ap = p + ap = p(a+1) $$ which is composite. Do it again, $$ a\cdot (1+2p) + 1 = a + 2ap + 1 = (a+1) + 2ap = p + 2ap = p(2a+1) $$ $$ a\cdot (1+3p) + 1 = a + 3ap + 1 = (a+1) + 3ap = p + 3ap = p(3a+1) $$ $$ a\cdot (1+4p) + 1 = a + 4ap + 1 = (a+1) + 4ap = p + 4ap = p(4a+1) $$ which all give composite numbers, as they are larger than $p$ and divisible by $p$
This argument works for any (non-constant) polynomial.
