0
$\begingroup$

How would I go about finding $\gcd(n+2,n)$. I have managed to show that $\gcd(n+1,n)$ is $1$ which was pretty straight forward however we have only been taught the euclidean algorithm for computing gcd and it doesn't seem suitable for $n+2,n$. I have a feeling I need to make some statements before hand regarding n being even?

$\endgroup$
  • 1
    $\begingroup$ The Euclidean algorithm is perfectly suitable for these values. $\endgroup$ – Lord Shark the Unknown Oct 20 '17 at 17:20
2
$\begingroup$

$$\gcd(n+2,n)=\gcd(n+2-n, n)=\gcd(2,n)$$

Now consider cases, what if $n$ is even, what if $n$ is odd.

$\endgroup$
  • $\begingroup$ How exactly is $n+2$ comparable to $n+2-n$? $\endgroup$ – JayVB Oct 20 '17 at 17:33
  • 1
    $\begingroup$ If $n$ is odd, then $n+2$ is also odd. Therefore $\gcd(n,n+2)$ is odd (not necessarily $1$), while $\gcd(n,2)$ is always $1$. $\endgroup$ – DonielF Oct 20 '17 at 17:35
  • $\begingroup$ $\gcd(a,b)=\gcd(a-b,b)$. $\endgroup$ – Siong Thye Goh Oct 20 '17 at 17:38
  • $\begingroup$ @DonielF Actually for $n$ odd, we know the value of $\gcd(n,n+2)$ exactly. $\endgroup$ – Siong Thye Goh Oct 20 '17 at 17:44
1
$\begingroup$

Hint:

If $d$ divides $n+2$ and $n$ then it also divides $2=(n+2)-n$ so for common positive divisors there are at most two possibilities: $d=1$ or $d=2$.

$\endgroup$
1
$\begingroup$

Hint :

$$n+2=n\cdot 1+2$$

$$n=2\cdot a +0 \text{ or } 1$$

For some $a \text { in } \mathbb N$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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