# Homework Help: Co-Primes Proof

1. May 19, 2014

### knowLittle

1. The problem statement, all variables and given/known data
Let $n \in \mathbb{Z} , n \not | 3$. Prove that $gcd( n , n +3 ) =1$

3. The attempt at a solution
If n is not divisible by 3, then
n = 3k+1 or n =3k+2 , $k \in \mathbb{Z}$

What is a feasible approach? Can I do this?
For first case,
$gcd(3k+1, 3k+4 ) = 1 \\ \exists s,t \in \mathbb{Z} \\ 1 =(3k+1)s + (3k+4)t$

2. May 19, 2014

### micromass

I would just use the definition. Assume that there is an integer $d$ that divides both $n$ and $n+3$, then...

3. May 19, 2014

### knowLittle

Thanks.

You mean state Euclid's lemma?
Let $a,b,c \in \mathbb{Z} \wedge a \not = 0$ . If $a|bc \wedge gcd(a,b) =1 ,$then $a|c$

$n | (n+3)c , c \in \mathbb{Z} \\ n| c$?

4. May 19, 2014

### micromass

I don't see how this is applicable here. Just use the definitions.

5. May 19, 2014

### knowLittle

$d| n+3 \\ d|n \\ n =dk \wedge n +3 = dp, p,k \in \mathbb{Z} \\ 3=d(p-k)$

Since p-k is an integer, d|3 ?
I don't get where is the connection of $d$ with $n$ not divisible by 3.

6. May 19, 2014

### micromass

Ok, so you found that $d$ divides $3$. Can you then list all the possible values that $d$ can be?

7. May 19, 2014

### knowLittle

Since 3 is prime d can be 1 or 3.

8. May 19, 2014

### micromass

So you need to prove that $d=3$ can't happen.

9. May 19, 2014

### knowLittle

So,

$d=3 \\ n =3k \\ n+3 =3p \\ gcd(n, n+3 ) =1 \\ nh + (n+3)x =1, h,x \in \mathbb{Z} \\ 3(kh+px) =1, kh+px \in \mathbb{Z}$

Then, 3|1; however, 1 =3y is impossible, since y must be integer.
So, necessarily d =1 only.

I still don't see the connection. Are we assuming that $d \equiv n$?

10. May 19, 2014

### Curious3141

Again, you're overthinking the problem.

If a number divides two distinct numbers, then it also divides their difference. Hence d divides 3. Since 3 is prime, that means d can be 3 or 1.

Since d divides n, and d = 3, does 3 divide n? Does that violate any of the stipulations of the question? What does that leave you with as a possible value of d?

11. May 19, 2014

### knowLittle

So, d | n
d =3

does 3 |n ?
Well, the stipulations say that $n$ is not divisible by 3. $n\not | 3$
Sorry, but again I am lost.
$(n = 3k )\not = (3 \not = np), k,p \in \mathbb{Z}$

12. May 19, 2014

### Curious3141

You KNOW that $d \mid n.$ (Fact 1)

You KNOW that $d \mid 3.$ (Fact 2)

You KNOW that $3 \nmid n.$ (Fact 3)

Fact 2 implies that $d=1$ (possibility 1) or $d=3$ (possibility 2) because 3 is prime.

IF possibility 2 were true, THEN by Fact 1, $3 \mid n$. But this cannot be so because it would conflict with Fact 3. Therefore possibility 2 is rejected.

That leaves only possibility 1, i.e. $d=1$. The only possible common divisor for $n$ and $n+3$ where $3 \nmid n$ is 1. Therefore, this is also the greatest common divisor.

By the way, you're using the non-divisibility notation wrongly. If you want to state that n is not divisible by 3, it should be $3 \nmid n$ (read as '3 does not divide n', or '3 is not a divisor of n').

13. May 20, 2014

### knowLittle

Thank you very much, Curious.
BTW, that cat in your pic looks happy :>