Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

How to use fundamental theorem of arithmetic to conclude that $\gcd(a^k,b^n)=1$ for all $k, n \in$ N whenever $a,b \in$ N with $\gcd(a,b)=1$?

Fundamental theorem of arithmetic: Each number $n\geq 2$ can be presented in an unique way as a product $n=p_1^{a_1}p_2^{a_2} \dots p_r^{a_r}$, where $p_i$ are primes $p_1<p_2< \dots <p_r$ and $a_i \in$ N.

share|cite|improve this question
up vote 10 down vote accepted

Hint: $\gcd(a,b)=1$ if and only if $a$ and $b$ share no prime factors.

share|cite|improve this answer
But doesn't it mean that if gcd(a,b)=1 then a and b are primes. How then they have prime factorization? – alvoutila Sep 12 '11 at 15:20
@alvoutila: $\gcd(a,b)=1$ does not mean that $a$ and $b$ are primes. Instead, $\gcd(a,b)=1$ means that if $d>0$ divides both $a$ and $b$, then $d$ must be $1$. Example: $\gcd(24,35)=1$, but neither are primes. – Eric Naslund Sep 12 '11 at 21:24

Hint $\rm\ $ prime $\rm\ p\: |\: n^k\ \Rightarrow\ p\: |\: n\ $ by uniqueness of prime factorizations.

Note $\ $ In fact uniqueness of factorizations into primes (i.e. atoms) is equivalent to the following

Prime Divisor Property $\rm\quad p\ |\ a\:b\ \Rightarrow\ p\:|\:a\ $ or $\rm\ p\:|\:b,\ $ for all primes $\rm\:p\,;\:\: $ more generally

Primal Divisor Property $\rm\ \ \: c\ |\ a\:b\ \Rightarrow\ c_1\, |\: a\:,\: $ $\rm\ c_2\:|\:b,\ \ c = c_1\:c_2,\ $ for all $\rm\:c$

The latter property may be considered to be a generalization of the prime divisor property from atoms to composites (one easily checks that atoms are primal $\Leftrightarrow$ prime). This leads to various "refinement" views of unique factorizations, e.g. via Schreier refinement and Riesz interpolation, the Euclid-Euler Four Number Theorem (Vierzahlensatz), etc, which prove more natural in noncommutative rings - see Paul Cohn's 1973 Monthly survey Unique Factorization Domains.

share|cite|improve this answer
can you please tell me what the "|" means? – Pavel Orekhov Feb 7 at 19:19
@paulpaul1076 It means "divides" (standard number theory notation) – Bill Dubuque Feb 9 at 20:09
thanks, I have only seen the three dots notation for that. – Pavel Orekhov Feb 9 at 20:41
@paulpaul1076 That's relatively rare. The above notation is by far the most widely used. – Bill Dubuque Feb 9 at 21:08

The prime factors of $a^k$ are exactly the same as the prime factors of $a$. Hence, a prime $p$ divides both $a^k$ and $b^n$ iff it divides both $a$ and $b$. Furthermore, $\gcd(a,b)=1$ iff $a$ and $b$ share no prime factors. Thus $\gcd(a^k,b^n)=1$ iff $\gcd(a,b)=1$.

share|cite|improve this answer
do you mean that if $a= p_1^{a_1}p_2^{a_2} \dots p_r^{a_r}$ then $a^k =p_1^{ka_1}p_2^{ka_2} \dots p_r^{ka_r}$ But then how conclude from here that $gcd(a^k, a^n)=1$? And besides that if gcd(a,b)=1 then a and b are primes so how you get prime factorization for these numbers not to mention to $a^k$? – alvoutila Sep 12 '11 at 7:35
@alvoutila, I've edited my answer to give a complete solution, incorporating Eric's hint. – lhf Sep 12 '11 at 11:12
I still am uncertain because I thought that is gcd(a,b)=1 it would mean that a and b are primes? Is this true? But if it is true that gcd(a,b)=1 => 1|a and 1|b, then it might mean that they are primes. So how is it possible to say that they don't prime factors, when there are no factors, because they are already primes? – alvoutila Sep 12 '11 at 18:00
@alvoutila, $\gcd(a,b)=1$ means that $a$ and $b$ are coprime, that is, they have no prime factors in common. It does not mean that $a$ and $b$ are prime. For instance $12$ and $35$ are coprime but neither is prime. – lhf Sep 12 '11 at 18:03

One way to go about this is to first prove that $(a,b) = 1$ and $(a,c) =1$ implies $(a, bc)=1$. Your problem then follows by induction.

To prove the lemma, notice that $ax + by = 1$ and $az + cw = 1$ imply

$$ax + by(az+cw) = 1$$ $$ax + byaz + (bc)yw = 1$$ $$a(x+byz) + bc (yw) = 1.$$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.