# Thread: PROVE THE FOLLOWING has 3 parts

1. ## PROVE THE FOLLOWING has 3 parts

1.
i) if p is prime, a,b are integers, and p divdes ab, then p divides a or p divides b[Hint use result when proving the theorem there exists integers m, n such that g = m*a=n*b]

ii) If r is a rational number then there exist integers m,n such that n>0, r = m/n and m, n have no common factors.. [USE WELL ORDERING PRINCIPLE]

iii) PROVE SQRT(21) is irrational [Hint use part 1 and part 2]

2. Originally Posted by ruprotein
1.
i) if p is prime, a,b are integers, and p divdes ab, then p divides a or p divides b[Hint use result when proving the theorem there exists integers m, n such that g = m*a=n*b]
Let $\displaystyle a,b>0$.

If $\displaystyle p|(ab)$ then $\displaystyle \gcd(a,p)=1,p$ (definition of prime: no non-trivial proper divisors). If $\displaystyle \gcd(a,p)=p$ then $\displaystyle p|a$ and proof is complete. It $\displaystyle \gcd(a,p)=1$ then $\displaystyle p|b$ (by Euclid's Lemma)*

*)Let $\displaystyle a,b,c>0$, and if $\displaystyle c|ab$ and $\displaystyle \gcd(a,c)=1$ then $\displaystyle a|b$.

3. Originally Posted by ruprotein
ii) If r is a rational number then there exist integers m,n such that n>0, r = m/n and m, n have no common factors.. [USE WELL ORDERING PRINCIPLE]
For everything positive.

The consequence of the Well-Ordering principle is that any two positive integers $\displaystyle a,b$ has the greatest common divisor $\displaystyle d$.*)

In that case we can write,
$\displaystyle \frac{a'd}{b'd}=\frac{a'}{b'}$
Where, $\displaystyle \gcd(a',b')=1$.

*)Let $\displaystyle S=\{ax+by>0|x,y \in \mathbb{Z} \}$.
Then by Zorn's lemma this set has a minimial element (this is greatest common divisor).
Thus, any two positive integers have a greatest common divisor.

4. I think that the well ordering principle referred here is the axiom “Any non-empty set of positive integers has a first term”. Then consider $\displaystyle \left\{ {k \in Z^ + :kr \in Z} \right\}.$ That set is not empty and has a first term N.
Now $\displaystyle \left( {\exists M \in Z} \right)\left[ {r = \frac{M}{N}} \right]$, so show that M & N cannot have a common divisor other than 1.

5. Originally Posted by Plato
“Any non-empty set of positive integers has a first term”.
I know. I do not like to take as an axiom, it makes me want to vomit. Using AC is the most natual approach and hence this is a theorem.

6. It may well make you want to vomit. But I will bet 2 to 1 that that is the approach required by this instructor/text. It is the natural way to do it in a basic real analysis course.