# 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 $\displaystyle p\nmid a \ \ \text{and} \ \ p\nmid b$

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

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

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

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

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

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

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

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

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

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

Correct?

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

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

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

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

Since p|p, $\displaystyle 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 $\displaystyle \gcd (a,b)=1$ then there is no prime $\displaystyle p$ that divides both $\displaystyle a$ and $\displaystyle b$. The neatest way to do this is by contradiction, suppose that $\displaystyle \gcd (a,b)=1$ and that there exists prime $\displaystyle p$ such that $\displaystyle p|a$ and $\displaystyle p|b$ and derive a contradiction.

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

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

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

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

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

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

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

Once again consider proof by contradiction ..

CB

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

$\displaystyle \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:

$\displaystyle \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 $\displaystyle a,b \in \mathbb{R}$ such that $\displaystyle \gcd(a,b)=1$ and that there exists prime $\displaystyle p$ such that $\displaystyle p | a$ and $\displaystyle p | b$.

As $\displaystyle p | a$ and $\displaystyle p | b$ $\displaystyle p$ is a common divisor of $\displaystyle a$ and $\displaystyle b$, so $\displaystyle \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