Results 1 to 2 of 2

Math Help - Fundamental Theorem of Arithmetic...

  1. #1
    Newbie Pi R Squared's Avatar
    Joined
    Oct 2009
    Posts
    13

    Question Fundamental Theorem of Arithmetic...

    I am having a difficult time understanding this. I have a question I need to solve.

    Prove that if a divides bn and a,b are relatively prime then a divides n.

    If I understand correct, for an integer to be relatively prime means that gcd{a,b}=1.

    I think I also understand the idea. I just do not understand how to start a proof of this nature. I am really confused...

    Any help would be appreciated. I do not want a complete answer, just some guidance.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,517
    Thanks
    771
    Prove that if a divides bn and a,b are relatively prime then a divides n
    For a natural number n\ge 2, the Fundamental Theorem of Arithmetic claims that n=p_1\cdot\dots\cdot p_k where all p_i are primes \ge 2 (some primes may occur several times). In such case, let Prime(n) denote the multiset \{p_1,\dots,p_n\}. The Fundamental Theorem also says that for each n, Prime(n) is uniquely defined. E.g., Prime(12)=\{2,2,3\}.

    It is clear that Prime(mn)=Prime(m)\cup Prime(n). (Indeed, the right-hand side is one factorization of mn; therefore, it is the only one.) Also, k is a divisor of m if and only if Prime(k)\subseteq Prime(m). The right-to-left direction is obvious, and if kn=m for some n, then Prime(kn)=Prime(k)\cup Prime(n)=Prime(m), so Prime(k)\subseteq Prime(m).

    Finally, it is easy to show that Prime(m)\cap Prime(n)=\emptyset if and only if \gcd(m,n)=1.

    All right, assume that a divides bn and \gcd(a,b)=1. Then Prime(a)\subseteq Prime(b)\cup Prime(n) and Prime(a)\cap Prime(b)=\emptyset. Therefore, Prime(a)\subseteq Prime(n), i.e., a divides n.

    Maybe this is not the "classical" and the simplest proof, but it should work.
    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 Number Theory Forum
    Replies: 8
    Last Post: March 19th 2007, 02:53 PM
  4. Fundamental Theorem of Arithmetic Help
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: February 24th 2007, 03:41 PM

Search Tags


/mathhelpforum @mathhelpforum