Fundamental Theorem of Arithmetic...

Printable View

• December 10th 2009, 02:50 PM
Pi R Squared
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.
• December 10th 2009, 03:44 PM
emakarov
Quote:

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.