Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

This isn't really a GCD question, because GCD is only defined for integers. I'm interested in the the existence of a common divisor of any two non-zero real numbers. In other words can you prove or disprove the following:

Given $x,y \neq 0\in \mathbb{R}, \exists \space g \space s.t. \space x/g \in \mathbb{Z}$ and $y/g \in \mathbb{Z}$.

(I hope my math is understandable, haven't done this in awhile). It's clearly possible for many numbers, including irrational ones (e.g. for multiples of $\pi$, $g = \pi$). Is it possible for all real numbers?

share|improve this question
2  
If $x/g=m$, and $y/g=n$, then $x/y=m/n$. –  Chris Eagle Mar 20 '12 at 0:17
    
For this to exist for all reals, it would require that the ratio of two rational numbers can be expressed as the ratio of two integers, which is a rational number. –  Peter Grill Mar 20 '12 at 0:21
    
Yeah, what @ChrisEagle said. –  Peter Grill Mar 20 '12 at 0:22
    
@PeterGrill In your first comment, I think you mean "the ratio of two real numbers". –  Alex Becker Mar 20 '12 at 0:24
    
@AlexBecker: I actually meant to say "ratio of two irrational numbers" as that was the example I was thinking about, but real is even better as your answer has shown. –  Peter Grill Mar 20 '12 at 0:28

2 Answers 2

up vote 6 down vote accepted

The following conditions are equivalent for nonzero reals $x,y$

  1. There is a real $g$ such that $x/g$ and $y/g$ are integers
  2. The quotient $x/y$ is rational

Proof:

$1 \implies 2$: Since quotient of integers is rational, your condition implies that

$(x/g) / (y/g) \in \mathbb{Q}$

after clearing $g$ in denominators

$x/y \in \mathbb{Q}$.

$2 \implies 1$:

If $x/y$ is rational: $x/y=p/q$ then define $g = y/q$ (or $g = x/p$), then $x/g = xq/y = p$ and $y/g = q$ are integers. QED

So any pair of reals with irrational quotient is a counterexample, for example $x=1$ and $y=\sqrt{2}$.

Real numbers $x,y$ with rational quotient are known as commensurable. This is how irrationality was formulated in the ancient times. It has been said that diagonal of a square is not commensurable with its side.

The Euclidean algorithm for finding GCD was originally formulated on segments (reals) - it found a common measure ($g$) given segments of length $x$ and $y$.

share|improve this answer
    
Great answer, just a small addition: There is an "algorithm" for finding the GCD of two commensurate real numbers, $gcd(a,b) = a ~ f(b / a)$, where $f$ is Thomae's function. –  A. Donda Aug 4 at 15:51

The statement is not true. Consider $x=1,y=\pi$. If $y/g=n\in\mathbb Z$, then $g=\pi/n$ so $x/g=n/\pi\notin \mathbb Z$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.