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.
 A: 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.
A: 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)$.
A: 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?
