1. ## 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?

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

3. 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?

4. 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).

5. 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?

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

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

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?

8. 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 ^^