Fundamental Theorem of Arithmetic

    The Fundamental Theorem of Arithmetic: every integer greater than 1 is either a prime or a product of a finite number of primes and this factorization is unique except for the rearrangement of the factors. In this topic we start out with Euclid’s Lemma which states that if a prime divides a product then it must divide one of the factors. This lemma is very useful and will be used to show there are infinitely many primes and that every integer greater than 1 is a product of primes. Then we define the Euler totient function and by using the prime factorization of an integer we give a formula to compute functional values. Finally, in this topic we take a special interest in a collection of multiplicative Abelian groups which consist of invertible elements constructed from the integers modulo n.

Definition (Prime) An integer fundamental theorem of arithmetic in the integers _gr_1.gif] is said to be a prime number if fundamental theorem of arithmetic in the integers _gr_2.gif] and the only divisors of fundamental theorem of arithmetic in the integers _gr_3.gif] are fundamental theorem of arithmetic in the integers _gr_4.gif] and fundamental theorem of arithmetic in the integers _gr_5.gif]

Proposition (Euclid's Lemma)

    (i) An integer fundamental theorem of arithmetic in the integers _gr_6.gif] is a prime number if and only if fundamental theorem of arithmetic in the integers _gr_7.gif] for any integers fundamental theorem of arithmetic in the integers _gr_8.gif] and fundamental theorem of arithmetic in the integers _gr_9.gif]
    
    (ii) If fundamental theorem of arithmetic in the integers _gr_10.gif] is a prime number, fundamental theorem of arithmetic in the integers _gr_11.gif] fundamental theorem of arithmetic in the integers _gr_12.gif] fundamental theorem of arithmetic in the integers _gr_13.gif] are integers, and fundamental theorem of arithmetic in the integers _gr_14.gif] then fundamental theorem of arithmetic in the integers _gr_15.gif] for some fundamental theorem of arithmetic in the integers _gr_16.gif]
    
    (iii) Every integer (except fundamental theorem of arithmetic in the integers _gr_17.gif]) is a product of primes.
    
    (iv) There are infinitely many prime numbers.
    
    Proof. (i) If fundamental theorem of arithmetic in the integers _gr_18.gif] is prime and fundamental theorem of arithmetic in the integers _gr_19.gif] then fundamental theorem of arithmetic in the integers _gr_20.gif] or fundamental theorem of arithmetic in the integers _gr_21.gif] If fundamental theorem of arithmetic in the integers _gr_22.gif] then fundamental theorem of arithmetic in the integers _gr_23.gif] or if fundamental theorem of arithmetic in the integers _gr_24.gif] then fundamental theorem of arithmetic in the integers _gr_25.gif] In either case, fundamental theorem of arithmetic in the integers _gr_26.gif] or fundamental theorem of arithmetic in the integers _gr_27.gif] Similarily, when fundamental theorem of arithmetic in the integers _gr_28.gif]Conversely, suppose fundamental theorem of arithmetic in the integers _gr_29.gif] for any integers fundamental theorem of arithmetic in the integers _gr_30.gif] and fundamental theorem of arithmetic in the integers _gr_31.gif] To show that fundamental theorem of arithmetic in the integers _gr_32.gif] is prime let fundamental theorem of arithmetic in the integers _gr_33.gif] be a divisor of fundamental theorem of arithmetic in the integers _gr_34.gif] Then fundamental theorem of arithmetic in the integers _gr_35.gif] for some fundamental theorem of arithmetic in the integers _gr_36.gif] and so fundamental theorem of arithmetic in the integers _gr_37.gif] or fundamental theorem of arithmetic in the integers _gr_38.gif] Thus, if fundamental theorem of arithmetic in the integers _gr_39.gif] for some fundamental theorem of arithmetic in the integers _gr_40.gif] then fundamental theorem of arithmetic in the integers _gr_41.gif] and so fundamental theorem of arithmetic in the integers _gr_42.gif] If fundamental theorem of arithmetic in the integers _gr_43.gif] for some fundamental theorem of arithmetic in the integers _gr_44.gif] then fundamental theorem of arithmetic in the integers _gr_45.gif] and so fundamental theorem of arithmetic in the integers _gr_46.gif] as desired. fundamental theorem of arithmetic in the integers _gr_47.gif]
    (ii) fundamental theorem of arithmetic in the integers _gr_48.gif] The statement is clearly true when fundamental theorem of arithmetic in the integers _gr_49.gif] and fundamental theorem of arithmetic in the integers _gr_50.gif] is (i). Assume the statement is true for fundamental theorem of arithmetic in the integers _gr_51.gif] and suppose fundamental theorem of arithmetic in the integers _gr_52.gif] Then by (i), fundamental theorem of arithmetic in the integers _gr_53.gif] or fundamental theorem of arithmetic in the integers _gr_54.gif] So by the induction hypothesis there is some fundamental theorem of arithmetic in the integers _gr_55.gif] such that fundamental theorem of arithmetic in the integers _gr_56.gif] or it may be the case that fundamental theorem of arithmetic in the integers _gr_57.gif] Therefore, there is some fundamental theorem of arithmetic in the integers _gr_58.gif] such that fundamental theorem of arithmetic in the integers _gr_59.gif] as desired.
    (iii) Consider the set fundamental theorem of arithmetic in the integers _gr_60.gif] consisting of all integers greater than 1 that are not a product of primes. Assume for a contradiction that fundamental theorem of arithmetic in the integers _gr_61.gif] is not empty, then by the Well-Ordering Axiom there is a least element say fundamental theorem of arithmetic in the integers _gr_62.gif] Then fundamental theorem of arithmetic in the integers _gr_63.gif] is itself not a prime number and so, fundamental theorem of arithmetic in the integers _gr_64.gif] where fundamental theorem of arithmetic in the integers _gr_65.gif] and fundamental theorem of arithmetic in the integers _gr_66.gif] Since fundamental theorem of arithmetic in the integers _gr_67.gif] is the least element in fundamental theorem of arithmetic in the integers _gr_68.gif] fundamental theorem of arithmetic in the integers _gr_69.gif] and fundamental theorem of arithmetic in the integers _gr_70.gif] are products of primes; and thus so is fundamental theorem of arithmetic in the integers _gr_71.gif] This contradiction shows that fundamental theorem of arithmetic in the integers _gr_72.gif] is empty and so every integer greater than fundamental theorem of arithmetic in the integers _gr_73.gif] is a product of primes. Therefore, every integer (except fundamental theorem of arithmetic in the integers _gr_74.gif]) is a product of primes because if fundamental theorem of arithmetic in the integers _gr_75.gif] and fundamental theorem of arithmetic in the integers _gr_76.gif] then fundamental theorem of arithmetic in the integers _gr_77.gif] is a product of primes as desired.
    (iv) Assume, as Euclid did, that there are only finitely many prime numbers say,   fundamental theorem of arithmetic in the integers _gr_78.gif] Consider fundamental theorem of arithmetic in the integers _gr_79.gif] which by (iii) must be a product of primes. Let's say fundamental theorem of arithmetic in the integers _gr_80.gif] and since fundamental theorem of arithmetic in the integers _gr_81.gif] we have fundamental theorem of arithmetic in the integers _gr_82.gif] Therefore, fundamental theorem of arithmetic in the integers _gr_83.gif] which can not be true. Therefore, there can not be a finite number of prime numbers, as desired. fundamental theorem of arithmetic in the integers _gr_84.gif]

Proposition (Fundamental Theorem of Arithmetic) Every integer fundamental theorem of arithmetic in the integers _gr_85.gif] can be written uniquely in the form fundamental theorem of arithmetic in the integers _gr_86.gif] where fundamental theorem of arithmetic in the integers _gr_87.gif] are prime numbers and fundamental theorem of arithmetic in the integers _gr_88.gif] 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 fundamental theorem of arithmetic in the integers _gr_89.gif] Assume that fundamental theorem of arithmetic in the integers _gr_90.gif] has two factorizations say fundamental theorem of arithmetic in the integers _gr_91.gif] and fundamental theorem of arithmetic in the integers _gr_92.gif] where fundamental theorem of arithmetic in the integers _gr_93.gif] and fundamental theorem of arithmetic in the integers _gr_94.gif] and the fundamental theorem of arithmetic in the integers _gr_95.gif] and fundamental theorem of arithmetic in the integers _gr_96.gif] are all positive for fundamental theorem of arithmetic in the integers _gr_97.gif] and fundamental theorem of arithmetic in the integers _gr_98.gif] By Euclid's Lemma, fundamental theorem of arithmetic in the integers _gr_99.gif] for some fundamental theorem of arithmetic in the integers _gr_100.gif] and fundamental theorem of arithmetic in the integers _gr_101.gif] for some fundamental theorem of arithmetic in the integers _gr_102.gif] Since all the numbers fundamental theorem of arithmetic in the integers _gr_103.gif] and fundamental theorem of arithmetic in the integers _gr_104.gif] are prime, we must have fundamental theorem of arithmetic in the integers _gr_105.gif] and fundamental theorem of arithmetic in the integers _gr_106.gif] Then fundamental theorem of arithmetic in the integers _gr_107.gif] since fundamental theorem of arithmetic in the integers _gr_108.gif] Let fundamental theorem of arithmetic in the integers _gr_109.gif] be the integer defined as

      fundamental theorem of arithmetic in the integers _gr_110.gif]

If fundamental theorem of arithmetic in the integers _gr_111.gif] then fundamental theorem of arithmetic in the integers _gr_112.gif] has a unique factorization. If fundamental theorem of arithmetic in the integers _gr_113.gif] then fundamental theorem of arithmetic in the integers _gr_114.gif] and fundamental theorem of arithmetic in the integers _gr_115.gif] has two factorizations. Both cases reveal that fundamental theorem of arithmetic in the integers _gr_116.gif] can not exist as desired. fundamental theorem of arithmetic in the integers _gr_117.gif]

Definition (Euler's φ-Function) For each integer fundamental theorem of arithmetic in the integers _gr_118.gif] let fundamental theorem of arithmetic in the integers _gr_119.gif] denote the number of positive integers less than fundamental theorem of arithmetic in the integers _gr_120.gif] and relatively prime to fundamental theorem of arithmetic in the integers _gr_121.gif] and let fundamental theorem of arithmetic in the integers _gr_122.gif] The function of fundamental theorem of arithmetic in the integers _gr_123.gif] is called the Euler's fundamental theorem of arithmetic in the integers _gr_124.gif]-function, or sometimes the totient function.

Proposition (Euler's φ-Function)

    (i) If fundamental theorem of arithmetic in the integers _gr_125.gif] is a prime number and fundamental theorem of arithmetic in the integers _gr_126.gif] is positive, then fundamental theorem of arithmetic in the integers _gr_127.gif]
    
    (ii) If fundamental theorem of arithmetic in the integers _gr_128.gif] and fundamental theorem of arithmetic in the integers _gr_129.gif]are different prime numbers, then fundamental theorem of arithmetic in the integers _gr_130.gif]
    
    (iii) If fundamental theorem of arithmetic in the integers _gr_131.gif] then fundamental theorem of arithmetic in the integers _gr_132.gif]
    
    (iv) If fundamental theorem of arithmetic in the integers _gr_133.gif] then fundamental theorem of arithmetic in the integers _gr_134.gif]
    
    (v) If fundamental theorem of arithmetic in the integers _gr_135.gif] is prime, then fundamental theorem of arithmetic in the integers _gr_136.gif]
    
    (vi) If fundamental theorem of arithmetic in the integers _gr_137.gif] is the unique prime factorization of fundamental theorem of arithmetic in the integers _gr_138.gif] then
fundamental theorem of arithmetic in the integers _gr_139.gif]   

    Proof. (i) By Euclid's Lemma, the integers fundamental theorem of arithmetic in the integers _gr_140.gif] such that fundamental theorem of arithmetic in the integers _gr_141.gif] and fundamental theorem of arithmetic in the integers _gr_142.gif] is divisible by fundamental theorem of arithmetic in the integers _gr_143.gif] are fundamental theorem of arithmetic in the integers _gr_144.gif] Thus the number of positive integers less than fundamental theorem of arithmetic in the integers _gr_145.gif] and relatively prime to fundamental theorem of arithmetic in the integers _gr_146.gif] is fundamental theorem of arithmetic in the integers _gr_147.gif]
    (ii) By Euclid's Lemma, an integer fundamental theorem of arithmetic in the integers _gr_148.gif] will satisfy fundamental theorem of arithmetic in the integers _gr_149.gif] if and only if fundamental theorem of arithmetic in the integers _gr_150.gif] or fundamental theorem of arithmetic in the integers _gr_151.gif] and the number of such fundamental theorem of arithmetic in the integers _gr_152.gif] is fundamental theorem of arithmetic in the integers _gr_153.gif] Thus the number of fundamental theorem of arithmetic in the integers _gr_154.gif] such that fundamental theorem of arithmetic in the integers _gr_155.gif] and fundamental theorem of arithmetic in the integers _gr_156.gif] is fundamental theorem of arithmetic in the integers _gr_157.gif] fundamental theorem of arithmetic in the integers _gr_158.gif]
    (iv) There are fundamental theorem of arithmetic in the integers _gr_159.gif] congruence classes which are represented by an integer relatively prime to fundamental theorem of arithmetic in the integers _gr_160.gif] in fundamental theorem of arithmetic in the integers _gr_161.gif] Let these representatives be fundamental theorem of arithmetic in the integers _gr_162.gif] The products fundamental theorem of arithmetic in the integers _gr_163.gif] are all distinct because fundamental theorem of arithmetic in the integers _gr_164.gif] and since each product is still relatively prime to fundamental theorem of arithmetic in the integers _gr_165.gif] there is a representative from each of the fundamental theorem of arithmetic in the integers _gr_166.gif] congruence classes fundamental theorem of arithmetic in the integers _gr_167.gif] Therefore, fundamental theorem of arithmetic in the integers _gr_168.gif] fundamental theorem of arithmetic in the integers _gr_169.gif] fundamental theorem of arithmetic in the integers _gr_170.gif] Since fundamental theorem of arithmetic in the integers _gr_171.gif] fundamental theorem of arithmetic in the integers _gr_172.gif] as desired.
    (v) If fundamental theorem of arithmetic in the integers _gr_173.gif] then fundamental theorem of arithmetic in the integers _gr_174.gif] otherwise fundamental theorem of arithmetic in the integers _gr_175.gif] and so fundamental theorem of arithmetic in the integers _gr_176.gif] since fundamental theorem of arithmetic in the integers _gr_177.gif] Therefore, fundamental theorem of arithmetic in the integers _gr_178.gif] as desired. fundamental theorem of arithmetic in the integers _gr_179.gif]

Proposition (Group of Invertibles) Define the set   fundamental theorem of arithmetic in the integers _gr_180.gif] and define the operation fundamental theorem of arithmetic in the integers _gr_181.gif] on fundamental theorem of arithmetic in the integers _gr_182.gif] by fundamental theorem of arithmetic in the integers _gr_183.gif] then fundamental theorem of arithmetic in the integers _gr_184.gif] is an Abelian group of order fundamental theorem of arithmetic in the integers _gr_185.gif]

    Proof. The operation fundamental theorem of arithmetic in the integers _gr_186.gif] fundamental theorem of arithmetic in the integers _gr_187.gif] is a well-defined binary operation on fundamental theorem of arithmetic in the integers _gr_188.gif]; meaning, if fundamental theorem of arithmetic in the integers _gr_189.gif] and fundamental theorem of arithmetic in the integers _gr_190.gif] in fundamental theorem of arithmetic in the integers _gr_191.gif] then    fundamental theorem of arithmetic in the integers _gr_192.gif] fundamental theorem of arithmetic in the integers _gr_193.gif] fundamental theorem of arithmetic in the integers _gr_194.gif] fundamental theorem of arithmetic in the integers _gr_195.gif] which follows from fundamental theorem of arithmetic in the integers _gr_196.gif] and fundamental theorem of arithmetic in the integers _gr_197.gif] fundamental theorem of arithmetic in the integers _gr_198.gif] and since if fundamental theorem of arithmetic in the integers _gr_199.gif] and fundamental theorem of arithmetic in the integers _gr_200.gif] then there exists integers fundamental theorem of arithmetic in the integers _gr_201.gif] and fundamental theorem of arithmetic in the integers _gr_202.gif] such that   fundamental theorem of arithmetic in the integers _gr_203.gif] and fundamental theorem of arithmetic in the integers _gr_204.gif] and so fundamental theorem of arithmetic in the integers _gr_205.gif] which means fundamental theorem of arithmetic in the integers _gr_206.gif] Thus fundamental theorem of arithmetic in the integers _gr_207.gif] By the definition of fundamental theorem of arithmetic in the integers _gr_208.gif] and the use of associavity in the integers, it follows that fundamental theorem of arithmetic in the integers _gr_209.gif] fundamental theorem of arithmetic in the integers _gr_210.gif] fundamental theorem of arithmetic in the integers _gr_211.gif] fundamental theorem of arithmetic in the integers _gr_212.gif] fundamental theorem of arithmetic in the integers _gr_213.gif] fundamental theorem of arithmetic in the integers _gr_214.gif] for any fundamental theorem of arithmetic in the integers _gr_215.gif] fundamental theorem of arithmetic in the integers _gr_216.gif]  and fundamental theorem of arithmetic in the integers _gr_217.gif] The element fundamental theorem of arithmetic in the integers _gr_218.gif] is the identity because fundamental theorem of arithmetic in the integers _gr_219.gif] fundamental theorem of arithmetic in the integers _gr_220.gif] fundamental theorem of arithmetic in the integers _gr_221.gif] for any fundamental theorem of arithmetic in the integers _gr_222.gif] For every element fundamental theorem of arithmetic in the integers _gr_223.gif] of fundamental theorem of arithmetic in the integers _gr_224.gif] there is an inverse because fundamental theorem of arithmetic in the integers _gr_225.gif] yields  integers fundamental theorem of arithmetic in the integers _gr_226.gif] and fundamental theorem of arithmetic in the integers _gr_227.gif] such that fundamental theorem of arithmetic in the integers _gr_228.gif] Then fundamental theorem of arithmetic in the integers _gr_229.gif] and fundamental theorem of arithmetic in the integers _gr_230.gif] Commutativity follows since fundamental theorem of arithmetic in the integers _gr_231.gif] fundamental theorem of arithmetic in the integers _gr_232.gif] fundamental theorem of arithmetic in the integers _gr_233.gif] fundamental theorem of arithmetic in the integers _gr_234.gif] for fundamental theorem of arithmetic in the integers _gr_235.gif] fundamental theorem of arithmetic in the integers _gr_236.gif] fundamental theorem of arithmetic in the integers _gr_237.gif]

Example (Group of Invertibles) Construct the Cayley tables for fundamental theorem of arithmetic in the integers _gr_238.gif] and fundamental theorem of arithmetic in the integers _gr_239.gif]

fundamental theorem of arithmetic in the integers _gr_240.gif]            fundamental theorem of arithmetic in the integers _gr_241.gif]

fundamental theorem of arithmetic in the integers _gr_242.gif]

Cite this as:
Fundamental Theorem Of Arithmetic In The Integers
Published by Library of Math -- Online math organized by subject into topics.
Written by Smith, David A.
http://www.libraryofmath.com/fundamental-theorem-of-arithmetic-in-the-integers.html
 
    
Library of Math
Library of Math
Online Math Organized by Subject Into Topics
math search
Library of Math AddThis Feed Button
Online Math
Math Books
Custom math gifts on sale now.
Share your enthusiasm for mathematics!
Math People
Math Gifts
The Library of Math - Online Math Organized by Subject Into Topics.
© 2005 - 2008 www.LibraryOfMath.com All rights reserved.
about us | feedback | privacy policy | terms of use | mision statement | help

Page copy protected against web site content infringement by Copyscape Valid CSS! Valid HTML 4.01 Transitional Subscribe to the Library of Math Feed