(m,n)=(m+kn,n)

Printable View

- May 22nd 2008, 06:56 AMszpengchaoprove this Highest Common Factor property
(m,n)=(m+kn,n)

- May 22nd 2008, 09:53 AMMoo
Hello,

Let d=gcd(m,n) and d'=gcd(m+kn,n)

**1st part**

d divides m.

It also divides n.

So it divides every linear combination of the two, and in particular m+kn.

Therefore, d divides both m+kn and n.

We can conclude that d divides d' (because d' is thecommon factor)**highest**

**2nd part**

d' divides n.

d' also divides m+kn.

So it divides every linear combination of the two, and in particular m+kn+(-k)n=m.

Therefore, d' divides both m and n.

We can conclude that d' divides d.

----> d=d' - May 22nd 2008, 09:55 AMszpengchaocan u prove this
p is an odd prime

prove:

1^k+2^k+3^k+....(p-1)^k = 0 mod p if p-1 doesnt divid k - May 22nd 2008, 02:27 PMThePerfectHacker