Associated Topics || Dr. Math Home || Search Dr. Math

### 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)

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

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

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/
```
Associated Topics:
College Number Theory

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search