1
$\begingroup$

I'm doing a little research on elementary number theory, and found this question online. I thought it should be easy for me to prove, but that seemed not to be true:

Let $p, q$ be primes.
Prove: gcd($x, pq$) = 1 $\Rightarrow$ gcd($x, p$) = 1 and gcd($x, q$) = 1

I tried rewriting this to: $1 = ax + bpq$ for some integers $a, b$ (using the extended euclidean algorithm) but I got stuck there, so I think that isn't the right approach.

$\endgroup$
  • 2
    $\begingroup$ You don't need $p,q$ to be primes. If $d\,|\,x$ and $d\,|\,p$ then $d\,|\,pq\implies d\,|\,\gcd(x,pq)$. $\endgroup$ – lulu Mar 12 '17 at 11:06
1
$\begingroup$

Since $\operatorname{gcd}(x, pq)=1$, we have $ax+bpq=1$ for some $a, b\in \mathbb{Z}$. But then $ax+(bp) q=1$ gives $\operatorname{gcd}(x, q)=1$ whereas $ax+(bq) p=1$ gives $\operatorname{gcd}(x, p)=1$.

$\endgroup$
  • $\begingroup$ Wonderful, thank you! $\endgroup$ – Peter Mar 12 '17 at 11:24
2
$\begingroup$

You have to fix the reasoning.

Because $gcd(x,pq) = 1$, there exist $a, b$ with $ax + bpq = 1$.

Then also $ax + (bp)q = ax + (bq)p = 1$ so you have numbers to prove the RHS.

(And it does not have to be $1$, it can be any $gcd$)

$\endgroup$
1
$\begingroup$

Because gcd(x,pq)=1gcd(x,pq)=1, there exist a,ba,b with ax+bpq=1ax+bpq=1.

Then also ax+(bp)q=ax+(bq)p=1ax+(bp)q=ax+(bq)p=1 so you have numbers to prove the RHS.

$\endgroup$

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.