Rel. Prime algebra/elementary number theory

Question

Hello I have two questions 1) show that $5n+2$ and $12n+5$ are relatively prime. Can I do it this way?

From Euclids algortihm.

$12n+5=(5n+2) \cdot 2 +(2n+1)$

$5n+2=(2n+1) \cdot 2 +n$

$2n+1=(n) \cdot 2 +1$

$n=1 \cdot n + 0$

Hence gcd=1

My second question is let a,b,c $\in$ Z suppose $c|a+b$ and $(a,b)=1$ show that c is relatively prime to both a and b. Now sure how to start I know that I can write $au+bv=1$ and $a+b=ct$ but i dont know if that is useful

nonuser · Answer 1 · 2018-01-07T20:32:32.677

1

For 1. it is OK what you do.

For the second part. Suppose $c$ and $a$ are not relatively prime. Then there exist prime $p$ such that $p|a$ and $p|c$, so $a= dp$ and $p|dp+b$ so:

$$p|(dp+b)-dp =b$$

$p|b$ and this is a contradiction.

edited Jan 07 '18 at 20:32

answered Jan 07 '18 at 20:08

nonuser

90,026

score 0 · Answer 2 · answered Jan 07 '18 at 20:11

0

Note that$$5(12n+5)-12(5n+2)=1$$ Then according to Bezout lemma they are coprime.

answered Jan 07 '18 at 20:11

Mostafa Ayaz

31,924

Bezout says the converse: if $(12n+5)$ and $(5n+2)$ are coprime then there are $r,s$ with $r(12n+5)+s(5n+2)=1$. But of course, this question explains that $ra+sb=1$ also implies that $gcd(a,b)=1$. – Dietrich Burde Jan 07 '18 at 20:22
Thank you, but unfortunately we didn't learn about bezout's lemma yet – Jan 07 '18 at 20:29
@Djhoe You don't need Bezout's Lemma. From $ra+sb=1$ it follows directly that $gcd(a,b)=1$,see the duplicate above. – Dietrich Burde Jan 07 '18 at 20:43
Yes you're right! – Mostafa Ayaz Jan 07 '18 at 21:10

Rel. Prime algebra/elementary number theory

2 Answers2