Originally, I was examining $\gcd(a,x) = 1, \gcd(b,x) = 1$ and conjectured $\gcd(ab,x) = 1$. I think this is true, because I thought:

Let $x = p_1^{a_1}\cdot p_2^{a_2}\cdot p_3^{a_3}\dots$

$a\neq 0\pmod{p_1}$

$a\neq 0\pmod{p_2}$

$a\neq 0\pmod{p_3} \dots$

And similarly for $b$, we must have

$ab\neq 0\pmod{p_1}$

$ab\neq 0\pmod{p_2}$

$ab\neq 0\pmod{p_3} \dots$

And hence $\gcd(ab,x) = 1$. (Verify? I'm still a bit iffy on this)

If this is true, however, then if $\gcd(a,x) = \gcd(b,x) = k$ for some $k$ a product of distinct prime numbers, then $\gcd(ab,x) = k$ because for each of the primes in $k$'s factorization we have both $a,b = 0 \pmod p$ and for every other prime both $a,b \neq 0 \pmod p$.

Is this generally true for every number $k$, rather than just all $k$ a product of distinct primes? Does $\gcd(a,x) = \gcd(b,x) = 12 \implies \gcd(ab,x) = 12$?

  • $\begingroup$ It's true for $k = 1$, but not for $k > 1$. Let $a = k,\, b = p\cdot k$ where $p$ is a prime not dividing $k$, and take $x = k^2$. $\endgroup$ – Daniel Fischer Jul 1 '15 at 10:44
  • $\begingroup$ Can it take values other than $k$ and $k^2$? $\endgroup$ – user242594 Jul 1 '15 at 11:14
  • $\begingroup$ Yes, let for example $k = 6$, $a = 30, b = 42, x \in \{12,18\}$. $\endgroup$ – Daniel Fischer Jul 1 '15 at 11:18

gcd(3,9)=gcd(3,9)=3 but gcd(3*3,9)=9


Your Answer

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