Update: I believe the solution by @UnexpectedValues can be adapted to work for all natural numbers.
Proof: By Dirichlet prime number theorem, for every N, there is a prime q of the form q=(N−1)+kN as long as N-1 and N are co-prime, which is true whenever N>2. Then N|q+1and the solution by UnexpectedValues can be used with appropriate p. Such p exists whenever q>2which is always the case for N>3. For N=3, one can take e.g. q=5 (since 3|5+1). And N≤2 is trivial.
Update: I believe the solution by @UnexpectedValues can be adapted to work for all natural numbers.
Proof: By Dirichlet prime number theorem, for every N, there is a prime q of the form q=(N−1)+kN as long as N-1 and N are co-prime, which is true whenever N>2. Then N|q+1and the solution by UnexpectedValues can be used with appropriate p. Such p exists whenever q>2which is always the case for N>3. For N=3, one can take e.g. q=5 (since 3|5+1). And N≤2 is trivial.