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

Reimer Glasgow
Author by

Reimer Glasgow

I'm teaching myself for fun!

Updated on October 11, 2022


  • Reimer Glasgow
    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?