0

For all y in the intergers and prime numbers x , if x divides y then x does not divide y+ 1

I understand you could prove this directly but apparently a proof by contradiction is easier (I just dont know how)

The basic form is to assume the hypothesis then negate the conclusion so that

x divides y+1 is what we are trying to show. what's the contradiction then and how do you finish it?

rajteh
  • 23

3 Answers3

1

$x\mid y,x\mid y+1\implies x\mid (y+1-y)\implies x\mid 1$ !!

  • Using the fact that if $p\mid a,p\mid b\implies p\mid a-b$ (which is quite easy to prove I think)

  • Also using the fact that since $x$ is a prime so $x\nmid 1$

Learnmore
  • 31,062
  • It works for x=1 but now they dont consider 1 as a prime – user577215664 Oct 15 '17 at 05:31
  • @Isham; that's the contradiction – Learnmore Oct 15 '17 at 05:33
  • I can kinda see but can you put an explanation in words what you did exactly (sorry this is like my first contradiction proof) – rajteh Oct 15 '17 at 05:42
  • @rajteh;if $p\mid a,p\mid b\implies a=pk,b=pd\implies a-b=p(k-d)$; – Learnmore Oct 15 '17 at 05:49
  • This post is literally on the tag "proof explanation", I think you could be a bit more expressive, couldn't you? – qualcuno Oct 15 '17 at 05:56
  • @GuidoA.; so you downvoted for that – Learnmore Oct 15 '17 at 06:06
  • Yes, no offense, but the hover over the downvote button states "this answer is not useful" and to be honest, I thought it wasn't. It was pretty clear that OP needed a thorough explanation, not only on the contradiction itself but on how to write this kind of proofs. Even when he asked you to clarify, you replied again with a bunch of implications. – qualcuno Oct 15 '17 at 06:11
1

Start by assuming the opposite of what you want to prove. In this case, suppose that $x,y \in \mathbb{Z}$ verify $x \ | \ y$ and $x \ | \ y + 1$, with $x$ a prime. Now, this implies

$$ y = k\cdot x \\ y+1 = l\cdot x $$

for $\ l,k\in \mathbb{Z}$. Therefore, subtracting at both sides we get:

$$ 1 = (l-k)\cdot x $$

and taking modules:

$$ 1 = |l-k|\cdot|x| \geq |x| $$

We have reached a contradiction, since every prime has a module of 2 or greater. This mean what we assumed is false, so either $x \ | \ y$ or $x \ | \ y + 1$. In particular, if we assume $x \ | \ y$, then necessarily $x \ \not| \ y + 1$.

qualcuno
  • 17,121
  • thanks! but can you explain the taking modules part (sorry)? – rajteh Oct 15 '17 at 05:48
  • Yeah of course, it's one of many ways of saying that $x$ should be $1$ o $-1$, I decided to go for that one. We take modules on both sides. Then, we use that $l-k$ is a non-zero integer, becuause $(l-k)\cdot x$ is not zero, and therefore $|l-k|$ is a natural number, and naturally this implies $|l-k| \geq 1$. So, $1 = |l-k|\cdot |x| \geq |x|$ and since $x$ is an integer, x is either $1$ or $-1$. This shows the contradiction we were looking for, since $x$ must be prime. If you're familiar with divisibility properties, that was a long way of justifying that $x | 1$ implies $x \in {-1,1}$. – qualcuno Oct 15 '17 at 05:52
0

$x|y \,$ and $\, x|(y+1)$ then $ \frac {y+1}{x}=n \iff \frac y x + \frac 1 x=n \iff m+ \frac 1 x=n \iff \frac 1 x = n-m$

user577215664
  • 40,625