# Thread: Fundamental Theorem of Arithmetic...

1. ## 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.

2. 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.