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?

Printable View

- Mar 12th 2008, 11:59 AMpizzaRusher1234greatest 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 PMThePerfectHacker
- Mar 12th 2008, 06:23 PMpizzaRusher1234
- Mar 12th 2008, 06:31 PMThePerfectHacker
- Mar 13th 2008, 08:27 AMpizzaRusher1234
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 AMMoo
Hello,

In a general case, if d|a and d|b, d|ax+by, $\displaystyle \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 AMpizzaRusher1234
- Mar 13th 2008, 11:54 PMMoo
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 ^^