Integer Parts — Some basic properties and examples

The function: $[x]$

Definition:

Given a real number x, the expression $[x]$ represents the largest integer $\leq x$. Also, we denote by $||x|| = [x + \frac{1}{2}]$ the closest integer to x:

Theorem:

Let x and y be real numbers. Then,

(i) $[x+m] = [x] + m$, if m is an integer;

(ii) $[x] + [y] \leq [x + y] \leq [x] + [y] + 1$;

(iii) the number of positive integers $\leq x$ and division by a positive integer a is equal to $[x/a]$.

Theorem (Legendre’s Theorem):

Let p be a prime number and n a positive integer. Then, the largest exponent $\alpha = \alpha_{p}$ such that $p^{\alpha}|n!$ is given by $\alpha = \sum_{i=1}^{\infty}[\frac{n}{p^{i}}]$,

this last sum being in fact a finite sum since $[n/p^{i}] = 0$ when $i > \log {n}/\log {p}$. It follows that $n! = \prod_{p \leq n} p^{\sum_{i=1}^{\infty}[n/p^{i}]}$

Some classic questions based on integer parts and their solutions:

(1) Let $\alpha, \beta \in \Re$. Show that

(1a) $[\alpha] + [\beta] + [\alpha + \beta] \leq [2\alpha] + [2\beta]$

(1b) $[\alpha] + [\beta] + 2[\alpha + \beta] \leq [3\alpha] + [3\beta]$

(1c) $[\alpha] + [\beta] + 3[\alpha + \beta] \leq [4\alpha] + [4\beta]$

(1d) $2[\alpha] + 2[\beta] + 2 [\alpha + \beta] \leq [4\alpha] + [4\beta]$

(1e) $3[\alpha] + 3[\beta] + [\alpha + \beta] \leq [4\alpha] + [4\beta]$

(2) Show that $\frac{(2n)!}{(n!)^{2}}$ is an even integer for each $n \in N$.

(3) Let $m, n \in N$. Show that

(3a) $\frac{(2m)!(2n)!}{m!n!(m+n)!}$ is an integer.

(3b) $\frac{(4m)!(4n)!}{n!m!((m+n)!)^{3}}$ is an integer.

Solutions to above:

Proof (1):

Let $\alpha = n + a$, with $n \in Z$ and $0 \leq a <1$, and let $\beta = m +b$, $0 \leq b <1$.

(1a) Proving this inequality amounts to proving that $[a+b] \leq [2a] + [2b]$. If $0 \leq a + b <1$, the result is immediate. If $1 \leq a+b$, then $2a + 2b \geq 2$ and therefore $[2a] \geq 1$ or $2b \geq 1$ and the result follows.

(1b) It suffices to show that $2[a+b] \leq [3a] + [3b]$. If $0 \leq a + b <1$, the result follows. On the other hand, if $a+b \geq 1$, then we must show that $2 \leq [3a] + [3b]$. Clearly, $3a+ 3b \geq 3$. Now, since $[x]+[y] \geq [x+y] -1$ for all $x, y \in \Re$, it follows that $[3a] + [3b] \geq [3(a+b)] -1 \geq 2$, which gives the result.

(1c) It is enough to show that $3[a+b] \leq [4a] +[4b]$. If $0 \leq a+b <1$, the result is immediate. On the other hand, if $a+b \geq 1$, then $4a + 4b \geq 4$ and since $[4a] + [4b] \geq [4a+4b] -1 \geq 3$, we obtain the result.

Inequalities in (1d) and (1e) are obtained in a similar manner.

Proof (2):

This follows by observing that $\frac{(2n)!}{(n!)^{2}} = {{2n} \choose n} = 2{{2n-1} \choose {n-1}}$ for each integer $n \geq 1$.

Proof (3):

For part (3a), in light of Legendre’s theorem mentioned above, it is enough to show that $[\frac{2m}{p^{i}}] + [\frac{2n}{p^{i}}] \geq [\frac {m}{p^{i}}] + [\frac{n}{p^{i}}] + [\frac{m+n}{p^{i}}]$, an inequality which is a consequence of Problem (1a) above.

For part (3b), use, again, Legendre’s theorem and result of Problem (1c).

More classic gems of number theory are in the mines!! 🙂

Nalin Pithwa

This site uses Akismet to reduce spam. Learn how your comment data is processed.