I am stuck on how to begin this proof. My intuition tells me I need to do something with odd and even. For example, If $n$ and $k$ are even then their product is even and adding $1$ will make it odd and not divisible by $n$. I can show all the scenarios but I'm unsure if it work. Also it might be possible to do it by showing there's a remainder but I'm in the process of learning that topic so that's unclear.
Any tips or suggestions on how to start this?