3
$\begingroup$

I am asked to use the Fundamental Theorem of Arithmetic to show that:

For $x > 1, \; x \leq \left( 1 + \frac{\log x}{\log2} \right) ^{\pi(x)}$

I have that:

$\exists \text{ primes } p_1,\dots,p_{\pi(x)} \text{ and non-negative integers } n_1, \dots, n_{\pi(x)}$ such that:

$x = \prod \limits_{i=1}^{\pi(x)}{p_i^{n_i}}$ so then $\log x = \sum\limits_{i=1}^{\pi(x)}n_i\log p_i$

Now I'm thinking I can use $\prod \limits_{i=1}^{\pi(x)}{\left( 1 + \frac{\log x}{\log p_i}\right)} $ as a stepping stone since $\prod \limits_{i=1}^{\pi(x)}{\left( 1 + \frac{\log x}{\log p_i}\right)} \leq \left( 1 + \frac{\log x }{\log 2} \right)^{\pi(x)}$, but I'm unsure how I can show that:

$x \leq \prod \limits_{i=1}^{\pi(x)}{\left( 1 + \frac{\log x}{\log p_i}\right)}$

Any help you may be able to offer would be greatly appreciated, thank you!

$\endgroup$
  • 1
    $\begingroup$ You can write every $k \leqslant x$ in the form $\prod_{i = 1}^{\pi(x)} p_i^{n_i}$. From $k \leqslant x$, what (simple) bounds can you find for $n_i$? $\endgroup$ – Daniel Fischer Oct 22 '17 at 13:50
2
$\begingroup$

By the fundamental theorem of arithmetic (in fact we don't need its full strength, only the [easier] existence of prime factorisations, not the uniqueness) every positive integer $k$ has a prime factorisation

$$k = \prod_{i = 1}^{\infty} p_i^{n_i} \tag{1}$$

where $(p_i)$ is the sequence of primes in ascending order and the exponents $n_i$ are nonnegative integers, only finitely many of which are nonzero. In particular for every $i$ we have the inequality

$$p_i^{n_i} \leqslant k \tag{2}$$

since the product of the other factors is $\geqslant 1$ (it's a positive integer). It follows that $n_i = 0$ if $p_i > k$, and thus for a positive integer $k \leqslant x$ we have the factorisation

$$k = \prod_{i = 1}^{\pi(x)} p_i^{n_i} \tag{1'}$$

and the inequality

$$p_i^{n_i} \leqslant k \leqslant x \tag{2'}$$

from which we obtain

$$n_i \leqslant \frac{\log k}{\log p_i} \leqslant \frac{\log x}{\log p_i} \tag{3}$$

by taking logarithms and rearranging. Thus in the factorisations of positive integers $\leqslant x$, there are

$$1 + \biggl\lfloor \frac{\log x}{\log p_i}\biggr\rfloor \leqslant 1 + \biggl\lfloor \frac{\log x}{\log 2}\biggr\rfloor \leqslant 1 + \frac{\log x}{\log 2}$$

possible exponents for the prime $p_i \leqslant x$ (namely $0, 1, \dotsc, \bigl\lfloor \frac{\log x}{\log p_i}\bigr\rfloor$). Using all possible combinations of the exponents that may appear in the factorisation of a positive integer $k \leqslant x$, we can create

$$\prod_{i = 1}^{\pi(x)}\biggl(1 + \biggl\lfloor \frac{\log x}{\log p_i}\biggr\rfloor\biggr) \leqslant \biggl(1 + \frac{\log x}{\log 2}\biggr)^{\pi(x)}$$

products. For $x \geqslant 3$, some of these products (and for not-small $x$ the overwhelming majority of these products) will be larger than $x$, but by the fundamental theorem of arithmetic, all positive integers $k \leqslant x$ have a representation as such a product, whence

$$\lfloor x\rfloor \leqslant \prod_{i = 1}^{\pi(x)}\biggl(1 + \biggl\lfloor \frac{\log x}{\log p_i}\biggr\rfloor\biggr) \leqslant \biggl(1 + \frac{\log x}{\log 2}\biggr)^{\pi(x)}\,. \tag{4}$$

This is almost the desired inequality, only that we have $\lfloor x\rfloor$ as the left hand side rather than $x$. For $x \geqslant 3$ there is always at least one product exceeding $x$, and thus there are at least $\lfloor x\rfloor + 1 > x$ products, whence we have the desired

$$x \leqslant \biggl(1 + \frac{\log x}{\log 2}\biggr)^{\pi(x)} \tag{5}$$

for $x \geqslant 3$. And for $x = 2$, $(4)$ is the same as $(5)$.

However, $(5)$ does not hold for all non-integral values $1 < x < 3$, for example with $x = \sqrt{8} = 2^{3/2}$ we have

$$\biggl(1 + \frac{\log \sqrt{8}}{\log 2}\biggr)^{\pi(\sqrt{8})} = \biggl(1 + \frac{3}{2}\biggr)^1 = \frac{5}{2} < \sqrt{8}\,.$$

$\endgroup$

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.