There are at least $n$ primes between $n$ and $n^2$

Theorem 1: $\pi(2^k) \le 3\dfrac{2^k}{k} $

(1)  For $k \le 5$:

$\pi(2^1) = 1 \le 2\dfrac{2^1}{1} = 4$
$\pi(2^2)  = 2 \le 2\dfrac{ 2^2}{2} = 4$
$\pi(2^3) = 4 \le 2\dfrac{2^3}{3} = \dfrac{16}{3} > 5$
$\pi(2^4) = 6 \le 2\dfrac{2^4}{4} = 8$
$\pi(2^5) = 11 \le 2\dfrac{2^5}{5} = \dfrac{64}{5} > 12$

(2)  Assume it is true up to some $k \ge 5$

(3) $\pi(2n) - \pi(n) \le (2n)\dfrac{\log 2}{\log n}$ since:

(a) $2^{2n} = \sum\limits_{i \le 2n}{{2n}\choose i}$

(b) $n^{\pi(2n) - \pi(n)} \le p^{\pi(2n) - \pi(n)} \le \prod\limits_{n < p \le2n}p \le {{2n}\choose{n}} \le 2^{2n}$

(c) $(\pi(2n) - \pi(n))\log n \le (2n)\log 2$

(d) $\pi(2n) - \pi(n) \le (2n)\dfrac{\log 2}{\log n}$

(4) $\pi(2^{k+1}) - \pi(2^k) \le (2^{k+1})\dfrac{\log 2}{\log 2^{k}}$ so that $\pi(2^{k+1}) \le \pi(2^k) + (2^{k+1})\dfrac{\log 2}{\log 2^{k}}$

(5)  $\log 2^{k} = k\log 2$ so that $\dfrac{1}{k} = \dfrac{\log 2}{\log 2^{k}}$

(6)  $5k+5 < 6k$ so that $\dfrac{5}{k} < \dfrac{6}{k+1}$

(7)  $\pi(2^{k+1}) \le \pi(2^k) + \dfrac{2^{k+1}}{k} \le \dfrac{3\times2^k}{k} + \dfrac{2\times2^k}{k} = \dfrac{5\times2^k}{k} \le \dfrac{3\times2^{k+1}}{k+1}$


Corollary: $\pi(x) \le 6 \log 2 \dfrac{x}{\log x}$

(1)  For $x \le 4, \pi(x) \le 6\log 2 \dfrac{x}{\log x}$

$\pi(2) = 1 \le 6\log2\dfrac{2}{\log 2}$ since $\log 2 < 12\log 2$

$\pi(3) = 2 \le 6\log 2\dfrac{3}{\log 3}$ since $2\log 3 < 18\log 2$

$\pi(4) = 2 \le 6\log 2\dfrac{4}{\log 4}$ since $2\log 4 < 24\log 2$

(2)  There exists $k$ such that $2^k \le x \le 2^{k+1}$

(3)  $\dfrac{1}{k+1} < \dfrac{\log 2}{\log 2^{k}}$ since $\log 2^k < (k+1)(\log 2)$

(4)  $\pi(x) \le \pi(2^{k+1}) \le 3\dfrac{2^{k+1}}{k+1} \le 6\dfrac{2^{k}}{k+1} < 6\log 2\dfrac{2^k}{\log 2^k} \le 6\log 2\dfrac{x}{\log x}$

Let $v_p(n)$ be the maximum power of $p$ that divides $n$

Lemma 1: $v_p(n!) = \sum\limits_{m \ge 1}\left\lfloor\dfrac{n}{p^m}\right\rfloor$

There are $\left\lfloor\dfrac{n!}{p}\right\rfloor$ instances of numbers divisible by $p$.

There are $\left\lfloor\dfrac{n!}{p^2}\right\rfloor$ instances of numbers divisible by $p^2$

And so on.

Lemma 2: $\lfloor{2x}\rfloor - 2\lfloor{x}\rfloor \in \{0, 1\}$

(1)  Let $\{x\}$ be the fractional part of $x$

(2)  If $\{x\} < \dfrac{1}{2}$, then $\lfloor{2x}\rfloor - 2\lfloor{x}\rfloor = 0$

(3)  If $\{x\} \ge \dfrac{1}{2}$, then $\lfloor{2x}\rfloor - 2\lfloor{x}\rfloor = 1$

Theorem 2: $\pi(x) \ge \dfrac{\log 2}{2}\dfrac{x}{\log x}$

(1) If $m > \dfrac{\log 2n}{\log p}$, then $\left\lfloor\dfrac{2n}{p^m}\right\rfloor - 2\left\lfloor\dfrac{n}{p^m}\right\rfloor = 0$

(2)  $v_p\left({{2n}\choose{n}}\right) = \sum\limits_{m \ge 1}\left(\left\lfloor\dfrac{2n}{p^m}\right\rfloor - 2\left\lfloor\dfrac{n}{p^m}\right\rfloor\right) \le
\left\lfloor\dfrac{\log 2n}{\log p}\right\rfloor$

(3)  $\dfrac{2^{2n}}{2n} \le {{2n}\choose{n}}$

(4) $2n\log 2 - \log 2n \le \log {{2n}\choose{n}} \le \sum\limits_{p \le 2n}\left\lfloor\dfrac{\log 2n}{\log p}\right\rfloor\log p \le \sum\limits_{p \le 2n}\log 2n = \pi(2n)\log 2n$

(5) $\pi(2n) \ge \log 2\dfrac{2n}{\log 2n} - 1$

(6)  For $2 \le x \le 16, \pi(x) \ge \dfrac{\log 2}{2}\dfrac{x}{\log x}$

• $\pi(2) = 1 = \dfrac{\log 2}{2}\dfrac{2}{\log 2} = 1$
• $\pi(3) = 2  > \dfrac{3}{2} > \dfrac{\log 2}{2}\dfrac{3}{\log 3}$
• $\pi(4) = 2 =  \dfrac{4}{2} > \dfrac{\log 2}{2}\dfrac{4}{\log 4}$
• $\pi(5) = 3 \ge \dfrac{5}{2} > \dfrac{\log 2}{2}\dfrac{5}{\log 5}$
• $\pi(6) = 3 = \dfrac{6}{2} > \dfrac{\log 2}{2}\dfrac{6}{\log 6}$
• $\pi(7) = 4 > \dfrac{7}{2} > \dfrac{\log 2}{2}\dfrac{7}{\log 7}$
• $\pi(8) = 4 = \dfrac{8}{2} > \dfrac{\log 2}{2}\dfrac{8}{\log 8}$
• $\pi(9) = 4  > \dfrac{3}{2} = \dfrac{\log 2}{3\log 2}\dfrac{9}{2} > \dfrac{\log 2}{2}\dfrac{9}{\log 9}$
• $\pi(10) =4 > \dfrac{5}{3} = \dfrac{\log 2}{3\log 2}\dfrac{10}{2} > \dfrac{\log 2}{2}\dfrac{10}{\log 10}$
• $\pi(11)=5 > \dfrac{11}{6} = \dfrac{\log 2}{3 \log 2}\dfrac{11}{2} > \dfrac{\log 2}{2}\dfrac{11}{\log 11}$
• $\pi(12)=5 > 2 = \dfrac{\log 2}{3 \log 2}\dfrac{12}{2} > \dfrac{\log 2}{2}\dfrac{12}{\log 12}$
• $\pi(13)=6 > \dfrac{13}{6} = \dfrac{\log 2}{3 \log 2}\dfrac{13}{2} > \dfrac{\log 2}{2}\dfrac{13}{\log 13}$
• $\pi(14)=6 > \dfrac{7}{3} = \dfrac{\log 2}{3 \log 2}\dfrac{14}{2} > \dfrac{\log 2}{2}\dfrac{14}{\log 14}$
• $\pi(15)=6 > \dfrac{5}{2} = \dfrac{\log 2}{3 \log 2}\dfrac{15}{2} > \dfrac{\log 2}{2}\dfrac{15}{\log 15}$
• $\pi(16)=6 > \dfrac{8}{3} = \dfrac{\log 2}{3 \log 2}\dfrac{16}{2} > \dfrac{\log 2}{2}\dfrac{16}{\log 16}$

(7)  There exists $n$ such that $16 \le 2n < x \le 2n+2$

(8)  $\dfrac{2n}{\log 2n} - \dfrac{n+1}{\log 2n} = \dfrac{n-1}{\log 2n} \ge \dfrac{7}{\log 16} = \dfrac{7}{4\log 2} > \dfrac{4}{4\log 2} = \dfrac{1}{\log 2}$

(9) $\pi(x) \ge \pi(2n) \ge \log 2\dfrac{2n}{\log 2n} - 1 = \dfrac{2n\log 2 - \log 2n}{\log 2n} = \dfrac{\log\frac{2^{2n}}{2n}}{\log 2n}$

(10) for $n=8$, $2^6 > 8$

(11)  $2(2^{n-2}) = 2^{(n+1)-2} > 2n > n+1$ so that $\dfrac{2^{n-2}}{n} > 1$ and $\dfrac{2^{n-1}}{2n} > 1$ and $\dfrac{2^{2n}}{2n} > 2^{n+1}$

(12)  $\dfrac{\log\frac{2^{2n}}{2n}}{\log 2n} \ge \dfrac{\log 2^{n+1}}{\log (2n+2)} = \dfrac{(n+1)\log 2}{\log (2n+2)}$

(13)  Since $n+1 = \dfrac{2n+2}{2} \ge \dfrac{x}{2}$, it follows that $\dfrac{(n+1)\log 2}{\log (2n+2)} \ge \dfrac{x\log 2}{2\log x}$

Corollary: For $46 \ge n \ge 4$, there are at least $n$ primes between $n$ and $n^2$

(1)  For $n \ge 28$, then:

• Between $4$ and $16$, there are 4 primes: $\{5, 7, 11, 13\}$
• Between $5$ and $25$, there are 6 primes: $\{7,11,13,17,19,23\}$
• Between $6$ and $36$, there are more than $6$ primes: $\{7,11,13,17,19,23,\dots\}$
• Between $7$ and $49$, there are more than $7$ primes: $\{11,13, 17, 19, 23, 29, 31,\dots\}$
• Between $8$ and $64$, there are more than $8$ primes: $\{11, 13,17,19,23,29,31,37,\dots\}$
• Between $9$ and $81$, there are more than $9$ primes: $\{11,13,17,19,23,29,31,37,41,\dots\}$
• Between $10$ and $100$, there are more than $10$ primes: $\{11,13,17,19,23,29,31,37,41,43,dotts\}$
• Between $11$ and $121$, there are more than $11$ primes: $\{13,17,19,23,29,31,37,41,43,47,53,\dots\}$
• Between $12$ and $144$, there are more than $12$ primes: $\{13,17,19,23,29,31,37,41,43,47,53,59,\dots\}$
• Between $13$ and $169$, there are more than $13$ primes: $\{17,19,23,29,31,37,41,43,47,53,59,61,67,\dots\}$
• Between $14$ and $196$, there are more than $14$ primes: $\{17,19,23,29,31,37,41,43,47,53,59,61,67,71,\dots\}$
• Between $15$ and $225$, there are more than $15$ primes: $\{17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,\dots\}$
• Between $16$ and $256$, there are more than $16$ primes: $\{17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,\dots\}$
• Between $17$ and $289$, there are more than $17$ primes: $\{19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,\dots\}$
• Between $18$ and $324$, there are more than $18$ primes: $\{19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,\dots\}$
• Between $19$ and $361$, there are more than $19$ primes: $\{23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,\dots\}$
• Between $20$ and $400$, there are more than $20$ primes: $\{23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,\dots\}$
• Between $21$ and $441$, there are more than $21$ primes, $\{23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,\dots\}$
• Between $22$ and $484$, there are more than $22$ primes, $\{23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113\dots\}$
• Between $23$ and $529$, there are more than $23$ primes, $\{29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,\dots\}$
• Between $24$ and $576$, there are more than $24$ primes, $\{29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,\dots\}$
• Between $25$ and $625$, there are more than $25$ primes, $\{29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,\dots\}$
• Betwen $26$ and $676$, there are more than $26$ primes, $\{29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,\dots\}$
• Between $27$ and $729$, there are more than $27$ primes, $\$\{29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,\dots\}$

(2)  $\pi(n^2) - \pi(n) \ge \dfrac{(n^2)\log 2}{2\log (n^2)} - \dfrac{(6n)\log 2}{\log n} = \dfrac{(n^2)\log 2}{4\log (n)} - \dfrac{(6n)\log 2}{\log n} = \dfrac{(\frac{n}{4} - 6)(n\log 2)}{\log n}$

An infinitude of primes

Euclid provided a proof for the infinitude of primes.  The following proof is based on his argument:

Theorem 1:  There are an infinite number of primes

(1)  Assume that $p_n$ is the largest prime.

(2)  Let $q = p_n! + 1$

(3)  Since $q > p_n$, $q$ cannot be a prime (by our assumption).

(4)  So, therefore a prime $p$ divides $q$

(5)  But if $p \le p_n$, then $p | p_n!$ and $p | (p_n! + 1) - p_n! = 1$ which is impossible.

(6)  Therefore, we have a contradiction since $p > p_n$ but $p$ is a prime.

QED

Introduction

The purpose of this blog will be for me to focus on primes and the fundamental theorems related to them.

These will represent my notes.  The goal is to present the fundamental ideas of number theory in as clear a manner as I can without requiring any background beyond standard arithmetic, a genuine interest in math, and an openness to the concepts involved.

The content will be taken straight from number theory text books, classic math papers, and forums on math web sites.

My favorite math web site for asking questions about mathematics is math.stackexchange.com.  If you haven't been to this site, I encourage you to visit if you have any questions.