Here's the problem

Suppose that $$ a, b \in \mathbb {R^+},\qquad 0 < a + b < 1 $$ Prove or disprove that $$ \exists n \in \mathbb{Z^+}: \left\{na\right\} + \left\{nb\right\} \ge 1$$ where $\{x\} = x - \lfloor x \rfloor$ and $\lfloor x \rfloor = \max\left\{ n | n \in \mathbb{Z}, n \le x \right\}$.


  1. The original problem in magazine ( ISSN 1005-6416 ) might be (For a long time, I can't remember clearly):

    $a, b$ are irrationals, subjects to $\forall n \in \mathbb{Z^+}: \left\{ na \right\} + \left\{ nb \right\} \le 1$, prove that $a + b \in \mathbb{Z}$.

    Because I've found that $a, b$ needn't have been irrationals, I insist that there be a general proof (I think it's algebrian). I think the steps are like this:

    • Divides $\left\{ (x, y) | x, y \in \mathbb{R^+}, x + y < 1 \right\}$ into many (infinity) pieces.
    • For each piece, we obtain a $n$.
  2. It may be easy when $a, b \in \mathbb{Q}$. Here's the proof:

    Let $f(n) = \left\{na\right\} + \left\{nb\right\}$. For each $x \not \in \mathbb{Z}$, we have $\left\{x\right\} + \left\{-x\right\} = 1$

    So if $a, b \in \mathbb{Q}$, we have $f(1) + f(-1) = 2$

    Note that: $\exists T \in \mathbb{Z^+}$ subjects to $\forall n \in \mathbb{Z}: f(n + T) = f(n)$

    So $2 = f(1) + f(-1) = f(1) + f(2T-1) \le 2 \max\left(f(1), f(2T-1)\right)$

    We've done.

  3. I'd like a proof with algebraic construction.


  • 1
    $\begingroup$ This is certainly true for rationals when $a = b = \frac{k}{m}$ (suppose $\frac{k}{m}$ is in lowest terms) since this forces $\frac{k}{m} < \frac{1}{2}$. Thus, the fractional part $\{n \cdot \frac{k}{m}\} \in \left\{0, \frac{1}{m}, \frac{2}{m}, \dots , \frac{m-1}{m} \right\}$. Note that the condition $a + b < 1$ implies that $m > 2$ and hence $\frac{m-1}{m} > \frac{1}{2}$. $\endgroup$
    – JavaMan
    Jan 30, 2012 at 8:42
  • 2
    $\begingroup$ The fractional parts of multiples of irrationals are dense and equidistributed in $[0,1]$ ( mathworld.wolfram.com/FractionalPart.html ). This might be helpful for the irrational case. $\endgroup$
    – Listing
    Jan 30, 2012 at 9:09
  • $\begingroup$ @Listing I know that there's a proof by the theorems of multiples of irrationals (although I don't know how). But I'd prefer a algebra proof without discussing whether $a, b$ are rationals or not. That's what I meant. $\endgroup$
    – Yai0Phah
    Jan 30, 2012 at 9:29
  • 3
    $\begingroup$ @JavaMan Thanks. 1. It's from a mock test of math competition from a magazine made up of mock tests, so I think the context might be useless. 2. I'm not a native speaker. As you see in the post, I try to replace the English words with the mathematical symbols. $\endgroup$
    – Yai0Phah
    Jan 30, 2012 at 14:31
  • 2
    $\begingroup$ The "easy" case is that when the set $\{a,b,1\}$ is linearly independent over $\mathbf{Q}$, then the set of points $$\{(\{na\},\{nb\})\mid n\in\mathbf{N}\}$$ is dense on the square $[0,1]\times[0,1]$ meaning that the sum attains values arbitrarily close to two. This the 2-dimensional version of Kronecker's density theorem (see e.g. Joe Roberts': "Elementary Number Theory - a problem oriented approach", or Tom Apostol's "Modular Functions and Dirichlet Series in Number Theory") $\endgroup$ Feb 1, 2012 at 8:58

3 Answers 3


Look at the following figure of the checkered $(x,y)$-plane with gridlines at integer $x$'s and $y$'s:


The points $z_n:=(n\ a,n\ b)$ $\ (n\in{\mathbb Z})$ are marked. We will show that at least one $z_n$ with $n>0$ falls in the interior of a grey triangle, which means $\{n a\}+\{n b\}>1$.

We distinguish the following two cases:

(i) $b/a$ is rational. $-$ In this case there are $p$, $q\in{\rm N}_{\geq1}$ with ${\rm gcd}(p,q)=1$ and a $\lambda>0$ with $a=p\lambda$, $b=q\lambda$. All points $z_n$ are lying on the line $$\ell:\quad t\mapsto z(t)=(pt, qt)\qquad(-\infty<t<\infty)\ ;$$ in fact $z_n=z(n\lambda)$. This line passes through the points $(j p, j q)$ $\ (j\in{\mathbb Z})$ and actually is a closed curve $\gamma$ on the torus $T$ obtained by identifying points $(x,y)$ and $(x',y')$ with $x\equiv x'$ $\ ({\rm mod}\ p)$ and $y\equiv y'$ $\ ({\rm mod}\ q)$. Let $\pi: \ {\mathbb R}^2\to T$ denote the corresponding projection. There is a finite set of segments $\sigma_k\subset\gamma=\pi(\ell)$ colored in grey, which makes up for half of the length of $\gamma$.

(i.i) If $\lambda$ is rational then the $z_n$ project onto only finitely many equally spaced points on $\gamma$, and some $z_n$ with $n>0$ will project onto the same point as $z_{-1}$ and therefore will lie in the interior of a grey triangle. (This case has already been dealt with by the OP.)

(i.ii) If $\lambda$ is irrational then the points $\pi(z_n)$ are dense on $\gamma$, and some of them will lie in the interior of one of the grey intervals of $\gamma$. It follows that the corresponding $z_n$ are lying in a grey triangle.

(ii) $b/a=:m$ is irrational. $-$ Put $\delta:=1-a-b$ and consider again the line $$\ell: \quad t \mapsto z(t):=(t, m t)\qquad(-\infty<t<\infty)$$ (now with a different parametrization). The $z_n$ are equally spaced on $\ell$ with distance $d:=\sqrt{a^2+b^2}$. The line $\ell$ intersects the vertical gridlines $x=k\in{\mathbb Z}$ in the points $(k, m k)$ whose ordinates $y_k:=m k$ are irrational for $k\ne0$. Therefore the $y_k$ are dense ${\rm mod}\ 1$. There is a $k_0>0$ such that $1-\{y_{k_0}\}<\delta$. It is easy to see that the segment $\sigma\subset\ell$ with endpoints $(k_0-a, y_{k_0}-b)$ and $(k_0, y_{k_0})$ is lying completely in the grey triangle to the left of $(k_0, y_{k_0})$. Since $\sigma$ has length $d$ there is at least one $z_n\in\sigma$, and this $z_n$ lies in the interior of a grey triangle.

  • $\begingroup$ In summary, you proved: 1. if $a, b \not \in Q$, $\displaystyle{\frac{a}{b}} \in \mathbb{Q}$, the points on line (in torus) will be density so some point will be in gray triangle. 2. if $\displaystyle{\frac{a}{b}} \not \in \mathbb{Q}$, there will be a "gray segment" which length is larger than $\displaystyle{\sqrt{a^2 + b^2}}$ (exactly could be $\displaystyle{\frac{\sqrt{a^2 + b^2}}{a + b} - \varepsilon}$ foreach $\varepsilon > 0$. Am I right? $\endgroup$
    – Yai0Phah
    Feb 2, 2012 at 4:24
  • $\begingroup$ You might as well need to improve your symbol such as $\bmod n$ and $\pmod n$ with LaTeX command bmod and pmod. $\endgroup$
    – Yai0Phah
    Feb 2, 2012 at 4:39
  • $\begingroup$ The algebraic constructor proof might not exist. $\endgroup$
    – Yai0Phah
    Feb 2, 2012 at 4:45
  • $\begingroup$ @Frank Science: Concerning your first comment: Yes. $\endgroup$ Feb 2, 2012 at 9:11

Case 1: $a,b$ rationals.

This case is simple. $a=\frac{m}{n}$ and $b=\frac{r}{p}$ with both fractions irreducible.

WLOG $n \geq p$.

Subcase 1.1 *$n < p$*

Solve $rx \cong -1 \mod p$, which has the solution $x= x_0 +lp$.

Then for all $x$ we have $\{ xb \}=\frac{p-1}{p}$, and because $1 < n < p$ you can easely find such $x$ so that $xa \notin Z$, meaning $\{ xa \} >\frac{1}{n}$.

Since $\frac{p-1}{p}+\frac{1}{n} > \frac{p-1}{p}+\frac{1}{p} =1$ we are done.

Subcase 1.2 *$n = p$*

Same idea.

Solve $rx \cong -1 \mod p$, which has the solution $x= x_0 +lp$.

The only possible issues are if $xm= 0, 1 \mod p$.

But this is not possible.

The first case is not possible since both $x,m$ are invertible, while in the second case you get

$$rx \cong -1 \mod p \Rightarrow r \cong -x^{-1} \mod p$$ $$mx \cong 1 \mod p \Rightarrow m \cong x^{-1} \mod p $$

Thus, $r+m \cong 0 \mod p$ and hence $a+b= \frac{m+r}{p} \in Z$ which is a contradiction.

Case 2 A rational, b irrational. This case follows immediately from Dirichclet theorem.

Indeed, $a=\frac{m}{n}$ irreducible.

The equation $xm \cong -1 \mod p$ has solution $x= x_o+np$, and by Dirichlet theorem, since $b$ is irrational, the set $\{ (x_0+np)b\} $ is dense in $[0,1]$.

Pick some $k$ so that $\{ (x_0+kp)b\} > \frac{1}{n}$ and you are done, $(x_0+kp)$ satisfies your condition.

Case 3: $a,b$ irational. Then $b= \alpha a$.

Subcase 3.1 $\alpha$ irrational. See Jyrki's comment.

Subcase 3.2 $\alpha$ rational. $\alpha=\frac{m}{n}$ irreducible.

Fix some $\epsilon$ so that $(m+n)\epsilon <1$. Then we also have $m-1 < m(1-\epsilon) < m$.

By Dirichlet theorem, the set $\{nka\} $ is dense in $[0,1]$.

Pick some $k$ so that

$$\{ kna \} > 1- \epsilon \,.$$


$$kna = l+ 1- \epsilon$$

for some integer $l$.



Note that by our choise of $\epsilon$,

$$\frac{ml+m-1}{n} < \frac{m(l+1-\epsilon)}{n} < \frac{ml+m}{n} \,.$$

This shows that $[\frac{m(l+1-\epsilon)}{n}] \leq \frac{ml+m-1}{n}$ and hence

$$\{\frac{m(l+1-\epsilon)}{n} \} > \frac{1-m\epsilon}{n}$$


$$\{ kna \} + \{ knb \} >1- \epsilon+ \frac{1-m\epsilon}{n} \geq 1$$

the last inequality following from $(m+n)\epsilon<1$.

P.S. The proof is extremely technical, there might be a mistake into it. I wrote but I would definitely not enjoy reading it :P

  • $\begingroup$ Why -1? The voter might as well point out the mistake. Thanks. $\endgroup$
    – Yai0Phah
    Feb 2, 2012 at 3:28

The case for rationals was mentioned in Javaman's comment above. Here is one for the irrationals. I'm arguing here a bit informal, I think from this a precise answer can be derived.

Assume a and b in their base-2-expansions at some position behind the decimal separator:
$\qquad \small \begin{array} {rrl} a&:& \ldots 10010100101001 \ldots \\ b&:& \ldots 00001010110000 \ldots \\ & & \ldots .........! \end{array} $

a) if at some position k both strings have simultanously a 1 then it is obvious that $\small n=2^k $ solves the problem.

So to have a counterexample we
b) need a pair of numbers, which have at no position simultanously a 1. But if we have nonterminating bitstrings (because of irrationality), then there will be one position k where in the bitstring of a is a 1 and the distance to the next 1 in the bitstring of b is minimal, say d. But then it suffices to use $\small n=2^{k+d} \cdot (1+2^{-1} + 2^{-2}+ \ldots 2^{-d}) $ to make the 1 in the bitstrings of a and b repeating such that the last new 1 in $\small n \cdot a $ matches that in $\small n \cdot b$ at position $\small k+d $ and we have the previous case and that pair of numbers is not a counterexample but a solution.

c) Because to have a nonterminating bitstring means, we have 1 anywhere we can always find a suitable position k and d in each pair a,b of irrational numbers.
A similar argument may be used for the rational numbers and -maybe- the "transfer" of that argument is really simple but I've not given too much thought into this.

  • $\begingroup$ I cannot understand accurately when the bit happens $1 + 1 = 10$ for $n \cdot a$ or $n \cdot b$. $\endgroup$
    – Yai0Phah
    Feb 1, 2012 at 13:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.