250 5 Number Theory
- Prove that for no integern>1 doesndivide 2n−1.
712.Find all pairs of positive integers(a, b)with the property thatab+a+bdivides
a^2 +b^2 +1.
713.Letx, y, zbe positive integers such thatxy−z^2 = 1. Prove that there exist
nonnegative integersa, b, c, dsuch that
x=a^2 +b^2 ,y=c^2 +d^2 ,z=ac+bd.5.1.3 The Greatest Integer Function..............................
The greatest integer function associates to a numberxthe greatest integer less than or
equal tox. The standard notation isx. For example, 2 =2, 3. 2 =3,− 2. 1 =−3.
This being said, let us start with the problems.
Beatty’s theorem.Letαandβbe two positive irrational numbers satisfyingα^1 +^1 β= 1.
Then the sequencesαnandβn,n ≥ 1 , are strictly increasing and determine a
partition of the set of positive integers into two disjoint sets.
Proof.In other words, each positive integer shows up in exactly one of the two sequences.
Let us first prove the following result.
Lemma.Ifxn,n≥ 1 , is an increasing sequence of positive integers with the property
that for everyn, the number of indicesmsuch thatxm<nis equal ton− 1 , thenxn=n
for alln.
Proof.We do the proof by induction. The base case is obvious: because the sequence is
increasing, the onlynfor whichxn<2isn=1. Now let us assume thatx 1 = 1 ,x 2 =
2 ,...,xn− 1 =n−1. From the hypothesis it also follows that there are no other indices
mfor whichxm<n. And because there is exactly one more term of the sequence that is
less thann+1, this term must bexnand it is equal ton.
Returning to the problem, let us write all numbers of the formαnandβnin an
increasing sequenceyn. For everynthere are exactlynαnumbers of the formkα,
andnβnumbers of the formkβthat are strictly less thann(here we used the fact that
αandβare irrational). We have
n− 1 =⌊
n
α+
n
β⌋
− 1 ≤
⌊
n
α⌋
+
⌊
n
β⌋
<
n
α+
n
β=n.Hencenα+nβ=n−1, which shows that the sequenceynsatisfies the condition of
the lemma. It follows that this sequence consists of all positive integers written in strictly
increasing order. Hence the conclusion.