1
$\begingroup$

How to show that $p \nmid a \Rightarrow \gcd(p,a)=1$?

If we have canonical representations of $p= q_1^{b_1} \cdots q_n^{b_n}$ and $a= r_1^{c_1} \cdots r_k^{c_k}$, then because $p \nmid a$, $q_i \neq r_j$ for all $i=1, \dots, n$ and $j=1, \dots k \Rightarrow \gcd(p,a)=1$.

$\endgroup$
1
  • 3
    $\begingroup$ This problem is poorly stated. It's true that if $p = q_1^{b_1}\dots q_n^{b_n}$ and $a=r_1^{c_1}\dots r_k^{c_k}$ with $q_i \neq r_j$ then gcd$(p,a)=1$. But it's not true that if $p$ doesn't divide $a$ then gcd$(p,a)=1$. For instance, 6 doesn't divide 10 but gcd$(6,10)=2$. Ask yourself, is it possible for gcd$(q_i,r_j)>1$? $\endgroup$ Nov 19 '11 at 17:54
3
$\begingroup$

I think the problem must have come from a source that assumes $p$ is prime.

That means your second paragraph is barking up the wrong tree.

Suppose $\gcd(a,p)=m\ne 1$. Then $m$ is a common divisor of $a$ and $p$. That means $m$ divides $a$ and $m$ divides $p$. If $m$ divides $p$ and $p$ is prime, then $m = \text{either }1\text{ or }p$. We've ruled out $1$, so $m=p$. If $m$ divides $a$ and $m=p$, then $p$ divides $a$. But you ruled that out at the beginning.

$\endgroup$

Your Answer

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