1
$\begingroup$

Let $s$ and $t$ be two relatively prime odd numbers. We want to know the $d=\gcd(s-t,s+t).$ Let $d=2^lm$ thus $s-t=2^lmk_1$ and $s+t=2^lmk_2$ for $k_1$ and $k_2$ odd numbers and $\gcd(k_1, k_2)=1.$ Summing and subtracting both sides of two equality-es and diving by $2$ results in $s=2^lm \frac{(k_1+k_2)}{2}$ and $t=2^lm \frac{(k_2-k_1)}{2}$ in which $\frac{(k_2 \pm k_1)}{2}$ are integers as both $k_1$ and $k_2$ are odd numbers and because $s$ and $t$ are relatively prime implies $l=0$ which is not possible since both $s-t$ and $s+t$ are even so must $l \ge 1$ !! Contradiction?

A rewritten version of this same question, for the author's benefit:

Let $s$ and $t$ be two distinct relatively prime odd numbers.

We want to compute $d=\gcd(s-t,s+t).$ Note that $s-t$ and $s+t$ are both nonzero because $s$ and $t$ are distinct.

Let $d=2^\ell m$, where $m$ is odd. Then since $s-t$ and $s+t$ are both multiples of $d$, we have \begin{align} s-t&=2^\ell mk_1 \text{and}\\ s+t&=2^\ell mk_2 \end{align} where $k_1$ and $k_2$ are both odd. Furthermore, $\gcd(k_1, k_2)=1,$ for if it were some other number $u > 1$, then $ud$ would divide both $s+t$ and $s-t$, contradicting the fact that $d$ is their greatest common divisor. Finally, since both $s-t$ and $s+t$ are even and nonzero, we must have $\ell \ge 1$, which we'll use shortly.

Summing and subtracting both sides of these two equalities and dividing by $2$ gives \begin{align} s&=2^\ell m \frac{(k_1+k_2)}{2} \text{ and}\\ t& =2^\ell m \frac{(k_2-k_1)}{2} \end{align} Note that because $k_1$ and $k_2$ are both odd, their sum and difference are both even, hence $\frac{(k_2 \pm k_1)}{2}$ are both integers.

Now $s$ and $t$ are relatively prime (given), so $\ell$ must be zero (otherwise $2^\ell$ would divide both, and the gcd could not be $1$).

On the other hand, we showed above that $\ell \ge 1$. That's a contradiction.

=====

Now there's definitely something screwy in the "proof" above, because Jyrki's example shows that the gcd is actually $2$. But you'll have a lot easier time finding the error now that the "proof" is actually written clearly and coherently.

$\endgroup$
  • 2
    $\begingroup$ $s=5,t=3\implies s+t=8, s-t=2$ and $\gcd(s+t,s-t)=?$ $\endgroup$ – Jyrki Lahtonen Aug 5 '18 at 20:16
  • 1
    $\begingroup$ If $s$ and $t$ are two relatively prime odd numbers, then $\gcd(s+t,s-t)=2$. $\endgroup$ – Batominovski Aug 5 '18 at 20:16
  • $\begingroup$ @Batominovski, Of course but I am asking about the contradiction. Please read whole OP not just the title. $\endgroup$ – user231343 Aug 5 '18 at 20:17
  • 2
    $\begingroup$ Suggestion: It seems English may not be your first language. To help clarify your writing, try (a) using shorter sentences, and (b) introducing paragraph breaks. For instance, your first "thus" should start a new sentence. Also, try to put hypotheses first rather than last (so $\gcd(k_1, k_2) = 1$ should be right at the front of that sentence rather than at the end). Your third sentence is really about 3 or 4 sentences, and reading it leaves me breathless and confused, even though I know this material quite well. Does this matter? Maybe. Often writing clearly leads to improved understanding. $\endgroup$ – John Hughes Aug 5 '18 at 20:24
  • $\begingroup$ @JohnHughes, of course it matters. Thanks a lot for your suggestion. :) $\endgroup$ – user231343 Aug 5 '18 at 20:28
2
$\begingroup$

$k_1$ and $k_2$ don't have to be odd numbers, only one of them has to be. If $s$ and $t$ are both odd, $s+t$ and $s-t$ are both even, so you know that $d$ is also even.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I factored all 2's so that k_1 and k_2 be odds $\endgroup$ – user231343 Aug 5 '18 at 20:19
  • 2
    $\begingroup$ It could be that $s-t=4\cdot\text{odd}$ but $s+t=2\cdot\text{odd}$. In fact, one of $s+t$ and $s-t$ is $2$ modulo $4$, and the other is divisible by $4$. $\endgroup$ – Batominovski Aug 5 '18 at 20:20
  • $\begingroup$ Exactly, take $s=5$ and $t=1$ for example $\endgroup$ – TitiMcMath Aug 5 '18 at 20:22
  • $\begingroup$ I've edited your question to add a reformatted "proof" that is (I believe) much more readable. $\endgroup$ – John Hughes Aug 5 '18 at 22:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy