Part A: Prove that $(k, n+k) = 1$ if and only if $(k, n)= 1$

1,688

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.

Share:
1,688

Related videos on Youtube

Reimer Glasgow
Author by

Reimer Glasgow

I'm teaching myself for fun!

Updated on October 11, 2022

Comments

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