Integer Parts — Some basic properties and examples | For the love of Maths: the Queen of all Sciences

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

Share this:

Like this:

Related

Leave a Reply Cancel reply