Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Please review my attempt to prove a theorem. Any mistakes you point would be highly appreciated by me.

To prove the theorem, I'll be using the following properties which I'm assuming have already been proven.

Properties:

  1. $n|0$ (every integer divides $0$)
  2. $d|n$ and $d|m \implies d|(an + bm)$ (linearity property)
  3. $d|n$ and $n \neq 0 \implies |d| \leq |n|$

THEOREM:

Given any two integers $a$ and $b$, there is a common divisor $d$ of $a$ and $b$ of the form:

$$d = ax + by$$

where $x$ and $y$ are integers. Moreover, every common divisor of $a$ and $b$ divides $d$.

PROOF:

We will do an induction on the value of $|a| + |b|$.

Induction base: If $a = b = 0$, clearly $d = 0$ and every integer divides $0$. So, the theorem is true when $|a| + |b| = 0.$

Induction hypothesis: Let us assume that the theorem is true when $|a| + |b| < n$ where $n$ is an integer.

Induction: Now, let us see what happens when $|a| + |b| = n.$

There are two possible cases:

  • $|b| = 0$.
  • $|b| > 0$.

When $|b| = 0, d = |a|$. This can be justified as follows. $|a|$ divides $a$ and $0$. Every integer that divides $a$ and $0$, also divides $\text{sgn}(a).a = |a|$.

When $|b| > 0$, without loss of generality, we can assume $|a| \geq |b|.$

$|a| = n - |b| < n$.

So, $|a| = (|a| - |b|) + |b| < n$.

From the induction hypothesis, there is an integer $d$ such that:

  1. $d|(|a| - |b|)$.
  2. $d|(|b|)$.
  3. $d = (|a| - |b|)x + |b|y$ where $x$ and $y$ are integers.

From (1) and (2), $d|(|a| - |b|) + |b|$ or $d|(|a|)$ or $d|\text{sgn}(a).|a|$ or $d|a$.

From (2), $d|(|b|)$ or $d|\text{sgn}(b).|b|$ or $d|b.$

From (3), $d = |a|x + |b|(y - x)$ or $d = a(\text{sgn}(a).x) + b(\text{sgn}(b)(y - x))$.

If $c|a$ and $c|b$, from the linearity property,

$c|a(\text{sgn}(a).x) + b(\text{sgn}(b)(y - x))$ or $c|d$.

Q.E.D.

share|improve this question
    
Daniel, In my proof I have omitted the step of dealing with a < 0, b < 0 separately. You believe that it can not be omitted. If you are right, my proof should have an error. Do you find any error in my proof or do you agree that the a < 0, b < 0 related step can be omitted? –  Lone Learner Jan 28 '12 at 15:28
    
If the problem were ONLY to prove that a gcd exists, it would be simpler. The set of common divisors always contains $1$, so it's not empty, and it cannot be infinite, since the gcd of of two numbers is no more than the max of the two numbers. –  Michael Hardy Jan 28 '12 at 17:13
    
Lone Learner: I have gone through the proof. It is correct. I don't like your use of "or" many ($7$?) times close to the end to mean essentially "and therefore." Too easily confused with logical or. The proof would be much clearer if you got rid of absolute values. Once $a$ and $b$ non-negative have been dealt with, the rest is trivially dealt with. –  André Nicolas Jan 28 '12 at 18:02
    
@LoneLearner: you were right and I think the proof is an interesting departure from the standard one I had cited. –  daniel Jan 28 '12 at 23:46
    
And where is the question? If there is no mistake, does "Yes you are right." count for an answer? –  awllower Feb 22 '13 at 11:50
add comment

1 Answer

up vote 5 down vote accepted

This CW answer intends to remove the question from the Unanswered queue.


As remarked in the comments, your proof is correct. Cheers!

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.