Statement: Suppose $(a,b) = 1$ then $(a^n,b^k) = 1$ for $n,k \geq 1$.

Attempt at Proof: Let $P$ be the set of all primes. Let $P_a$ be the set of primes $p_i$ such that

$$a = \prod_{i=1}^{r_1} p_i^{\alpha_i}.$$ Let $P_b$ be the set of primes $q_i$ such that $$b = \prod_{i=1}^{r_2} p_i^{\beta_i}.$$

Since $(a,b) = 1$, we have $P_a \cap P_b = \emptyset$.

Write $a = \prod_{i=1}^{\infty} p_i^{\alpha_i}$ where $\alpha_i = 0$ if $p_i \notin P_a$. Write $b = \prod_{i=1}^{\infty} q_i^{\beta_i}$, where $\beta_i = 0$ if $q_i \notin P_b$. Thus, $a^n = \prod_{i=1}^{\infty} p_i^{n\alpha_i}$ and $b^k = \prod_{i=1}^{\infty} q_i^{k\beta_i}$. By theorem 1.12 (Apostol Analytic Number Theory), we may write

$$(a^n,b^k) = \prod_{P_a} p_i^{c_i} \prod_{P_b} q_i^{c_i} \prod_{P \setminus (P_a \cup P_b)} s_i^{c_i}.$$

Where $c_i = \min\{n\alpha_i,k\beta_i\}.$ But, $c_i = 0$ for all $P_a,P_b$ by the above discussion and clearly $c_i = 0$ for $P \setminus (P_a \cup P_b).$ Thus, the above product is $1$, so $$(a^n,b^k) = 1$$ as desired.

Are there any issues with this proof? This is my first day of number theory, so I'm a bit unfamiliar with the proof structures.

  • $\begingroup$ The only issue is that is unnecesarily long. The essential fact is that $a$ and $b$ don't have common prime factors. $\endgroup$ – Martín-Blas Pérez Pinilla Jan 21 '16 at 17:57
  • $\begingroup$ @Martín-BlasPérezPinilla Agreed. $\endgroup$ – Anthony Peter Jan 21 '16 at 17:59

Much easier: as $p|rs, p\text{ prime}\implies p|r\text{ or }p|s$: $$p|a^n\text{ and }p|b^k\implies p|a\text{ and }p|b.$$

  • 1
    $\begingroup$ How silly of me, thank you. I've gone from a second course in graduate analysis to a first course in number theory, so I'm trying to get over the feelings of suspicion for such short proofs $\endgroup$ – Anthony Peter Jan 21 '16 at 17:56

Here is a proof without resorting to prime factorisations: $\gcd(a, b)$ means that there are integers $x, y$ such that $$ ax + by = 1 $$ If we raise each side of this equality to the power of $n+k-1$ and use the binomial theorem, we get $$ (a + b)^{n+k-1} = 1^{n+k-1}\\ a^{n+k-1} + \cdots + \binom{n+k-1}{k-1}a^nb^{k-1} + \binom{n+k-1}{k}a^{n-1}b^k + \cdots + b^k = 1\\ a^n\left(a^{k-1} + \cdots + \binom{n+k-1}{k-1}b^{k-1}\right) + b^k\left(\binom{n+k-1}{k}a^{n-1} + \cdots + b^{n-1}\right) = 1 $$ which means that $\gcd(a^n, b^k) = 1$ as well.


Your Answer

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

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