-3

I was given the statement "for any integer n and prime number p, if n is divisible by p, then n+1 is not divisible by p" and I have to do proof by contradiction. Here's what I have so far... (Note: I don't know how to do the symbols on here so that why I say "for all" or "there exists")

Claim: For all n in Integers and all p in prime numbers, if n is divisible by p, then n+1 is not divisible by p

Proof: Suppose not. That is, suppose that there exists an n in Integers and there exists a p in prime numbers such that n is divisible p and n+1 is divisible by p

Since n+1 is divisible by p, there exists k in Integers such that n+1 = k*p

That's all I got. Im just not sure where to go once i have declared that n+1 is divisible by p. I can set it all up but when it actually comes to proving it I get stuck. And help would be wonderful.

Stephen R.
  • 1
  • Suppose both $n$ and $n+1$ are divisible by $p$. Since $n+1$ is divisible by $p$ we have $\color{blue}{n+1=a\cdot p}$ for some integer $a$. This is the definition of divisibility after all. Do the same for the other and consider the difference. – JMoravitz Oct 18 '17 at 02:28
  • Hint: If $p\mid a$ and $p\mid b$, then $p\mid a-b$. Can you use this to arrive at a contradiction? – Prasun Biswas Oct 18 '17 at 02:29
  • @JMoravitz Okay so I updated the question with what I have now. But what do you mean do the same for the other? – Stephen R. Oct 18 '17 at 02:34
  • "What do you mean by same for the other?" Since $n$ is also divisible by $p$ then we know that $n=$_____ (note, you may need to use a different letter than $k$ for this one) – JMoravitz Oct 18 '17 at 02:38
  • @JMoravitz I'm confused. If n+1 = kp wouldn't n just = mp -1 for example? – Stephen R. Oct 18 '17 at 02:44
  • You claim "I can set it all up", but from what I've seen so far you haven't done much of any of the setup. The most important thing at this level for you to do is to learn the definitions of various concepts. Then, when given a problem a good first step is to write down what the definitions for the hypotheses say. – JMoravitz Oct 18 '17 at 02:44
  • "If n+1 = kp wouldn't n just = mp -1 for example?" Yes, but that is a result of $n+1$ being a multiple of $p$ and just a rewriting of what I said in my first comment. I was trying to get you to write down what it means for $n$ being a multiple of $p$, which is a different hypothesis and implies something different than that. – JMoravitz Oct 18 '17 at 02:52
  • You have two facts. p divides n. And p divides n+1. You used p divides n+1 to write that n+1=kp. But you haven't used p divides n at all. Use it to write something. If p divides n then n = .... what (and DON'T refer to n+1=kp; USE p divides n. *USE* it!) – fleablood Oct 18 '17 at 03:01
  • Here's a different idea. If $n $ is a multiple of $p $ what is the very next multiple of $p $? Is it possible to have two multiples of $p $ that are less than $p $ apart? Think about it. – fleablood Oct 18 '17 at 03:21

2 Answers2

1

You have $n+1=kp$ for some $p $.

And you have $n=jp $ for some $j $.

So you also have $1=(n+1)-n=(k-j)p$.

Or if $m=(k-j) $ we have $1=mp $.

Is that possible?

fleablood
  • 124,253
  • Okay but can you explain the 1=(n+1) - n = (k-j)p came from? – Stephen R. Oct 18 '17 at 02:52
  • 1
    You don't know that $(n+1)-n=1$? You don't know that $kp-jp=(k-j)p$? Not sure I can help with that. – fleablood Oct 18 '17 at 02:56
  • @stephenR. If we have an equality such as $n+1=kp$ then any time we ever see $n+1$ in an expression we may replace it with $kp$ in the expression without changing the value. So, $1=1+0=1+(n-n)=(n+1)-n=(kp)-n=(kp)-(jp)=(k-j)p$. This is written in many more steps than are necessary, but the only technical things that happened in this step are using the definitions of equality and using what equalities we already stated earlier in the proof as well as some arithmetic simplification. – JMoravitz Oct 18 '17 at 03:10
0

Suppose by contradiction that $n\in \Bbb Z$ such that $p|n$ and $p|(n+1).$ Then there exist integers $a, b$ with $n=ap$ and $n+1=bp.$ For such $a,b$ we have:

$1=(n+1)-n=bp-ap=(b-a)p $

so $0<\frac {1}{p}=b-a\in \Bbb Z\;$(Recall that $a,b\in \Bbb Z$ so $b-a\in \Bbb Z$)

so $\frac {1}{p}\in \Bbb Z^+$

so $\frac {1}{p}\geq 1$

so $p\leq 1,$ which is contrary to $p$ being a prime.

DanielWainfleet
  • 57,985
  • It is better to completely avoid division and fractions in proofs about prime numbers as the timing of when primes are introduced first in a formal proof writing or elementary number theory or algebra course division and rational numbers have often not yet been introduced or defined. The proof for this problem can completely avoid leaving the realm of the natural numbers. – JMoravitz Oct 18 '17 at 19:30