Prove Co-Primes: n, n+3 | Math Proof

[knowLittle]

Homework Statement

Let $n \in \mathbb{Z} , n \not | 3$. Prove that $gcd( n , n +3 ) =1$

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$

 

[micromass]

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

 

[knowLittle]

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

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$?

 

[micromass]

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

 

[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.

 

[micromass]

$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.

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

 

[knowLittle]

Since 3 is prime d can be 1 or 3.

 

[micromass]

Since 3 is prime d can be 1 or 3.

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

 

[knowLittle]

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

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$?

 

[Curious3141]

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$?

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?

 

[knowLittle]

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?

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}$

 

[Curious3141]

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}$

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').

 

[knowLittle]

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