Name: Prime Numbers From 1 to 100
Uploaded: 2019-07-19
Duration: 7 min 49 s
Description: The number 2 is the only even prime number. But, how do you find the prime numbers between 1 and 100? This video explains the easiest way to find prime numbers.

Question

For a positive integer

n

, define

A (n)

to be

\frac{(2 n)!}{{(n!)}^{2}}

. Determine the sets of positive integers

n

for which:

$A (n)$ is an even number.

Accepted Answer

We have,

$A (n) : \frac{(2 n)!}{{(n!)}^{2}}$

Since, the product of $k$ consecutive integers is divisible by $k!, A (n)$ is an integer.

We compare the highest powers of $2$ dividing the numerator and denominator to determine the nature of $A (n)$ .

Suppose we express $n$ in the base $2$ , say

$n = a_{l} 2^{l} + a_{l - 1} 2^{l - 1} + a_{l - 2} 2^{l - 2} + \dots + a_{1} \cdot 2 + a_{0}$

Since, $a_{l} = 1$

The highest power of $2$ dividing $n!$ is given by

$s = [\frac{n}{2}] + [\frac{n}{2^{2}}] + [\frac{n}{2^{3}}] + \dots + [\frac{n}{2^{l}}]$

where, $[x]$ denotes the largest integer smaller than $x$ .

But, for $1 \leq m \leq l$ ,

$[\frac{n}{2^{m}}] = a_{l} 2^{l - m} + a_{l - 1} 2^{l - m - 1} + \dots + a_{m}$

Thus,

$s = \sum_{m = 1}^{l} [\frac{n}{2^{m}}]$

$= \sum_{m = 1}^{l} \sum_{k = m}^{l} a_{k} 2^{k - m}$

$= \sum_{k = 1}^{l} a_{k} (\sum_{m = 1}^{k} 2^{m} - 1)$

$= \sum_{k = 1}^{l} a_{k} (2^{k} - 1)$

$= \sum_{k = 0}^{l} a_{k} 2^{k} - \sum_{k = 0}^{l} a_{k}$

$= n -$ {sum of the digits of $n$ in the base $2$ }

Hence, the highest power of $2$ dividing ${(n!)}^{2}$ is $2 s = 2 n - 2$ (sum of the digits of $n$ in the base $2$ ).

Similarly, the highest power of $2$ dividing $(2 n)!$ is $t = 2 n$ - (sum of the digits of $2 n$ in the base $2$ ). But the digits of $n$ in base $2$ and those of $2 n$ in base $2$ are the same except for a zero at the end of the representation for $2 n$ .
Thus,
$t - 2 s = a_{l} + a_{l - 1} + a_{l - 2} + \dots + a_{1} + a_{0}$

where the $a_{i}$ are the digits of $n$ in base $2$ . Note that $a_{l} = 1$ .

Hence $t - 2 s \geq 1$ . But $A (n)$ is even if and only if $t - 2 s \geq 1$ . Hence, it follows that $A (n)$ is even for all $n$ .

C R Pranesachar, B J Venkatachala and, C S Yogananda Solutions for Chapter: Number Theory, Exercise 1: Number Theory

C R Pranesachar Mathematics Solutions for Exercise - C R Pranesachar, B J Venkatachala and, C S Yogananda Solutions for Chapter: Number Theory, Exercise 1: Number Theory

Questions from C R Pranesachar, B J Venkatachala and, C S Yogananda Solutions for Chapter: Number Theory, Exercise 1: Number Theory with Hints & Solutions

Learn and Prepare for any exam you want !