0

Could someone walk me through this problem from my Discrete Mathematics textbook? It states: Prove that $\forall x, \forall y \in Z^+$ such that $x|y$ and $y|x$ implies $x=y$, or in English for every x,y in the Positive Integers such that x divides y and y divides x, implies x=y.

Proofs are not my strong-suit by any means, my go to usually being to attempt a proof by Contradiction. However, for this one I'm just stuck with the statement being true because, as my instructor likes to say, "Clearly Obvious"? I mean, if x=y then if x=4 and y=4, then 4/4 = 1 meaning both ways they divide the other and are equal?

Can someone explain this to me?

Analytic Lunatic
  • 389
  • 1
    On the one hand I agree that there can be too much focus on formal proof writing, but in this case it seems like you've either misunderstood the statement of the problem or which way logical implication goes. The example you gave is an example of the statement "If $x=y$ then $x|y$ and $y|x$", but the problem asks you to show the other direction. – Callus - Reinstate Monica Apr 07 '16 at 14:18

5 Answers5

1

Use the definition of dividing:

$$x | y \text { if for some integer } k \text{ we have } kx=y.$$ Now as $y| x$ we also have, for some integer $l$, that $yl=x$. Put these two together and we get that $$ x= yl = kxl $$ i.e. $x= kxl$ which we rewrite as $x(1-kl)=0$. If $x\neq 0$ (which we assumed) $1-kl=0$ i.e. $1=kl$. As $k$ and $l$ are integers, this implies that $k=l=1$. Thus if we look at the first equation again we see that $$y=kx=1\cdot x=x $$

Ove Ahlman
  • 4,329
0

$x \mid y \implies y = kx$ for some integer $k$, and $y \mid x \implies x = \ell y$ for some integer $\ell$ by the definition of divisibility. Putting these together, we have $y = k\ell y$, so we divide by the positive quantity $y$ to get $k\ell = 1$. Either $k, \ell = 1$ or $k, \ell = -1$ (this is easily proven), but since we're in $\mathbb{Z}^+$, they must be positive. Hence $k, \ell = 1$ and $x = y$.

shardulc
  • 4,562
0

Since $x|y$, exist $n\in\mathbb{Z}^{+}$ such that $y=xn$. Similarly, we have $m\in\mathbb{Z}^{+}$ such that $x=ym$. Therefore $$x=ym=x(nm),$$ i.e., $$x(1-x(nm))=0.$$ Since $x\neq 0$ we have $nm=1$. Thus $n=m=1$ and $x=y$.

Rafael
  • 3,789
0

Well say: $$x=y+k$$ Now: $$\dfrac{y}{x}=\dfrac{y}{y+k}$$ Since $x\mid y$: $$\dfrac{y}{y+k}\geq1$$ $$y\geq y+k$$ $$0\geq k$$

The same can be done for $\dfrac{x}{y}$, using $y=x-k$. We'll see that: $$0\geq k$$ $$0\leq k$$ so obviously $k=0$

Mastrem
  • 8,331
0

To be formal, let's use the definitions of $|$.

$a | b$ is defined to be $ b = m.a$ with $m$ is an integer.

Now, if you have $x|y$ and $y|x$, then

$x = k.y$ and $ y = m.x$ where both $k,m$ are integers.

$x = k.y = k. (m.x) \implies x - kmx = 0 \implies x(1-km) = 0 \implies x = 0$ or $km = 1$.

Since $x$ is positive, then $km = 1$ with $m,k$ integers.

The only possible pairs of $(m,k)$ are $(1,1)$ and $(-1,-1)$.

Since both $x$ and $y$ are positive, $m$ or $k$ can not be negatives.

Then $(m,k) = (1,1) \implies x = 1.y = y$

crbah
  • 1,162