Lemma 1:
If:
gcd(e,f)=1
e divides k
f divides k
Then:
ef divides k
Proof:
(1) Assume that ef does not divide k.
(2) Then, there must exist a prime p and a power c such that pc divides ef but pc does not divide k.
(3) Since gcd(e,f)=1, it follows that pc must entirely divide e or pc must entirely divide f.
(4) Let's assume that pc divides e. [We can make a parallel argument if pc divides f.
(5) But then we have a contradiction since e divides k implies that pc divides k.
(6) So we reject our assumption in step #1.
QED
Lemma 2:
If a ≥ b and b ≥ a, then a = b
Proof:
(1) a ≥ b
(2) So it follows that a = b or a is greater than b.
(3) But a is not greater than b since b ≥ a.
(4) So then it follows that a = b.
QED
Corollary 2.1:
If a,b are positive and a divides b and b divides a, then a = b
Proof:
(1) If a divides b, then b ≥ a.
(2) If b divides a, then a ≥ b
(3) Since a ≥ b and b ≥ a, we can use Lemma 2 above to conclude that a= b.
QED
Lemma 3:
if gcd(e,f)=1 and e divides af
then:
e divides a
Proof:
(1) Assume that e does not divide a.
(2) Then, there exists a prime p such that pc divides e but does not divide a.
(3) Since pc divides e, it follows that pc must divide af.
(4) Using Euclid's Lemma (see Lemma 2, here), we know that if p divides af, then it divides a or it divides f. But it cannot divide f since gcd(e,f)=1 so it divides a.
(5) But then pc must divide a since no p can divide f. This contradicts step #2.
(6) Therefore, we reject our assumption in step #1.
QED
2 comments :
Corollary 2.1:
If a divides b and b divides a, then a = b
I think this should instead be "If a divides b and b divides a, then |a| = |b|" because if you let a = -3 and b = 3, then -3|3 , 3|-3 but 3 doesn't equal -3. However, |3| = |-3|.
Thanks very much for your comment.
You are correct. I've updated the lemma to say if a,b are positive integers.
Cheers,
-Larry
Post a Comment