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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994-2013 The Math Forum