# Thread: GCD divisibility problem

1. ## GCD divisibility problem

Back again haha. Thanks for all the great help.

I have to prove that, for a positive integer n and any integer a, gcd(a, a+n) divides n; hence gcd(a, a+1)=1.

Not even sure where to begin.

2. Originally Posted by glowplug19
Back again haha. Thanks for all the great help.

I have to prove that, for a positive integer n and any integer a, gcd(a, a+n) divides n; hence gcd(a, a+1)=1.

Not even sure where to begin.
Hi glowplug19.

$\gcd(a,a+n)$ divides both $a$ and $a+n;$ hence it divides $(a+n)-a=n.$