Math Is Fun Forum

LuisRodg

Real Member

Registered: 2007-10-23

Posts: 322

gcd proof

How do you prove this? Any ideas?

mathsyperson

Moderator

Registered: 2005-06-22

Posts: 4,900

Re: gcd proof

This follows from the fact that

I've got a proof of that lying around somewhere, if you need it.

---

Why did the vector cross the road?
It wanted to be normal.

JaneFairfax

Member

Registered: 2007-02-23

Posts: 6,868

Re: gcd proof

The result is obvious if either

or

is equal to 1, so let us assume that

.

Let

be a common divisor of

and

  and consider the multiplicative group

modulo

. Since

and

,

divides

and

. where

is the order of 2 in the group. Hence

divides

and so

.

Conversely, if

, then

divides

and so

divides

and

(since

divides both

and

) and so

and

.

I have shown that every common prime divisor of

and

divides

and every prime divisor of

divides both

and

. I thus conclude that

.