Math Is Fun Forum

  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

#1 2009-05-26 06:26:04

LuisRodg
Real Member
Registered: 2007-10-23
Posts: 322

gcd proof

How do you prove this? Any ideas?

Offline

#2 2009-05-26 06:35:23

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.

Offline

#3 2009-05-26 07:40:23

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
.

Offline

Board footer

Powered by FluxBB