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

I Fundamental Theorem of Arithmetic - Bhattacharya et al

  1. Sep 4, 2016 #1
    I am reading the book, Basic Abstract Algebra by P.B. Bhattacharya, S.K. Jain, and S.R. Nagpaul ... ... and am currently focused on Chapter 2: Integers, Real Numbers and Complex Numbers ...


    I need help with an aspect of the proof of the Fundamental Theorem of Arithmetic in Section 1.3 ... ...


    The Fundamental Theorem of Arithmetic and its proof as presented by Bhattacharya et al reads as follows:


    ?temp_hash=527395e91194c9b9972ae8b938d4b624.png
    ?temp_hash=527395e91194c9b9972ae8b938d4b624.png




    In the above text we read the following:


    " ... ... So let ##p_1 \neq q_1##. For definiteness, let ##p_1 \gt q_1##. Then

    ##n \gt (p_1 - q_1) p_2 \ ... \ p_s = p_1p_2 \ ... \ p_s - q_1p_2 \ ... \ p_s##

    ##= q_1q_2 \ ... \ q_t - q_1p_2 \ ... \ p_s = q_1 (q_2 \ ... \ q_t - p_2 \ ... \ p_s)##

    By the induction hypothesis either ##q_1 = p_i## for some ##i = 2, \ ... \ , s## or

    ##q_1 | (p_1 - q_1)##. ... ... "


    I do not follow how

    ##n \gt (p_1 - q_1) p_2 \ ... \ p_s = p_1p_2 \ ... \ p_s - q_1p_2 \ ... \ p_s##

    ##= q_1q_2 \ ... \ q_t - q_1p_2 \ ... \ p_s = q_1 (q_2 \ ... \ q_t - p_2 \ ... \ p_s)##

    leads to

    either ##q_1 = p_i## for some ##i = 2, \ ... \ , s## or ##q_1 | (p_1 - q_1)##. ... ...



    Can someone slowly and clearly explain exactly how the above follows ...


    Hope someone can help ... ...

    Peter

    ======================================================


    The above refers to what Bhattacharya et al call the Second Principle of Induction ... this principle reads as follows in their text ... ... :


    ?temp_hash=527395e91194c9b9972ae8b938d4b624.png
     

    Attached Files:

  2. jcsd
  3. Sep 4, 2016 #2

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    The basis of this proof is that, if the FTA does not hold, then there must be a least whole number that has a non-unique prime factorisation. He's assuming that

    ##n = p_1 \dots p_s = q_1 \dots q_t##

    is that whole number. And that any whole number less than ##n## must, therefore, have a unique prime factorisation.

    I would change the proof slightly. If the two prime factorisations are different, then we know that they have no primes in common (otherwise we could cancel the common prime). In particular, this means that (without loss of generality) ##p_1 > q_1## and ##q_1## is distinct from all the ##p's##.

    Now, a bit of algebra gives:

    ##n > m = (p_1 -q_1)p_2 \dots p_s = q_1(q_2 \dots q_t - p_2 \dots p_s)##

    Now, this number ##m## is less than ##n## so must have a unique prime factorisation. In particular, ##q_1## must appear in the prime factorisation of ##(p_1 -q_1)p_2 \dots p_s##.

    And, as we know ##q_1## is distinct from the ##p's## (*) it must appear in the prime factorisation of ##(p_1 -q_1)## and so, in fact, ##p_1 = q_1##, which is a contradiction. You might want to prove this last bit yourself.

    (*) note also that ##p_2 \dots p_s < n## so has a unique prime factorisation and cannot have an alternative factorisation involving ##q_1##.
     
  4. Sep 4, 2016 #3
    Thanks for the help PeroK ... much appreciated...

    ... just working through your post now ...

    Thanks again,

    Peter
     
  5. Sep 5, 2016 #4

    PeroK,

    Thanks again for your help ...

    BUT ... I need help to show that ##q_1## appearing in the prime factorization of ##(p_1 -q_1)## leads to ##p_1 = q_1## ... ...

    Can you help further ...

    Peter
     
  6. Sep 5, 2016 #5

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Yes, but if you can't do something simple like that for yourself, then you are going to struggle.

    ##p_1 - q_1 = rq_1## for some ##r##

    ##p_1 = (r+1)q_1##

    (That itself could be taken to be the contradiction, as you have an alternative prime factorisation for ##p_1##)

    Or, to continue:

    ##r = 0## and ##p_1 = q_1##

    You need to get used to doing this for yourself. You can't learn number theory by letting Bhattacharya (or me) just spoon feed you all the steps.
     
  7. Sep 5, 2016 #6
    Thanks again for your help,

    Peter
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted