# PROVE THE FOLLOWING has 3 parts

• Jan 3rd 2007, 12:41 PM
ruprotein
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]
• Jan 3rd 2007, 01:55 PM
ThePerfectHacker
Quote:

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 $a,b>0$.

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

*)Let $a,b,c>0$, and if $c|ab$ and $\gcd(a,c)=1$ then $a|b$.
• Jan 3rd 2007, 02:04 PM
ThePerfectHacker
Quote:

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 $a,b$ has the greatest common divisor $d$.*)

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

*)Let $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.
• Jan 3rd 2007, 05:02 PM
Plato
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 $\left\{ {k \in Z^ + :kr \in Z} \right\}.$ That set is not empty and has a first term N.
Now $\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.
• Jan 3rd 2007, 05:14 PM
ThePerfectHacker
Quote:

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.
• Jan 3rd 2007, 05:23 PM
Plato
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.