Results 1 to 4 of 4

Math Help - Fundamental theory of arithmetic

  1. #1
    Newbie
    Joined
    Nov 2012
    From
    india
    Posts
    2

    Exclamation Fundamental theory of arithmetic

    Hi,

    I want to prove fundamental theorem of arithmetic by using strong induction and proof by smallest counterexample.
    Can someone by any chance help me? (with great detail please)?

    I would appreciate people's help.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Nov 2012
    From
    india
    Posts
    2

    Re: Fundamental theory of arithmetic

    Can anybody please help me please?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,530
    Thanks
    774

    Re: Fundamental theory of arithmetic

    I am not sure about smallest counterexamples, but for the inductive proof of the fundamental theorem of arithmetic see Wikipedia.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,386
    Thanks
    752

    Re: Fundamental theory of arithmetic

    if the theorem is not true, there exists a minimal counter-example, a.

    by supposition, there exists two distinct prime factorizations of a:

    a = p_1^{k_1}p_2^{k_2}\cdots p_r^{k_r} = q_1^{m_1}q_2^{m_2}\cdots q_s^{m_s} with p_1 < p_2 < \cdots < p_r, q_1 < q_2 < \cdots < q_s.

    now p_1|a so p_1|q_i^{m_i} for some i = 1,2,...,s.

    this, in turn, implies p_1|q_i. since q_i is prime, and p_1 \neq 1, we conclude p_1 = q_i.

    thus since \frac{a}{p_1^{k_1}} < a,

    we conclude that p_2^{k_2}\cdots p_r^{k_r} = \frac{q_1^{m_1}q_2^{m_2}\cdots q_s^{m_s}}{q_i^{m_i}} are, in fact, the same factorization.

    hence since we have r-1 factors on the left, and s-1 factors on the right:

    r - 1 = s - 1, so r = s.

    we now have two possibilities:

    i = 1 (on the RHS),
    i ≠ 1.

    if i ≠ 1, then q1 = p2, which implies p2 = q1 < qi = p1, contradicting our original factorization of a.

    thus we must have p1 = q1, and since the factorization of \frac{a}{p_1^{k_1}} IS unique,

    pi = qi for all i > 1, and ki = mi, for all i > 1.

    thus the only difference between:

    a = p_1^{k_1}p_2^{k_2}\cdots p_r^{k_r} = p_1^{m_1}p_2^{k_2}\cdots p_r^{k_r}

    is the power of p1.

    but p_1^{k_1} = \frac{a}{p_2^{k_2}\cdots p_r^{k_r}} < a, so we must have k1 = m1, and a does not exist, which proves the theorem.
    Last edited by Deveno; November 15th 2012 at 02:46 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof Using Fundamental Thm of Arithmetic
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: May 10th 2011, 03:52 PM
  2. Fundamental Theorem of Arithmetic
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: February 15th 2010, 04:31 PM
  3. Fundamental Theorem of Arithmetic...
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: December 10th 2009, 03:44 PM
  4. Fundamental Theorem of Arithmetic
    Posted in the Number Theory Forum
    Replies: 8
    Last Post: March 19th 2007, 02:53 PM

Search Tags


/mathhelpforum @mathhelpforum