What is $\gcd(n-1,n+10)$, for $n$ a natural number?

Question

Currently I have,

let $d=\gcd(n-1,n+10)$

then, $d\mid n-1$ and $d\mid n+10$

and hence $d$ must also divide $11$

not really sure what to do now, any help would be greatly appreciated.

Answer 1

Let $d=gcd(n-1,n+10)$. Then $$d=gcd(n-1,n+10)=gcd(n-1;n+10-(n-1))=gcd(n-1;11)$$ $d=1$ or $d=11$

Answer 2

As you have already observed, $d$ must divide $11$, thus $d$ is either $1$ or $11$.

However, one thing to note that is both are possible-for example, for $n=2$, $d=1$, and for $n=12$, $d=11$.

A similar idea would be using the Euclidean Algorithim, which yields that $$\gcd(n-1,n+10)=\gcd(n-1,n+10-n+1)=\gcd(n-1,11)$$ which is $1$ or $11$.

EDIT

An important observation would be noting when it is $1$, and when it is $11$.

This matter can be resolved using our upper equation, which says that $\gcd(n-1,n+10)=\gcd(n-1,11)=11$. This implies that $11|n-1$, further showing that $\gcd(n-1,11)=11 \Rightarrow 11|n-1 \Rightarrow n \equiv 1 \pmod {11}$.

Thus, $\gcd(n-1,11)=11$ implies that $n \equiv 1 \pmod {11}$. Further note that the converse is true-if $n \equiv 1 \pmod {11}$, then $n=11k+1$.

This gives us $$\gcd(n-1,11)=\gcd(11k,11)=11$$ Thus we have $$\gcd(n-1,n+10)=11 \Leftrightarrow n \equiv 1 \pmod {11}$$

Since $\gcd(n-1,n+10)$ is either $1$ or $11$, this gives us that $$\gcd(n-1,n+10)=1 \Leftrightarrow n \not \equiv 1 \pmod {11}$$

This can be demonstrated in my upper example-if $n=2$, then $n \not \equiv 1 \pmod {11}$ thus implying that $\gcd(n-1,n+10)=1$.

If $n=12$, then $n \equiv 1 \pmod {11}$, thus implying $\gcd(n-1,n+10)=11$.

Answer 3

Your argument is correct. Let us finalize it by investigating which are the numbers $n$ for which $d=1$ and which are those for which $d=11$.

If $n = 11k + 1$, then $\gcd (n-1, n+10) = \gcd (11k, 11k + 11) = 11 \gcd (k, k+1) = 11$ (check for yourself that the $\gcd$ of two consecutive numbers is $1$), so in this case $d=11$.

Assume, now, that $n = 11k + l$ with $l \in \{0, 2, 3, 4, \dots, 10\}$ (we have already studied the case $l=1$). If $d=11$, then $d \mid n-1$ means $11 \mid 11k + l -1$, and since $11 \mid 11k$ this implies that $11 \mid l-1$ - which is not possible for any of the $l$ from the set above. This means that for $n$ of the form above, $d=1$.