0

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?

cmk
  • 12,303
bow123
  • 53
  • 5
  • Assume, to the contrary, that $n,|,(kn+1)$. Deduce that $n,|,1$. – lulu Sep 25 '19 at 23:40
  • 1
    For $n=1$, it does divide. – Bernard Sep 25 '19 at 23:55
  • I am pretty sure i wrote n>1. Sorry for the confusion that is what i meant. – bow123 Sep 26 '19 at 00:09
  • @lulu is it enough to say that since kn is a multiple of n therefore there is a remainder of 1 and n l 1 hence contradiction. Is there a general rule that if n l kn +q then q must be divisible by n? makes sense intuitively. – bow123 Sep 26 '19 at 00:24
  • No need to rely on intuition. if $n,|,(nk+1)$ then $nk+1=mn$ for some $m\in \mathbb N$. But then $1=n\times(m-k)$. – lulu Sep 26 '19 at 00:32
  • Oh okay that makes a lot of sense. I wrote down that equation but didn't rearrange so i didn't see it. Thanks! – bow123 Sep 26 '19 at 00:38
  • Another way: $\ k,\color{#0a0}n + \color{#c00} 1,$ divided by $,\color{#0a0}n,$ has quotient $,k,$ & remainder $\color{#c00} 1,, $ by $\ 0 \le 1 < n.,$ If it was divisible by $,n,$ it would have remainder $,0,$ (this uses the uniqueness of the remainder in the Division Algorithm). – Bill Dubuque Sep 26 '19 at 01:31

0 Answers0