# Thread: gcd(a,b) = 1 iff no primes divide a and b

1. ## gcd(a,b) = 1 iff no primes divide a and b

(i) if the gcd(a,b) = 1, then $p\nmid a \ \ \text{and} \ \ p\nmid b$

$1|a \ \ \text{and} \ \ 1|b$

$p|(pa) \ \ \text{and} \ \ p|(pb)$

$\Rightarrow p|a \ \ \text{or} \ \ p|p \ \ \text{and} \ \ p|b \ \ \text{or} \ \ p|p$

Since p|p, $p\nmid a \ \ \text{and} \ \ p\nmid b$

(ii) if $p\nmid a \ \ \text{and} \ \ p\nmid b$, then the gcd(a,b) = 1

$p\nmid a, \ \ p\nmid b, \ \ \text{and} \ \ p|p$

$p|(pa) \ \ \text{and} \ \ p|(pb)$

$\Rightarrow 1|a \ \ \text{and} \ \ 1|b$

$\Rightarrow 1=ar+bs \ \ r,s\in\mathbb{Z}$

$\Rightarrow \text{gcd}(a,b)=1$

Correct?

2. Originally Posted by dwsmith
(i) if the gcd(a,b) = 1, then $p\nmid a \ \ \text{and} \ \ p\nmid b$

$1|a \ \ \text{and} \ \ 1|b$

$p|(pa) \ \ \text{and} \ \ p|(pb)$

$\Rightarrow p|a \ \ \text{or} \ \ p|p \ \ \text{and} \ \ p|b \ \ \text{or} \ \ p|p$

Since p|p, $p\nmid a \ \ \text{and} \ \ p\nmid b$
Try including some words explaining what you are trying to achive (preferably at each step).

Here you are trying to prove that if $\gcd (a,b)=1$ then there is no prime $p$ that divides both $a$ and $b$. The neatest way to do this is by contradiction, suppose that $\gcd (a,b)=1$ and that there exists prime $p$ such that $p|a$ and $p|b$ and derive a contradiction.

(ii) if $p\nmid a \ \ \text{and} \ \ p\nmid b$, then the gcd(a,b) = 1

$p\nmid a, \ \ p\nmid b, \ \ \text{and} \ \ p|p$

$p|(pa) \ \ \text{and} \ \ p|(pb)$

$\Rightarrow 1|a \ \ \text{and} \ \ 1|b$

$\Rightarrow 1=ar+bs \ \ r,s\in\mathbb{Z}$

$\Rightarrow \text{gcd}(a,b)=1$

Correct?
Now you are trying to show that if for all primes $p$ that $p \nmid a$ and $p\nmid b$ then $\gcd(a,b)=1$.

Once again consider proof by contradiction ..

CB

3. For the first part then, I would have:

$\text{Since} \ \exists p \ \text{such that} \ p|a \ \text{and} \ p|b, \ p|1$

However, since 1 isn't prime, a prime number can't divide 1.

Thus, we have reached a contraction, and if the gcd(a,b) = 1, then no prime number divides both a and b.

4. Originally Posted by dwsmith
For the first part then, I would have:

$\text{Since} \ \exists p \ \text{such that} \ p|a \ \text{and} \ p|b, \ p|1$

However, since 1 isn't prime, a prime number can't divide 1.

Thus, we have reached a contraction, and if the gcd(a,b) = 1, then no prime number divides both a and b.
No;

Suppose $a,b \in \mathbb{R}$ such that $\gcd(a,b)=1$ and that there exists prime $p$ such that $p | a$ and $p | b$.

As $p | a$ and $p | b$ $p$ is a common divisor of $a$ and $b$, so $\gcd(a,b)\ge p >1$ a contradiction.

CB

5. 1) gcd(a,b)=1. Since all prime numbers > 1, no p exists that divides both a and b. No need to resort to contradiction imo

2) let no p divide both a and b and let gcd(a,b)=m. p divides m iff it divides both a and b. Since no p divides both a and b, then no p divides m. The only number that cannot be written as a product of primes is 1 so m =1

Q.E.D