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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s