Results 1 to 2 of 2

Thread: 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,577
    Thanks
    790
    Prove that if a divides bn and a,b are relatively prime then a divides n
    For a natural number $\displaystyle n\ge 2$, the Fundamental Theorem of Arithmetic claims that $\displaystyle n=p_1\cdot\dots\cdot p_k$ where all $\displaystyle p_i$ are primes $\displaystyle \ge 2$ (some primes may occur several times). In such case, let $\displaystyle Prime(n)$ denote the multiset $\displaystyle \{p_1,\dots,p_n\}$. The Fundamental Theorem also says that for each $\displaystyle n$, $\displaystyle Prime(n)$ is uniquely defined. E.g., $\displaystyle Prime(12)=\{2,2,3\}$.

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

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

    All right, assume that $\displaystyle a$ divides $\displaystyle bn$ and $\displaystyle \gcd(a,b)=1$. Then $\displaystyle Prime(a)\subseteq Prime(b)\cup Prime(n)$ and $\displaystyle Prime(a)\cap Prime(b)=\emptyset$. Therefore, $\displaystyle Prime(a)\subseteq Prime(n)$, i.e., $\displaystyle a$ divides $\displaystyle 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: Feb 15th 2010, 04:31 PM
  3. Fundamental Theorem of Arithmetic
    Posted in the Number Theory Forum
    Replies: 8
    Last Post: Mar 19th 2007, 02:53 PM
  4. Fundamental Theorem of Arithmetic Help
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: Feb 24th 2007, 03:41 PM

Search Tags


/mathhelpforum @mathhelpforum