# Thread: "x divides y" proof

1. ## "x divides y" proof

Are these valid proofs? Specifically, is the way that I introduced the integer k the right way to do that? Thanks.

Let R be the relation on Z given by xRy iff x divides y.

Proof (Reflexive)
Suppose x is in Z. Consider integer k = 1. Then, x = (1)x = kx, and x divides x.
Thus, xRx and R is reflexive.

Proof (Symmetric)
Counterexample: Suppose (x, y) = (1, 10). Let k = 10. Then, y = 10 = (10)1 = kx, and xRy.
But (y, x) = (10, 1) and y = 1 = (k)10 for k = 1/10. Thus, y does not divide x
and (y, x) is not in R. So, R is not symmetric.

Proof (Transitive)
Suppose (x, y) and (y, z) are both in R. Then there exists integers k and n such that y = kx and z = ny.
So, z = ny = n(kx) = (nk)x. Since the product of integers is again an integer, nk is an integer.
Thus, x divides z and xRz. Therefore, R is transitive.

2. ## Re: "x divides y" proof

Those are correct, but I would phrase your counter-example as a proof by contradiction, like so:

Suppose 10 divides 1: then there is an integer k with 1 = 10k. Clearly, k = 0, or 1 do not work. So if k exists, we must have k > 1, in which case: 1 = 10k > 10 > 1, a contradiction.

Why do it this way? Because we are only using properties of the INTEGERS, and not making reference to an "outside system" (the rational numbers) which we do not need. Also, in the rational numbers, 10 DOES divide 1, which muddies the waters, logically speaking.

In other rings (essentially algebra systems in which we have addition, subtraction and multiplication, but perhaps not division) we may have no notion of what 1/k even "means", so it is a good idea to avoid using that way of thinking later on.

Of course, to be able to use my argument, you must legally be allowed to use the ORDER properties of the integers, and I do not know if your course has gone into these yet.

That is a small detail, however, and your proofs are correct, and your counter-example IS a valid one.