PRINT LINKED RELATED

Arithmetic Theorem

    Before we prove the Fundamental Theorem of Arithmetic, it is important to realize that not all sets of numbers have this property, (it fact many do not have this property). Let's consider the set of even integers, namely



We can add, subtract, even multiply elements of and obtain elements in so we say the set is closed under addition, subtraction, and multiplication. However, this is not he set of integers so we should define what we mean by divisibility; namely for any two elements of E we say means there such that The importance of should not be overlooked. For example, because where But because there is no such that So what are some primes in For example, 2 is prime in because there does not exist in such that Similarly, 6 is prime in because there does not exist in such that Also, 10 and 30 are primes, and so is not. But since we conclude that factorization into primes in is not unique.
    The first step in showing the Fundamental Theorem of Arithmetic is usually proving Euclid's Lemma.

Proposition (Euclid's Lemma)

    (i) An integer is a prime number if and only if for any integers and
    
    (ii) If is a prime number, are integers, and then for some
    
    (iii) Every integer (except ) is a product of primes.
    
    (iv) There are infinitely many prime numbers.
    
    Proof. (i) If is prime and then or If then or if then In either case, or Similarly, when Conversely, suppose for any integers and To show that is prime let be a divisor of Then for some and so or Thus, if for some then and so If for some then and so as desired.
    (ii) The statement is clearly true when and is (i). Assume the statement is true for and suppose



Then by (i), or So by the induction hypothesis there is some such that or it may be the case that Therefore, there is some such that as desired.
    (iii) Consider the set consisting of all positive integers greater than 1 that are not a product of primes. Assume for a contradiction that is not empty, then by the Well-Ordering Axiom there is a least element say Then is itself not a prime number and so, where and Since is the least element in and are products of primes; and thus so is This contradiction shows that is empty and so every integer greater than is a product of primes. Therefore, every integer (except ) is a product of primes because if and then is a product of primes as desired.
    (iv) Assume, as Euclid did, that there are only finitely many prime numbers say,   Consider



which by (iii) must be a product of primes. Let's say and since we have Therefore, which can not be true. Therefore, there can not be a finite number of prime numbers, as desired.

Proposition (Fundamental Theorem of Arithmetic) Every integer can be written uniquely in the form where are prime numbers and are positive integers.

    Proof. Every integer has a prime factorization by Euclid's Lemma. If there is an integer greater than 1 for which the factorization is not unique, then by the Well-Ordering Axiom there exists a smallest such integer, say Assume that has two factorizations say

and

where    and the and are all positive for and By Euclid's Lemma, for some and for some Since all the numbers and are prime, we must have and Then since Let be the integer defined as



If then has a unique factorization. If then and has two factorizations. Both cases reveal that can not exist as desired.

Example (Unique Factorization) Find the unique prime factorization of

    Solution. We have,
    
  
  

Example (Unique Factorization)  Find the unique prime factorization of

    Solution. We have,
    
  

Example (Unique Factorization) Factor and into a product of primes with the same set of primes with (possibly zero) nonnegative exponents.

    Solution. We have, the set of primes in both integers is and so we have
    


and

Example (Unique Factorization) There are infinitely many primes of the form

    Solution. We assume there are only a finite number of primes of the form say is all of them; and we consider the integer


    
Notice that the prime factorization of must contain at least one prime of the form because otherwise would be of the form In general, integers of the form have products of the form which can be seen by letting and then



Thus, there is one prime in the prime factorization of that is of the form say Either or If then which means and so which is absurd. If then implies which is also absurd. Therefore, there are infinitely many primes of the form

Proposition (Greatest Common Divisor) Let and be positive integers.

    (i) Any two nonzero integers and have a greatest common divisor, which can be expressed as the smallest positive linear combination of and
    
    (ii) An integer is a linear combination of and if and only if it is a multiple of their greatest common divisor.  
    
    (iii) There exists integers and such that if and only if
    
    (iv) If and then
    
    (v) If and then
    
    (vi) if and only if and
    
    (vii) If and is a common divisor of and then if and only if
    
    (viii) If and then
    
    (ix) If then

    Proof. (i) For every positive integer there are only a finite number of divisors and thus given two integers there are only a finite number of common divisors. Therefore, the greatest common divisor of every pair of integers must exist and be unique. The fact that is the smallest linear combination of and follows from the Euclidean Algorithm.
    (ii) Let then since the Well-Ordering Axiom yields a smallest positive integer, say Then for some integers and By the Division Algorithm with and so Whence Therefore, and similarly, So is a common divisor of and Let be a common divisor of and Then for some integers and Then as desired.
    (iii)  Apply (ii).
    (iv)  If then there exist integers and such that Thus for some since Therefore,
    (v)   If then there exist integers and such that Thus for some and since and   Therefore,
    (vi)  If then there exist integers and such that Thus, and so Also,    and so Conversely, if then there exists integers and such that If then there exists integers and such that Thus,   for some integers and Therefore, as desired.
    (vii) If then there exist integers and such that and so since and Thus, Conversely, if and then there exists integers and such that Therefore, for some and Thus and so
    (viii) If then there exist integers and such that If then for some integer Thus, and so as desired.  
    (ix) Suppose and let be the set of common divisors of and and let be the set of common divisors of and . We will first show that If then and for some and Thus, Hence, so that Conversely, suppose is a common divisor of and so that and Thus, Thus so that Therefore, Hence the largest element in namely is the same as the largest element in namely

Proposition (Euclidean Algorithm) Let and be positive integers with If then If then apply the division algorithm repeatedly as follows:













This process ends when a remainder of 0 is obtained. This must occur after a finite number of steps; that is, for some





Then the last nonzero remainder, is the greatest common divisor of and

    Proof. The proof follows from the property: if then Thus, if then and so Also, as in the statement of the proposition,

Example (Euclidean Algorithm) Use the Euclidean Algorithm to find By the Division Algorithm,







Thus,

Proposition (GCD and Linear Combinations) There are an infinite number of ways to write as a linear combination of and

    Proof. Let There exists integers and such that and thus, for any integer we have
    


which expresses as a linear combination of and

Definition (Least Common Multiple) The least common multiple of two nonzero integers and is the smallest positive integer that is divisible by and

Example (Least Common Multiple) The least common multiple of and 21 is The least common multiple of and 36 is The least common multiple of 2 and 20 is The least common multiple of 7 and 11 is    

    One immediate result from the Fundamental Theorem of Arithmetic is the ability to find the GCD and LCM from a factorization of two given integers. Say we are given and and we are able to find the unique factorization of each (and assume that all exponents are nonnegative and the are all primes in both and ), namely    



then



because for each prime in and have exactly factors of in common.

Proposition (Least Common Multiple and Greatest Common Divisor) If and are positive integers, then  

    Proof. Let and have prime factorization; namely
    


Now we can form the set of primes consists of all the and So we can write



where the exponents are zero where necessary. Now let and Then, we have,

Example (Least Common Multiple) Show that if and are integers, then if and only if and

    Solution. Suppose Since and it follows that and Conversely, suppose and Using the unique factorization theorem we can write and Then for and  because and Hence,

Example (Least Common Multiple and Greatest Common Divisor)  Show that if and are positive integers, then

    Solution. Let be a prime that divides or Then divides and Hence divides both sides of the equation Define, and by and say and Without loss of generality, suppose Then so Also, But so Therefore, But so the same power of divides both sides of the equation. Therefore, the two sides must be equal.