# Prove $(k,n+k)=1$ iff $(k,n)=1$

(a) Prove $(k,n+k)=1$ iff $(k,n)=1$.
(b) Is it true that $(k,n+k)=d$ iff $(k,n)=d$?
(all variables are integers, (a,b) means gcd(a,b))

For (a), I can only get so far.

$(k,n+k)=1\ \Rightarrow\ kq_1+(n+k)q_2=k(q_1+q_2)+nq_2=1$.

Note that we don't yet have that theorem (from a different class) that says something like if $d=(a,b)$, then $d$ is the smallest (or is it biggest) number which can be made by $ak_1+bk_2$, (which I'm not quite sure how it would help, anyway). So I'm stuck.

-
Although you say you can't use it, the condition $(n,k)=1$ is equivalent to Bezout's identity, that is, there exits integers $x$ and $y$ such that $xn+yk=1$. Therefore, you could prove this by the rearrangement, $xn+yk=x(n+k)+(y-x)k=1$. –  dls Feb 17 '12 at 3:24

Hint $\rm\$ If $\rm\ d\ |\ k\$ then $\rm\ d\ |\ k + n\ \iff\ d\ |\ n\:.\$ Therefore $\rm\ \{k,\:k+n\}\$ and $\rm\ \{k,\: n\}\$ have the same set of common divisors $\rm\:d,\:$ hence they have the same greatest common divisor.

-
This is the argument that I prefer. –  Lubin Feb 18 '12 at 1:30

I often like to use to use the theorem that $(n,k)=1$ if and only if there are integers $x,y$ such that $nx+ky=1$. But then $(n+k)x + k(y-x)=1$, so $(n+k,k)=1$.

On the other hand, if $(n+k,k)=1$, find $x,y$ so that $(n+k)x + ky = 1$, then $nx + k(x+y)=1$, so $(n,k)=1$.

More generally, if $ad-bc=1$, then $(m,n)=1$ if and only if $(am+bn,cm+dn)=1$.

This is because the matrix $$A=\left[\begin{matrix} a & b \\c & d\end{matrix}\right]$$ has inverse $$A^{-1}=\left[\begin{matrix} d & -b \\-c & a\end{matrix}\right]$$

But it's obvious that if $$\left[\begin{matrix} m'\\ n'\end{matrix}\right]=A\left[\begin{matrix} m \\ n\end{matrix}\right]$$ where $A$ is any $2\times 2$ integer matrix, then any common divisor of $m$ and $n$ is necessarily a common divisor of $m'$ and $n'$. When $ad-bc=1$, $A^{-1}$ is also an integer matrix, so we get that $$A^{-1}\left[\begin{matrix} m'\\ n'\end{matrix}\right]=\left[\begin{matrix} m \\ n\end{matrix}\right]$$ and therefore any common divisor of $m'$ and $n'$ is a common divisor of $m$ and $n$.

The problem at hand is the special case: $$A=\left[\begin{matrix} 1 & 0 \\1 & 1\end{matrix}\right]$$

Even more generally, if $x_1,...,x_n$ are integers and $A$ is an $n\times n$ integer matrix with $\det(A)=\pm 1$, and $[y_1,...,y_n]^T = A [x_1,...,x_n]^T$, then $\gcd(y_1,...,y_n)=\gcd(x_1,...,x_n)$.

A particularly lovely way of looking at this is that, if $x=(x_1,...,x_n)$ then $\gcd(x)=\gcd(x_1,..,x_n)$ is equal to the number of integer lattice points on the line segment between $0=(0,...,0)$ and $x$, excluding $0$ but including $x$ (if $x\neq 0$.)

But any integer matrix, $A$, takes lines through zero to lines through zero, and integer lattice points to integer lattice points. If $A$ is $1-1$, then the number of lattice points between $0$ and $Ax$ will thus always be at least as many as the number of lattice points between $0$ and $x$. Thus, $\gcd(Ax)\geq \gcd(x)$. If $A^{-1}$ is also an integer matrix, then $\gcd(x)=\gcd(A^{-1}Ax)\geq \gcd(Ax)$. So $\gcd(Ax)=\gcd(x)$.

This lets us generalize to $m\times n$ matrices $A$ as long as there exists an $n\times m$ matrix $B$ such that $BA=I_n$. Then $A$ is $1-1$ and $B$ is $1-1$ on the image of $A$, so the same argument applies: $\gcd(Ax)\geq \gcd(x)$ and $\gcd(x)=\gcd(BAx)\geq \gcd(Ax)$.

-

Assume $(n,k)=1$ and suppose that the positive integer $d$ divides both $n$ and $n+k$. Then $d$ divides any $\mathbb{Z}$-linear combination of $n$ and $n+k$. In particular, $d$ divides $(n+k)-n=k$. Hence $d$ divides $n$ and $k$, thus must equal 1 by assumption.

Conversely, assume that $(n,n+k)=1$ and let $d$ be a positive integer dividing $n$ and $k$. Do you see how to use the same trick to complete this direction?

-
In answer to your question: $(n,n+k)=1$. $(n,k)=d\ \Rightarrow\ d|n, d|k\ \Rightarrow \ d|(nx+ky)\ \Rightarrow\ d|(n*1+k*1)=(n+k)$. But $d|(n+k), d|n\ \Rightarrow\ d=1$. –  Jeff Feb 17 '12 at 5:11