Help with a lemma about rationals and coprime integers

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

skullturf
Posts: 556
Joined: Thu Dec 07, 2006 8:37 pm UTC
Location: Chicago
Contact:

Help with a lemma about rationals and coprime integers

Postby skullturf » Thu Jul 09, 2015 2:24 am UTC

For something I'm working on, I would like the following lemma to be true.

I'm reasonably certain that it is true, but it's one of those things where at first glance, you think "That's intuitive", but when you try to write down a proof, you realize that there are messy details to wade through.

Am I missing a clever approach by which you can prove it instantaneously? Or does it require a bit of wading through details?

The desired lemma:

(w,x,y,z) is a fixed 4-tuple of rational numbers. We consider all rational multiples of this 4-tuple, defined in the obvious way:

t(w,x,y,z) = (tw,tx,ty,tz) for any rational number t.

Some rational multiples of this rational 4-tuple will consist entirely of integers. Others will not.

My claim is that at most one rational multiple of the 4-tuple will consist of integers with no common divisor.

Example:
Spoiler:
Suppose my original 4-tuple is

X = (2/1, 4/3, 6/5, 8/7)

One rational multiple of X, not consisting entirely of integers, is

(1/2)*X = (1, 2/3, 3/5, 4/7)

Another rational multiple of X, not consisting entirely of integers, is

(15/2)*X = (15, 10, 9, 60/7)

Yet another rational multiple of X, this time consisting only of integers, is

(105/2)*X = (105, 70, 63, 60) = (3*5*7, 2*5*7, 3*3*7, 2*2*3*5), which consists of four integers with no common divisor

If k>1 is an integer, then (105k/2)*X will also consist only of integers, but those integers will have a common divisor.


Maybe you can sort of see why I thought this might be "intuitive". However, writing a proof might be messy, and it feels like there should be an easier way.

Rough idea behind proof:

Write X = (a1/b1, a2/b2, a3/b3, a4/b4) where each of those fractions is in lowest terms

Let G = gcd(a1,a2,a3,a4) and let L = lcm(b1,b2,b3,b4)

Show that multiplying X by L/G would give you all integers

Show, very roughly speaking, that multiplying by "anything else" would either give you non-integers, or integers all having a common factor.

It seems like that would probably work, but it also seems like writing it all out would be a pain.

Am I missing a clever shortcut?

EDITED TO ADD:

Maybe the more "elegant" trick is to do something like this:

If X = (a1/b1, a2/b2, a3/b3, a4/b4), then certainly there exist some rational numbers t with the property that t*X consists only of integers (because for example we can choose t = b1b2b3b4).

Then maybe choose the infimum of all rational t such that t*X consists only of integers?

Cauchy
Posts: 602
Joined: Wed Mar 28, 2007 1:43 pm UTC

Re: Help with a lemma about rationals and coprime integers

Postby Cauchy » Thu Jul 09, 2015 5:20 am UTC

Well, you can multiply your one example by -1 to get a second example, but that'll be it. I'll show that there's only among the positive rational multiples, by showing that two such rational multiples are necessary equal.

Let (a,b,c,d) and (e,f,g,h) be two rational multiples of (w,x,y,z) that have all integer entries, and the entries have greatest common divisor 1. Then, (a,b,c,d) = t_1(w,x,y,z) and (e,f,g,h) = t_2(w,x,y,z) (with t_1, t_2 > 0), so (e,f,g,h) = t_2/t_1(a,b,c,d). t_1 is not 0, since (0,0,0,0) does not have gcd 1, so t_2/t_1 is a rational number, say p/q in lowest terms (with p, q > 0). Then, (e,f,g,h) = (ap/q, bp/q, cp/q, dp/q). Since ap/q, bp/q, cp/q, and dp/q are integers, it follows that q divides each of ap, bp, cp, and dp. Since p and q are relatively prime, it follows that q divides each of a, b, c, and d. Thus, q is a common divisor of a, b, c, and d, and hence q is 1. Now, (e,f,g,h) = (ap/q, bp/q, cp/q, dp/q) = (ap, bp, cp, dp), so p is a common divisor of e, f, g, and h, and hence p is also 1. So p/q = 1/1 = 1, and hence (a,b,c,d) = (e,f,g,h). Thus, all the relatively prime rational multiples are the same, and hence there can be at most one.
(∫|p|2)(∫|q|2) ≥ (∫|pq|)2
Thanks, skeptical scientist, for knowing symbols and giving them to me.

User avatar
Xanthir
My HERO!!!
Posts: 5426
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Help with a lemma about rationals and coprime integers

Postby Xanthir » Thu Jul 09, 2015 11:20 pm UTC

Multiplying by -1 doesn't actually produce another example, because they're not coprime - they all share the divisor -1! Of course, maybe you exclude the negative unit from the definition as well.

This might be a more intuitive result:

Let (a,b,c,d) be a tuple with all values co-prime integers.

By definition, no integer multiplier k (other than 1) can produce another co-prime tuple, as all the members of such a tuple would share the factor k.

On the other hand, no non-integer rational k can produce a tuple with all-integer values. As the k is not an integer, it can be written in reduced form, where its denominator is an integer > 1. As all the original tuple values are coprime, by definition there is no integer > 1 that evenly divides all of them, so the resulting tuple necessarily contains at most one integer.

This exhausts the set of possible multipliers, so there is no way to produce another such tuple by this method.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

Cauchy
Posts: 602
Joined: Wed Mar 28, 2007 1:43 pm UTC

Re: Help with a lemma about rationals and coprime integers

Postby Cauchy » Sun Jul 12, 2015 8:19 pm UTC

Xanthir wrote:Multiplying by -1 doesn't actually produce another example, because they're not coprime - they all share the divisor -1! Of course, maybe you exclude the negative unit from the definition as well.


Typically, one excludes all units. The positive examples also have the divisor -1, since 5 = (-5)(-1), for instance.

This might be a more intuitive result:

Let (a,b,c,d) be a tuple with all values co-prime integers.

By definition, no integer multiplier k (other than 1) can produce another co-prime tuple, as all the members of such a tuple would share the factor k.

On the other hand, no non-integer rational k can produce a tuple with all-integer values. As the k is not an integer, it can be written in reduced form, where its denominator is an integer > 1. As all the original tuple values are coprime, by definition there is no integer > 1 that evenly divides all of them, so the resulting tuple necessarily contains at most one integer.

This exhausts the set of possible multipliers, so there is no way to produce another such tuple by this method.


That's... exactly what I wrote.
(∫|p|2)(∫|q|2) ≥ (∫|pq|)2
Thanks, skeptical scientist, for knowing symbols and giving them to me.

User avatar
Xanthir
My HERO!!!
Posts: 5426
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Help with a lemma about rationals and coprime integers

Postby Xanthir » Sun Jul 12, 2015 8:22 pm UTC

Cauchy wrote:That's... exactly what I wrote.


I honestly could not tell.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 12 guests