Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
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$. –  dls Feb 17 '12 at 3:24

3 Answers 3

up vote 7 down vote accepted

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.

share|improve this answer
    
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)$.

share|improve this answer

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?

share|improve this answer
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$. –  Jeff Feb 17 '12 at 5:11

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.