Dhirendra.C

PowerPoint Presentation: 

SRI DEVARAJ URS INTERNATIONAL RESIDENTIAL SCHOOL Kodiegehalli,D.Bpur MATHEMATICS PROJECT ON: EUCLID’S FUNDAMENTAL THOREM OF ARITHEMATIC NAME – Dhirendra.C CLASS- X ROLL NO. – H1008 2011-2012 SUBMITTED TO : DEPARTMENT OF MATHEMATICS

PowerPoint Presentation: 

Content: EUCLID’S INTRODUCTION FUNDAMENTAL THEOREM OF ARITHEMATIC Applications Euclid's proof (of existence) Proof of uniqueness; Generalizations

PowerPoint Presentation: 

Euclid ( /ˈ juːklɪd / ewk -lid ; Ancient Greek : Εὐκλείδης Eukleidēs ), fl. 300 BC, also known as Euclid of Alexandria , was a Greek mathematician , often referred to as the "Father of Geometry". He was active in Alexandria during the reign of Ptolemy I (323–283 BC). His Elements is one of the most influential works in the history of mathematics , serving as the main textbook for teaching mathematics (especially geometry ) from the time of its publication until the late 19th or early 20th century. [1][2][3] In the Elements , Euclid deduced the principles of what is now called Euclidean geometry from a small set of axioms . Euclid also wrote works on perspective , conic sections , spherical geometry , number theory and rigor . "Euclid" is the anglicized version of the Greek name ( Εὐκλείδης — Eukleídēs ), meaning "Good Glory". EUCLID’S INTRODUCTION

PowerPoint Presentation: 

In number theory , the fundamental theorem of arithmetic (or the unique-prime-factorization theorem ) states that any integer greater than 1 can be written as a unique product ( up to ordering of the factors ) of prime numbers . For example, are two examples of numbers satisfying the hypothesis of the theorem that can be written as the product of prime numbers. Proof of existence of a prime factorization is straightforward; proof of uniqueness is more challenging. Some proofs use the fact that if a prime number p divides the product of two natural numbers a and b , then p divides either a or b , a statement known as Euclid's lemma . Since multiplication on the integers is both commutative and associative , it does not matter in what way we write a number greater than 1 as the product of primes; it is common to write the (prime) factors in the order of smallest to largest. FUNDAMENTAL THEOREM OF ARITHEMATIC

PowerPoint Presentation: 

Many authors assume 1 to be a natural number that has no prime factorization. Thus Theorem 1 of Hardy & Wright (1979) takes the form, "Every positive integer, except 1, is a product of one or more primes," and Theorem 2 (their "Fundamental") asserts uniqueness. By convention, the number 1 is not itself prime, but since it is the product of no numbers, it is often convenient to include it in the theorem by the empty product rule. Some natural extensions of the hypothesis of this theorem allow any non-zero integer to be expressed as the product of "prime numbers" and " invertibles ". For example, 1 and −1 are allowed to be factors of such representations (although they are not considered to be prime). In this way, one can extend the Fundamental Theorem of Arithmetic to any Euclidean domain or principal ideal domain bearing in mind certain alterations to the hypothesis of the theorem. A ring in which the Fundamental Theorem of Arithmetic holds is called a unique factorization domain .

PowerPoint Presentation: 

applications The fundamental theorem of arithmetic establishes the importance of prime numbers. Prime numbers are the basic building blocks of any positive integer, in the sense that each positive integer can be constructed from the product of primes with one unique construction. Finding the prime factorization of an integer allows derivation of all its divisors, both prime and non-prime. This property of uniqueness is powerful, as the factorization can be thought of as a key for a number. This is why it can be used to build powerful encryption techniques such as RSA . For example, the above factorization of 6936 shows that any positive divisor of 6936 must have the form 2 a × 3 b × 17 c , where a takes one of the 4 values in {0, 1, 2, 3}, where b takes one of the 2 values in {0, 1}, and where c takes one of the 3 values in {0, 1, 2}. Multiplying the numbers of independent options together produces a total of 4 × 2 × 3 = 24 positive divisors. Once the prime factorizations of two numbers are known, their greatest common divisor and least common multiple can be found quickly. For instance, from the above it is shown that the greatest common divisor of 6936 and 1200 is 2 3 × 3 = 24. However, if the prime factorizations are not known, the use of the Euclidean algorithm generally requires much less calculation than factoring the two numbers.

PowerPoint Presentation: 

The fundamental theorem ensures that additive and multiplicative arithmetic functions are completely determined by their values on the powers of prime numbers. It may be important to note that Egyptians like Ahmes used earlier practical aspects of the factoring, such as the lowest common multiple , allowing a long tradition to develop, as formalized by Euclid, and rigorously proven by Carl Friedrich Gauss . Although at first sight the theorem seems 'obvious', it does not hold in more general number systems, including many rings of algebraic integers . This was first pointed out by Ernst Kummer in 1843, in his work on Fermat's Last Theorem . The recognition of this failure is one of the earliest developments in algebraic number theory .

PowerPoint Presentation: 

Euclid's proof (of existence) The proof consists of two steps. In the first step every number is shown to be a product of zero or more primes. In the second, the proof shows that any two representations may be unified into a single representation . Non-prime composite numbers: Proof by contradiction via minimal counterexample : Suppose there were positive integers which cannot be written as a product of primes. Then there must be a smallest such number (see well-order ): let it be n . This number n cannot be 1, because of the empty-product convention above. It cannot be a prime number either, since any prime number is a product of a single prime, itself. So it must be a composite number. Thus where both a and b are positive integers smaller than n . Since n is the smallest number which cannot be written as a product of primes, both a and b can be written as products of primes. But then can be written as a product of primes as well, simply by combining the factorizations of a and b ; but this contradicts our supposition. Hence, all positive integers must be able to be written as a product of primes.

PowerPoint Presentation: 

Proof of uniqueness; The key step in proving uniqueness is Euclid's proposition 30 of book 7 (known as Euclid's lemma ), which states that, for any prime number p and any natural numbers a , b : if p divides ab then p divides a or p divides b . This may be proved as follows: Suppose that a prime p divides ab (where a , b are natural numbers) but does not divide a . We must prove that p divides b . Since p does not divide a , and p is prime, the greatest common divisor of p and a is 1. By Bézout's identity , it follows that for some integers x , y (possibly negative), Multiplying both sides by b , Since p divides , p divides Since p divides both summands on the left, p divides b . A proof of the uniqueness of the prime factorization of a given integer proceeds as follows. Let s be the smallest natural number that can be written as (at least) two different products of prime numbers. Denote these two factorizations of s as p 1 ··· p m and q 1 ··· q n , such that s = p 1 p 2 ··· p m = q 1 q 2 ··· q n . Both q 1 and q 2 ··· q n must have unique prime factorizations (since both are smaller than s ). By Euclid's proposition either p 1 divides q 1 , or p 1 divides q 2 ··· q n . Therefore p 1 = q j (for some j ). [1] But by removing p 1 and q j from the initial equivalence we have a smaller integer factorizable in two ways, contradicting our initial assumption. Therefore there can be no such s , and all natural numbers have a unique prime factorization.

PowerPoint Presentation: 

Generalizations The fundamental theorem of arithmetic generalizes to various contexts; for example in the context of ring theory , where the field of algebraic number theory develops. A ring is said to be a unique factorization domain if the Fundamental theorem of arithmetic (for non-zero elements) holds there. For example, any Euclidean domain or principal ideal domain is necessarily a unique factorization domain. Specifically, a field is trivially a unique factorization domain.