Let a,b $\in$ Z and let a = p$_1$$^{\alpha_1}$...p$_n$$^{\alpha_n}$ and let b = q$_1$$^{\beta_1}$...q$_n$$^{\beta_n}$. Determine a condition on these two prime factorizations such that gcd(a,b) = 1.

So gcd(a,b) = 1 means that the integers a and b are relatively prime. Or the only common factor which divides each is 1.

So would that then impose the condition that these two prime factorizations necessarily need be distinct? If the greatest common divisor is 1 then that means that none of the bases (the 2 and 3 and 5 in, say; $2^3$ * $3^4$ * $5^7$) of one of the factorizations show up in the other factorization. So as an example if b includes a 2 in the factorization then a cannot have a 2 because in such a case both a and b would be divisible by 2 and thus not relatively prime. Is this correct?

  • $\begingroup$ Your answer is correct. You should write "primes" instead of "bases". That will be correct (by convention) even if some of the exponents happen to be prime. $\endgroup$ – Ethan Bolker Apr 6 '17 at 0:23
  • $\begingroup$ Thanks for the correction and validation, Ethan! $\endgroup$ – Kyle O'Connell Apr 6 '17 at 0:44

Indeed. If $\alpha_i, \beta_j \in \Bbb N$, $$a = \prod_{i=1}^n {p_i}^{\alpha_i}$$ and $$b = \prod_{j=1}^m q_j^{\beta_j}$$

where $p_i, q_j$ are primes then $\gcd(a, b) = 1 \iff p_i \neq q_j$ for all $i, j$.

Equivalently, we can think of these both as infinite products over all primes

$$a = \prod_{i} p_i^{\alpha_i}$$


$$b = \prod_{i} p_i^{\beta_i}$$

with only finitely many non-zero $\alpha_i, \beta_i$ so that the condition becomes

$$\gcd(a,b) = 1 \iff (\alpha_i \neq 0 \implies \beta_i = 0).$$

| cite | improve this answer | |
  • $\begingroup$ Excellent! Very elucidating response, I shall accept this as the answer. Thanks again for the help! $\endgroup$ – Kyle O'Connell Apr 6 '17 at 0:45

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.