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
I think this is a real question, effort or no effort. – anon Sep 10 '11 at 19:09
@anon Indeed, it is rather sad that folks are voting to close valid questions. What for, lack of "research effort"? I'm not aware of any rules here that say such is required (vs. recommended). – Bill Dubuque Sep 10 '11 at 19:58
@Thi One should keep in mind that answers teach far many more readers than only the questioner. So even poorly presented questions can lead to answers that may benefit many readers - both now, and in the future (from searches either on site or from web search engines). – Bill Dubuque Sep 11 '11 at 17:52
@Thi Yes, I understood that. My remark was concerned with closing (vs. downvoting), and targeted at all readers who might consider doing so in the future. – Bill Dubuque Sep 11 '11 at 18:27
@Bill (and others) I am fairly sure that the folks voting to close (honestly don't remember, whether I'm among them in the present case) are basically resorting to all measures open to them to express extreme displeasure of the way the OP is (ab)using this site to get homework done. Your concern is a valid one, though. Selecting "not a real question" as the reason is anything but ideal, but there is no appropriate alternative. I certainly don't know the best way of handling the problem. It is probably best to move that discussion to meta as the problem is not limited to this question. – Jyrki Lahtonen Sep 12 '11 at 12:39
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

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.