Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Number Theory fundamental theorem of arithemetic

  1. Feb 25, 2012 #1
    I have two full questions on some number theory questions I've been working on, I guess my best bet would be to post them separately.

    1) Suppose that n is in N (natural numbers), p1,....,pn are distinct primes, and l1,....ln are nonnegative integers. Let m = p1l1p2l2....pnln. Let d be in N such that d ≥ 2 and d divides m.

    a) Using the fundamental theorem of arithemetic prove that p is a prime that divides d, then pi for some i in {1,...,n}.

    Attempt: Since d is in N and d ≥ 2, this means that d itself is a product of primes (prime factorization) or a prime itself. This means d = p1p2...pn (product of primes). Then there exists a p that divides d. (Since we are starting from 1 in the natural numbers)

    Is this the right idea and what would be a clearer way of writing this as a proof?

    b) Suppose the i is in {1,...,n}. Prove that pik does not divide d if
    k > li

    Attempt: if k > li then d ≠ pik, but d may equal any prime in m = p1l1p2l2....pnln since we know d | m.

    this would imply d has a cononical factorization : p1l1p2l2....pnln and we know k > li therefore pik does not divide d.

    Right idea?
    Last edited: Feb 25, 2012
  2. jcsd
  3. Feb 26, 2012 #2


    User Avatar
    Science Advisor

    "n" is sort of irrelevant to the proof, it just serves to underscore that m is a product of a finite number of prime powers.

    the important fact is that d|m.

    we suppose that p is a prime dividing d, and we want to prove that p is one of the prime factors listed in the given factorization of m.

    the fundamental theorem of arithmetic tells us the given factorization is unique.

    (well, it is if we list the primes pi in ascending order p1<...< pn).

    the first step should be to prove that p|m.

    the next step should involve this fundamental fact about primes:

    if p is a prime, and p|ab, then either p|a, or p|b (or perhaps both).

    under what circumstances will p|pili ?

    for part (b): suppose, by way of contradiction, that k > li, but that somehow pik divided d.

    wouldn't pik also divide m? re-write:

    m/(pik) in some form that leads to a contradiction (you may assume li = k+r, for some r > 0).


    to bring this "back to earth", let's see an example:

    suppose m = 72 = 8*9 = (23)(32).

    if d is any divisor of 72, can there be any prime factors of d besides 2 and 3? could any multiple of 5 be a divisor of 72? how about 7? what do you think?
  4. Feb 26, 2012 #3
    To work on the first portion of this, the only way I could come up with being able to show that p|m is by the fact that I'm told that d|m, since this is the case, d can be written as a product of primes (call them the series of q's). Since we know d | m, this means (series of q's)|m. From the fact of primes that if p is a prime and p | ab, then p|a or p|b, we can say since d|m => (series of q's)|m => (a q of series of q's)|p1 or (a q of series of q's)|p2 or .......(a q of series of q's)|pn

    I haven't been able to figure it out. Now thinking about it, I don't even think I proved that p|d.....smh.
  5. Feb 26, 2012 #4


    User Avatar
    Science Advisor


    if a|b and b|c, then a|c


    suppose a|b and b|c. then b = ka, for some integer k, and c = mb, for some integer m.

    hence: c = mb = m(ka) = (mk)a, so a|c, since mk is surely an integer.


    i think what is giving you trouble is you want to "factorize" d. well, you COULD...and you'd have a list of d as some product like:

    d = q1k1q2k2...qrkr,

    and then you'd have to show that each q equalled "some" p, and that each power was less than or equal to the corresponding power in the factorization of m. this is actually doable, but keeping track of the exponents and subscripts is tedious, and in the end, not very instructive.

    if p|d, and d|m....by the above theorem, p|m. think about this: we have a factorization of m into powers of primes, which we know is unique, and we have that p is a prime dividing m. how can p NOT be one of those primes in the factorization of m?

    if i asked you: which primes divide 32760, would you consider that "a hard problem?". is it possible that 11 divides 32760? what about 17, or 163? how would you even begin to start answering those problems?

    well, what if i told you that:

    32760 = (23)(32)(5)(7)(13)

    is it any clearer which primes divide 32760?


    for your second question....does 3 divide 16? 32? 64? does 3 divide ANY power of 2? does 3 divide any power of 7? does 3 divide any power of any other prime? can you generalize this to prime numbers besides 3?
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook