State and prove Euclid lenna
Answers
In number theory, Euclid's lemma is a lemmathat captures a fundamental property of prime numbers, namely:[note 1]
Euclid's lemma — If a prime pdivides the product ab of two integers a and b, then p must divide at least one of those integers a and b.
For example, if p = 19, a = 133, b = 143, then ab = 133 × 143 = 19019, and since this is divisible by 19, the lemma implies that one or both of 133 or 143 must be as well. In fact,133 = 19 × 7.
Inherently, if the premise of the lemma does not hold, i.e., p is a composite number, its consequent may be either true or false. For example, in the case of p = 10, a = 4, b = 15, composite number 10 divides ab = 4 × 15 = 60, but 10 divides neither 4 nor 15.
This property is the key in the proof of the fundamental theorem of arithmetic.[note 2] It is used to define prime elements, a generalization of prime numbers to arbitrary commutative rings. Euclid's Lemma shows that in the integers irreducible elements are also prime elements. The proof usesinduction so it does not apply to all integral domains.
Theorem.
There are infinitely many primes.
Proof.
Suppose that p1=2 < p2 = 3 < ... < pr are all of the primes. Let P = p1p2...pr+1 and let p be a prime dividing P; then p can not be any of p1, p2, ..., pr, otherwise p would divide the difference P-p1p2...pr=1, which is impossible. So this prime p is still another prime, and p1, p2, ..., pr would not be all of the primes.
It is a common mistake to think that this proof says the product p1p2...pr+1 is prime. The proof actually only uses the fact that there is a prime dividing this product (see primorial primes).
The proof above is actually quite a bit different from what Euclid wrote. We now understand the integers as abstract objects, but the ancient Greeks understood them as counts of units (the unit, one, was not a number, two was thier first) and represeted them with lengths of line segments (multiples of some unit line segment). Where we talk of divisibility, Euclid wrote of "measuring," seeing one number (length)a as measuring (dividing) another length b if some integer numbers of segments of length a makes a total length equal to b.
The ancient Greeks also did not have our modern notion of infinity. School children now easily understand lines as infinite, but the ancients were again more concrete (in this regard). For example, they viewed lines as segments that could be extended indefinitely (not something infinite that we view just part of). For this reason Euclid could not have written "there are infinitely many primes," rather he wrote "prime numbers are more than any assigned multitude of prime numbers."
Finally, Euclid sometimes wrote his "proofs" in a style which would be unacceptable today--giving an example rather than handling the general case. It was clear he understood the general case, he just did not have the notation to express it. His proof of this theorem is one of those cases.
Below is a proof closer to that which Euclid wrote, but still using our modern concepts of numbers and proof. See David Joyce's pages for an English translation of Euclid's actual proof.
Theorem.
There are more primes than found in any finite list of primes.
Proof.
Call the primes in our finite list p1, p2, ..., pr. Let P be any common multiple of these primes plus one (for example, P = p1p2...pr+1). Now P is either prime or it is not. If it is prime, then P is a prime that was not in our list. If P is not prime, then it is divisible by some prime, call it p. Notice p can not be any of p1, p2, ..., pr, otherwise p would divide 1, which is impossible. So this prime p is some prime that was not in our original list. Either way, the original list was incomplete.
Note that what is found in this proof is another prime--one not in the given initial set. There is no size restriction on this new prime, it may even be smaller than some of those in the initial set. For example, if we begin with the set:
{2, 3, 7, 43, 13, 139, 3263443},
then the smallest choice of P is the product of these seven primes plus on, so P = 547.607.1033.31051. The new prime found would be 547, 607, 1033 or 31051, all of which are smaller than the last prime in the original set.