1. PF Contest - Win "Conquering the Physics GRE" book! Click Here to Enter
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Fundamental Theorem of Arithmetic

  1. Aug 9, 2010 #1
    1. The problem statement, all variables and given/known data

    Theorem. (Fundamental Theorem of Arithmetic) Ever positive integer n has a prime factorization, which is unique except for reordering of the factors.

    2. Relevant equations

    6.8 Definition. A prime factorization of n expresses n as a product of powers of distinct primes; the exponent of each prime is its multiplicity. We write a prime factorization of n as n=[tex]\prod[/tex][tex]^{k}_{i=1}[/tex]piei.

    3. The attempt at a solution

    [PLAIN]http://icanhascheezburger.files.wordpress.com/2007/09/128320993454987500dudewaitw.jpg [Broken]

    If n is a prime, of course it has a prime factorization. n = n1. I'm trying to find out how to construct a general proof.

    Suppose n = p1e1 * p2e2 * ... * pkek

    or something. Give me a jump-start.
    Last edited by a moderator: May 4, 2017
  2. jcsd
  3. Aug 9, 2010 #2
    Here are sketches of the proofs. You'll have to fill in the details however.

    Two parts here: Existence (every positive integer has a prime factorization) and Uniqueness (that prime factorization is unique).

    Existence is easy. Uniqueness is not as easy.

    For existence, assume there are numbers that cannot be written as the product of primes. Then there must be a smallest such number. Show that this leads to a contradiction. (Hint: if the number were prime, it would automatically just be itself^1. So it must be composite, etc.)

    For uniqueness, assume there are numbers that can be written as different products of primes. Again take the smallest such number. Write the two factorizations as products of primes. First prove that none of the prime factors can be the same between the two factorizations. Then, pick the smallest factor in either factorization. Divide one of the factors of the other factorization by the smallest factor (you get a remainder). Substitute the quotient + remainder into the factorization. Now show that the "remainder" part of the factorization also has two prime factorizations, which contradicts our assumption that this is the smallest such number.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook