3
$\begingroup$

(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.

  • 1
    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$.2012-02-17

3 Answers 3

7

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.

  • 0
    This is the argument that I prefer.2012-02-18
4

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)$.

3

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?

  • 1
    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$.2012-02-17