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.


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

  • $\begingroup$ But doesn't it mean that if gcd(a,b)=1 then a and b are primes. How then they have prime factorization? $\endgroup$ – user2723 Sep 12 '11 at 15:20
  • $\begingroup$ @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. $\endgroup$ – 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.

  • $\begingroup$ can you please tell me what the "|" means? $\endgroup$ – Pavel Feb 7 '16 at 19:19
  • $\begingroup$ @paulpaul1076 It means "divides" (standard number theory notation) $\endgroup$ – Bill Dubuque Feb 9 '16 at 20:09
  • $\begingroup$ thanks, I have only seen the three dots notation for that. $\endgroup$ – Pavel Feb 9 '16 at 20:41
  • $\begingroup$ @paulpaul1076 That's relatively rare. The above notation is by far the most widely used. $\endgroup$ – Bill Dubuque Feb 9 '16 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$.

  • $\begingroup$ 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$? $\endgroup$ – user2723 Sep 12 '11 at 7:35
  • $\begingroup$ @alvoutila, I've edited my answer to give a complete solution, incorporating Eric's hint. $\endgroup$ – lhf Sep 12 '11 at 11:12
  • $\begingroup$ 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? $\endgroup$ – user2723 Sep 12 '11 at 18:00
  • 2
    $\begingroup$ @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. $\endgroup$ – 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.$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy