For a natural number , the Fundamental Theorem of Arithmetic claims that where all are primes (some primes may occur several times). In such case, let denote the multiset . The Fundamental Theorem also says that for each , is uniquely defined. E.g., .Prove that if a divides bn and a,b are relatively prime then a divides n

It is clear that . (Indeed, the right-hand side is one factorization of ; therefore, it is the only one.) Also, is a divisor of if and only if . The right-to-left direction is obvious, and if for some , then , so .

Finally, it is easy to show that if and only if .

All right, assume that divides and . Then and . Therefore, , i.e., divides .

Maybe this is not the "classical" and the simplest proof, but it should work.