Fundamental Theorem of Arithmetic...

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.