Part A: Prove that $(k, n+k) = 1$ if and only if $(k, n)= 1$
Solution 1
$(k,k+n)=1 \Leftrightarrow \exists x,y \in \mathbb{Z}$ such that $ xk + (k+n)y = 1 \Leftrightarrow xk + yk + yn =1 \Leftrightarrow k(x+y) + yn = 1 \Leftrightarrow (n,k)=1$
Solution 2
If integer $d$ divides $k, n+k; d$ must divide $n+k-k=?$
If integer $D$ divides $k, n; d$ must divide $n+k,$ more generally $A\cdot n+B\cdot k$ where $A,B$ are arbitrary integers
Solution 3
Use this theorem:
the gcd of two numbers is 1 if and only if you can express 1 as a linear combination of the two numbers.
suppose that $(k,n)=1$. we want to show that (k, n+k)=1.
there exist integers $i,j$ such that $ki+nj=1$. then $k(i-j)+(n+k)j=1$, so (k, n+k)=1.
I'll let you do the converse. It is even easier than the first part.
Related videos on Youtube
Comments
-
Reimer Glasgow about 1 year
Part A is in the title, Part B is here: Is it true that $(k, n+k)= d$ if and only if $(k, n)=d$?
I am still working on the Part A.
What I have so far:
if $(k, n)= 1$ then $1|k$, $1|n$ and $1|(n-k)$
if $(k, n+k)=1$ then $1|k$, $1|n+k$ and $1|((n+k)- k) \to 1|n$
I was under the impression that if $d|a$ and $d|b$, that $d|(b-a)$.
Is this false? What more should I be doing to tackle part A?
-
CIJ over 8 yearsIn general [$\gcd(a,b)=\gcd(a,at+b)$][1] so your problem is just a special case. [1]: math.stackexchange.com/questions/23316/prove-gcda-b-gcda-b-at
-
pancini over 8 yearstheres never any point in writing $1|n$ since 1 divides every integer.
-