# greatest common factors

• Mar 12th 2008, 11:59 AM
pizzaRusher1234
greatest common factors
I'm stuck on this:

For all positive integers n and all integers a, gcf(a, a+n) | n.
(For all positive integers n and all integers a, the greatest common fact of 'a' and 'a+n' divides into 'n').

Anybody know where to start?
• Mar 12th 2008, 04:27 PM
ThePerfectHacker
Quote:

Originally Posted by pizzaRusher1234
I'm stuck on this:

For all positive integers n and all integers a, gcf(a, a+n) | n.
(For all positive integers n and all integers a, the greatest common fact of 'a' and 'a+n' divides into 'n').

Anybody know where to start?

For positive integers this statement is always true. Let d=gcd(a,a+n) then d|a and d|(a+n) so d|n. Thus, gcd(a,a+n) |n.
• Mar 12th 2008, 06:23 PM
pizzaRusher1234
Quote:

Originally Posted by ThePerfectHacker
For positive integers this statement is always true. Let d=gcd(a,a+n) then d|a and d|(a+n) so d|n. Thus, gcd(a,a+n) |n.

how do you know that d divides a+n? Is there a proof?
• Mar 12th 2008, 06:31 PM
ThePerfectHacker
Quote:

Originally Posted by pizzaRusher1234
how do you know that d divides a+n? Is there a proof?

If d=gcd(a,a+n) then by definition d|a and d|(a+n).
• Mar 13th 2008, 08:27 AM
pizzaRusher1234
sorry.

you said "[since] d|a and d|(a+n) [then] d|n"

I meant how do you know that d|n? Is there a proof for that?
• Mar 13th 2008, 08:29 AM
Moo
Hello,

In a general case, if d|a and d|b, d|ax+by, $\forall x,y \in \mathbb{Z}^2$

So if d|a and d|(a+n), d|a+n-a=n

(Wink)
• Mar 13th 2008, 09:25 AM
pizzaRusher1234
Quote:

Originally Posted by Moo
Hello,

In a general case, if d|a and d|b, d|ax+by, $\forall x,y \in \mathbb{Z}^2$

So if d|a and d|(a+n), d|a+n-a=n

(Wink)

is this sort of like this

for integers a,b,c: c = ax + by if, and only if, gcf(a, b)|c.

How would a proof of that go?
• Mar 13th 2008, 11:54 PM
Moo
The "if and only if" is correct, but it's not a real definition ;-)

You can say "if c=ax+by, SO gcf(a,b) divides c"

Let's write it :-)

If d=gcf(a,b), then a=da' and b=db' (with a' and b' coprime, but it doesn't matter for the demonstration)

So c=da'x+b'dy=d(a'x+b'y)

So d divides c, it's as simple as this ^^