# GCD divisibility problem

• May 3rd 2009, 09:37 PM
glowplug19
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.
• May 4th 2009, 01:14 AM
TheAbstractionist
Quote:

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