0
$\begingroup$

Let $p_1,p_2,...p_k$ be a finite set of prime numbers. Prove that the number of positive integers $n \leq x$ that can be written in the form $n=p_1^{r_1}p_2^{r_2}...p_k^{r_k}$ is at most $$ \prod_{i=1}^{k} (\frac{\log x}{\log p_i}+1)$$ Prove that if $x$ is sufficiently large, then there are positive integers $n \leq x$ that cannot be represented in this way.

I encountered this problem while going through the book "Elementary Methods in Number Theory" by Nathanson. Here, no additonal theory except the basic elementary facts about primes are given before this problem. Using these tools, can anyone please try and solve or give hints? I tried but I couldn't approach the problem.

$\endgroup$
3
  • 1
    $\begingroup$ Just think about $p_1, r_1$. How big can $r_1$ be? Well, $p_1^{r_1}≤x\implies r_1\log p_1≤\log x$. Thus $r_1\in \{0,\big \lfloor \frac {\log x}{\log p_1}\big \rfloor\}$. Can you finish from there? $\endgroup$ – lulu May 21 '20 at 14:16
  • $\begingroup$ Right! Yes, I got it. Thanks. $\endgroup$ – Dishant May 21 '20 at 14:23
  • $\begingroup$ To be clear: the intent of the second part is to use this upper bound to prove that there are infinitely primes (if you know there are infinitely many primes then it is obvious that there are arbitrarily large numbers that can't be factored using just $p_1, \cdots, p_k$). You need to argue that, for sufficiently large $x$, that product is $<x$. $\endgroup$ – lulu May 21 '20 at 14:31
0
$\begingroup$

I think the comment is good enough for you to figure out the solution to the first part. The $2$nd part is even easier, you could use the fact that primes are infinite and use the fundamental theorem of arithmetic.

$\endgroup$
3
  • $\begingroup$ Can you please elaborate on the second part? I wanted to know how I can use Fundamental Theorem of Arithmetic? $\endgroup$ – Dishant May 21 '20 at 14:27
  • $\begingroup$ Since primes are infinite, take a prime p outside of the given finite set , now clearly p cannot be written as a product of primes from the given set or else it would not be a prime.( In this argument we are using the fundamental theorem of arithmetic and the definition of prime) $\endgroup$ – Arpan1729 May 21 '20 at 14:37
  • $\begingroup$ Got it..thanks! $\endgroup$ – Dishant May 21 '20 at 14:40

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.