Using Two Irrationals to Generate All Positive Integers

Date: 10/03/2003 at 00:59:55
From: Sarah
Subject: two irrational numbers a, b generating all positive integers

If a and b are positive irrational numbers such that 1/a + 1/b = 1, 
then every positive integer can be uniquely expressed as either floor
(ka) or floor(kb), where k is a positive integer. 


I don't know how to approach this kind of problem. It's asking me to 
show that somehow a and b can generate every possible positive 
integer.  How do I do that? 

Date: 10/03/2003 at 05:21:26
From: Doctor Jacques
Subject: Re: two irrational numbers a, b generating positive integers

Hi Sarah,

This is a very interesting question indeed.

We may first record some useful facts:

* As neither a or b is 1/2, if, for example, a < b, we have:
    1 < a < 2
    2 < b

* As neither a or b is rational, no number of the form ka, kb, k/a,
  k/b, (for integer k), is an integer.

We show first that every integer N >= 1 can be expressed at least in 
one way as floor(ka) or floor(mb).

Assume that this is not the case. This means that there are integers 
k, m, and N such that

  1)  ka < N
  2)  N+1 < (k+1)a
  3)  mb < N
  4)  N+1 < (m+1)b

where all the inequalities are strict because a and b are irrational, 
as noted above.

With a little algebra, we can deduce from this:

  1)  (k/N) < (1/a) < (k+1)/(N+1)

  2)  (m/N) < (1/b) < (m+1)/(N+1)

and, adding these together:

 (k+m)/N < (1/a) + (1/b) = 1
 
                       1 = (1/a) + (1/b) < (k+m+2)/(N+1)

which leads to:

  k+m < N < k + m + 1

This says that there is an integer N strictly between consecutive 
integers (k+m) and (k+m+1), an obvious contradiction.

Let us now consider the unicity question. As a and b are > 1, there 
is at most one integer k and one integer m such that N = floor(ka) or 
N = floor(mb). We must show that it is not possible to have both, 
i.e. that we cannot have:

  N = floor(ka) = floor(mb)

We use a similar technique: assume, by contradiction, that the above 
equality holds for some k, m, N. We have:

  1)  N < ka < N+1
  2)  N < mb < N+1

Can you transform the above relations to get a contradiction similar 
to the previous one (an integer strictly between two consecutive 
integers)?

Please feel free to write back if you require further assistance.

- Doctor Jacques, The Math Forum
  http://mathforum.org/dr.math/