Problem on gcd of two numbers

Question

Let $(a,b)$ be the Greatest Common Divisor of two numbers $a$ and $b$.

Then, if $(r,n)=1$, is it true that $(r,n-r)=1$?

If correct, prove it.

Thanks in advance :)

Can you share any thoughts you have on the problem so far? Do you think the claim is true? Why or why not? — G Tony Jacobs, Feb 17 '14 at 07:54

score 3 · Answer 1 · answered Feb 17 '14 at 07:55

3

If some divisor larger than $1$ divides $r$ and $n-r$ then it will have to divide their sum. (Think about what "divide" means to see this. $p$ divides $q$ if $q=kp$ for an integer $k$.)

answered Feb 17 '14 at 07:55

msh210

3,860

score 3 · Accepted Answer · answered Feb 17 '14 at 07:58

3

Assume that $(r,n)=1$. So there are numbers $r,s\in \mathbb Z$ such that $rx+ns=1$. we can use $rs$ and one can see that $rx+ns+rs-rs=1$. It implies that $(n-r)s+r(x+s)=1$ and we can conclude that $(n-r,r)=1$.

answered Feb 17 '14 at 07:58

Bobby

7,396

score 1 · Answer 3 · answered Feb 17 '14 at 07:57

1

If $(r,n)=1$, then there is no integer $k$ such that $n=rk$. This means that there is no integer $k$ such, that $n-r=r(k-1)$. So, $(n-r,r)=1$.

answered Feb 17 '14 at 07:57

frabala

3,732

score 0 · Answer 4 · answered Feb 17 '14 at 08:20

0

You might want to read upon Euclid's algorithm to compute GCD. Not only will this answer your question but give you a lot more...

answered Feb 17 '14 at 08:20

Gautam Shenoy

10,318

I agree on this. – frabala Feb 17 '14 at 09:54

Problem on gcd of two numbers

4 Answers4