Thread: 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?

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.

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?

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

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?

Hello,

In a general case, if d|a and d|b, d|ax+by,

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

Originally Posted by Moo

Hello,

In a general case, if d|a and d|b, d|ax+by,

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?

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