# Let n be an integer greater than 3. Find a formula for gcd(n, n + 3)

Let $n$ be an integer greater than $3$. Find a formula for $\gcd(n, n + 3)$ for each of the cases :

$1)$ $n \equiv 0\mod 3$
$2)$ $n \equiv 1\mod 3$
$3)$ $n \equiv 2\mod 3$

Any help would be greatly appreciated.

-
I don't quite understand what is going on, ive calculated n such that 6+3k ≡ 0(mod 3), 7+3k ≡ 1(mod 3) and 8+3k ≡ 2(mod 3) for any k in N. – user144626 Apr 21 '14 at 9:27
There will be different cases. – Satvik Mashkaria Apr 21 '14 at 9:27
You are thinking way too hard about it. Why don't you start with some small cases and see what pattern develops? Try computing $\gcd(1,4), \gcd(2,5), \gcd(3,6), \gcd(4,7), \ldots$, etc. What do you see? How can you prove the pattern? – heropup Apr 21 '14 at 9:29
so gcd(3,n) is either 3 or 1 – user144626 Apr 21 '14 at 9:32

## 2 Answers

Apply the Euclidean algorithm. $\gcd(n, n+3) = \gcd(3, n)$. What's $\gcd(3, n)$ in each of the three cases?

-

Suppose $d|n$ and $d|(n+3)$. Then $d|3 = (n+3)-n$. Thus $d=1,3$.

So the gcd of $n$ and $n+3$ is either $1$ or $3$.

Can you see what it must be for each case?

-