0

We want to show that if $x|y^2$ then $x|y$. Is this contrapositive proof correct?

Proof by contrapositive: Assume $x \not| \;y$ and $x,y \in Z$. Thus, $y=xk+r$ for $k \in Z, r \in N, r < k$ by definition of not divides (there is a remainder). Hence, $y^2=(xk+r)^2=x^2k^2+2xk+r^2=x(xk^2+2k)+r^2$ for $r^2, xk^2+2k \in Z$. Therefore, $x \not| \;y^2 $ because there is a remainder $r^2$

mont2223
  • 1
  • 5
    But $4|2^2$ and not $4|2$. – drhab Mar 18 '21 at 15:23
  • As drhab pointed out the statement isn't even true. The problem is that $r^2$ could divide $x$ – Lukas Mar 18 '21 at 15:24
  • Thought for integers it is true that $x^2|y \implies x |y$ and $x^2|y^2 \implies x |y$ – Henry Mar 18 '21 at 15:24
  • Thank you for your comments. They are true. But, let's look at a specific case, say if $19|y^2$ then $19|y$. How would I prove this by contrapositive without having 19 different cases for say remainder of 1, remaninder of 2, remainder of 3,...? – mont2223 Mar 18 '21 at 15:27
  • 1
    $19$ is prime. That is a very special case. You have for a prime $p$ and integers $a,b$ that if $p\mid a\cdot b$ then by the very definition of what it means to be prime that we know that $p\mid a$ or that $p\mid b$. This is true in particular when $a$ and $b$ happened to both be the same thing. – JMoravitz Mar 18 '21 at 15:28
  • Thank you for your comment. What if I picked a compositive number, like say 8? Would my proof have seven cases? – mont2223 Mar 18 '21 at 15:31
  • If the composite number were not equal to a product of distinct primes, the statement is false, such as is the case for $4\mid 36$ despite $4\nmid 6$. As for if the composite number were equal to a product of distinct primes, for example $pq$, asking if $pq\mid y^2\implies pq\mid y$, here we again use the defining property of primes and transitivity of the division relation. Since $p\mid pq\mid y^2$, this implies $p\mid y^2$. Similarly, $q\mid y^2$ from which we learn $p\mid y$ and $q\mid y$, from which we can say from fundamental theorem of arithmetic that $y=pqk$ for some integer $k$. – JMoravitz Mar 18 '21 at 15:37
  • No, you should never have your proof go through thousands of different cases. – JMoravitz Mar 18 '21 at 15:38

1 Answers1

2

No, it is not correct. And it could not be, since the statement is false: $4\mid2^2$, but $4\nmid2$.

The error in your proof lies in assuming that $r^2$ is the remainder of the division of $y^2$ by $x$.

José Carlos Santos
  • 427,504