Attempted Translation of Kanold

An upper bound for Jacobsthal's Function

by Hans-Joachim Kanold

The untranslated article is here.

Paul Erdos:  Let $n$ be any integer.  Jacobsthal defines $g(n)$ to be the least integer so that amongst any $g(n)$ consecutive integers $a, a+1, \dots, a+g(n)-1$ there is at least one which is relatively prime to $n$

Paul Erdos has shown that for almost all $n$, the order of magnitude of $g(n)$ is the same as $\frac{n}{\varphi(n)}V(n)$ with  $\varphi(n)$, the well-known Euler function, and with $V(n)$  the number of different prime divisors of $n$.

"Almost all” means: all natural numbers $n$ with the exception of a set of natural density zero. Note [3] investigated relationships between $g(n)$ and prime numbers in arithmetic sequences.  (Note 3: KANOLD, H.-J.: Über Primzahlen in arithmetischen Folgen. Math. Ann. 156, 393-395 (1964), t57, 358-362 (t965).)

The present work aims to provide further estimates of $g(n)$ to be derived.

We can rely on square-free arguments $n>1$ restricted.  

Let:

(1) $n = p_1 p_2  \dots p_k$ with $2 \le p_1 < p_2 < \dots < p_k$ the canonical decomposition of $n$ into a product of prime numbers

Furthermore, for the shortcut:

(2)  $g(n) = g$ 

And: $g(p_1) = 2$ applies, we can now also assume $k > 1$.  Based on the definition of $g$ there exists (at least) one natural number $a$ so that:

(3)  $(a,n) = (a+g,n) = 1$;  and $(a + \gamma) > 1$ for $\gamma = 1, \dots, g-1$.

With the known function of Möbius we get a first basic relationship:

(4)  $g -1 = - \sum\limits_{d|n\text{, }d>1}\mu(d)\left(\left[\frac{a+g-1}{d}\right]-\left[\frac{a}{d}\right]\right)$

We now introduce the following abbreviated terms.

(5)  $\frac{a+g-1}{d} - \left[\frac{a+g-1}{d}\right] = \Theta_d; \frac{a}{d} - \left[\frac{a}{d}\right] = \vartheta_d$

From (3), for $d > 1$, it follows:

(6)  $0 \le \Theta_d \le 1 - \frac{2}{d}; \frac{1}{d} \le \vartheta_d \le 1 - \frac{1}{d}$ 

Because $\Theta_d = 1 - \frac{1}{d}$ leads to $d|a+g$, the second basic relationship is:

(7)  $(g-1)\frac{\varphi(n)}{n} = \sum_\limits{d|n\text{, }d>1}\mu(d)(\Theta_d - \vartheta_d)$

Let:

(8) $(a+\gamma, n) = \delta_{\gamma} \text{                      } (\gamma = 1, \dots, g-1)$

then according to (1) and (3) always:

(9)  $\delta_{\gamma} \ge p_1; \delta_{\gamma} | p_1 \dots p_k; V(\delta_{\gamma}) \ge 1$

We look at the product:

(10)  $\Delta = \delta_1 \delta_2 \dots \delta_{g-1}$

And ask: How often is $(1 \le K \le k)$  in $\Delta$? The number of multiples of $p_K$ which is not larger than $a + g - 1$ are given by $\left[\frac{a+g-1}{p_K}\right]$; the number of multiples that are not greater than $a$ is $\left[\frac{a}{p_K}\right]$.  So:

(11)  $\Delta = \prod\limits_{K=1}^k {p_K}^{\left[\frac{a+g-1}{p_K}\right] - \left[\frac{a}{p_K}\right]}$

The number of $\Delta$ contained prime numbers, each according to its multiplicity counted, is therefore 

(12)  $\sum\limits_{K=1}^{k} \left(\left[\frac{a+g-1}{p_K}\right] - \left[\frac{a}{p_K}\right]\right)$

According to (3) it is of course:

(13)  $\left[\frac{a}{p_K}\right] = \left[\frac{a-1}{p_K}\right]$; $\left[\frac{a+g-1}{p_K}\right] = \left[\frac{a+g}{p_K}\right]$

If we denote, as in the introduction, with $V(m)$ the number of different prime divisors of a natural number $m$, then we get the third basic relationship:

(14)  $\sum\limits_{\gamma = 1}^{g-1}V(\delta_{\gamma}) =$ $\sum\limits_{K=1}^{k}$ $ \left(\left[\frac{a+g-1}{p_K}\right] - \left[\frac{a}{p_K}\right]\right)$  $= (g-1)\sum\limits_{K=1}^{k}\frac{1}{p_K} + \sum\limits_{K=1}^k \left( \vartheta_{p_K} - \Theta_{p_K} \right)$

For convenience, we will use:

(15)  $\frac{1}{g-1}\sum\limits_{\gamma=1}^{g-1} V(\delta_{\gamma})  -$ $\sum\limits_{K=1}^k \frac{1}{p_K} = \frac{1}{g-1}\sum\limits_{K=1}^k$ $( \vartheta_{p_K} - \Theta_{p_K} ) = \xi$

Let $d | n, d \nmid a + \gamma$ for $\gamma = 1, \dots, g-1$. It follows:

(16)  $\Theta_d - \vartheta_d = \frac{g-1}{d}$

Let $d | n, d> 1$ and:

(17)  $d | a +  \gamma_d$; $d | a + g - {\gamma`}_d$; $1 \le \gamma_d \le g - {\gamma'}_d$;  $1 \le \gamma_d, {\gamma'}_d \le \text{min}\{d-1, g-1\},$

It follows from (5):

(18)  $\vartheta_d = 1 - \frac{\gamma_d}{d}$; $\Theta_d = \frac{{\gamma'}_d - 1}{d}$; $\Theta_d - \vartheta_d = \frac{\gamma_d + {\gamma'}_d -1}{d} - 1$

According to (17):

(19)  $\gamma_d + {\gamma'}_d \le \text{min}\{g; 2d-2\}$;  $0 \le g - \gamma_d - {\gamma'}_d \equiv 0 \pmod d$

II. We now want to derive some simple estimates from the basic relationships.

Lemma 1:  It always applies that: $0 < |\xi| < 1$

Proof: We first show that $\xi(g-1)$ cannot be completely, therefore also in particular $\xi$ not equal to zero.  From (15) we get:

(20)  $p_1 \dots p_k \sum\limits_{\gamma = 1}^{g-1}V(\delta_{\gamma}) - (g-1) \sum\limits_{K=1}^k \frac{p_1\dots p_k}{p_K} = \xi(g-1)p_1 \dots p_k$ 

Furthermore,

(21)  $\left(\sum\limits_1^k \frac{p_1 \dots p_k}{p_K}, p_1 \dots p_k \right) = 1$

Would now be $\xi(g-1)$ completely, so would be:

(22)  $p_1 \dots p_k | g-1$; $g-1 \ge n$ 

But that would mean that there is a sequence of length $n$ which does not contain a number that is relatively prime to $n$, which is obviously a contradiction, since every such sequence has exactly $\varphi(n)$ to $n$ must contain coprime numbers.  It is always (cf. [2]).

(23)  $g \ge k+1$

After (6) and (15) follows

(24)  $|\xi| \le \frac{1}{k} \sum\limits_1^k |\vartheta_{p_K} - \Theta_{p_K}| \le \frac{1}{k} \sum\limits_1^k \left(1 -  \frac{1}{p_K} \right) < 1$

This completes the proof of the above proposition.

Lemma 2: Let $k>1$. For $\xi < 0$ applies $g < \frac{k-3}{|\xi|} -2$,  For $\xi > 0$ applies $g < \frac{k-1}{\xi} + 2$ 

Proof:  Because of $g(p_1 \dots p_k) > g \left(\frac{p_1 \dots p_k}{p_K} \right)$ for any $K \in \{ 1, \dots, k \}$  are for $d = p_K$ the prerequisites (17) are met.  According to (15), (17) to (19) we obtain:

(25)  $g - 1 = \frac{1}{\xi} \sum\limits_1^k \left( 1 - \frac{\gamma_{p_K} + {\gamma'}_{p_K} -1}{p_K} \right)$; $2 \le \gamma_{p_K} + {\gamma'}_{p_K} \equiv g \pmod {p_K}$

Let $\xi > 0$. If $\gamma_{p_K} + {\gamma'}_{p_K} = 2$ for all $K=1, \dots, k$ then for $k > 1$, $g - 2 > 0$

(26)  $n = p_1 \dots p_k | g-2$, $g-2 \ge n$

which leads to a contradiction as in (23). Thus, according to (9), (15) and (25) we have

(27)  $g-1 < \frac{1}{\xi} \left( k - \sum\limits_1^k \frac{1}{p_K} \right) = \frac{k}{\xi} - \frac{1}{\xi} \left( \frac{1}{g-1} \sum\limits_1^{g-1} V(\delta_{\gamma})  - \xi\right) \le \frac{k}{\xi} - \frac{1}{\xi}(1 - \xi);$ $g < \frac{k-1}{\xi} + 2$ 

Let $\xi < 0$. From (25) we obtain (28):

(28) $g-1 = \frac{1}{|\xi|} \left( \sum\limits_1^k \frac{\gamma_{p_K} - {\gamma'}_{p_K}-1}{p_K} -k \right)$

Assume $\gamma_{p_K} + {\gamma'}_{p_K} = 2p_K - 2$ [cf. (19)] for $K=1, \dots, k$, so would be

(29)  $p_K | g - 2p_K+2$; $n=p_1 \dots p_k | g+2$; $g+2 \ge n$

Then there would be a sequence of natural numbers of length $n-3$, which does not contain a number that is coprime to $n$. We would have:

(30) $n - \varphi(n) \ge n - 3$; $3 \ge \varphi(n) = (p_1 - 1) \dots (p_k - 1)$

Because $p_3 -1 \ge 4$, it follows $k \le 2$; because of $|\xi| = \sum\limits_1^k \frac{1}{p_K} - \frac{1}{g-1}  \sum\limits_1^{g-1} V(\delta_{\gamma}) \le \sum\limits_1^k \frac{1}{p_K} - 1$ 

but delivers

(31)  $1 + |\xi| \le \sum\limits_1^k \frac{1}{p_K} \le \frac{1}{2} + \frac{1}{3}$

a contradiction. Therefore, according to (28)

(32) $g - 1 < \frac{1}{|\xi|} \left( \sum\limits_1^k \frac{2p_K - 3}{p_K} - k\right) = \frac{1}{|\xi|} \left( k - 3 \sum\limits_1^k \frac{1}{p_K} \right) \le \frac{1}{|\xi|} (k - 3 - 3|\xi|)$; $g < \frac{k-3}{|\xi|} - 2$

This proves the Lemma 2. A simple consequence is

Lemma 3: Let $k > 1$. For $\xi \ge \frac{1}{k+1}$ or $\xi \le \frac{-1}{k+3}$ follows $g \le k^2$

Proof: If $\xi \le \frac{-1}{k+3}$, then Lemma 2 provides:

(33)  $g < (k-3)(k+3) - 2 = k^2 - 11 < k^2$

If $\xi \ge \frac{1}{k+1}$, then follows:

(34)  $g < (k-1)(k+1) + 2 = k^2 + 1$; $g \le k^2$

From a slightly different structure is the:

Lemma 4: If $m$ and $n$ are coprime, then $g(mn) \le \text{min} \{ mg(n) - \varphi(m) + 1; ng(m) - \varphi(n) + 1  \} $

Proof: We imagine a sequence of length $mg(n) = mg$ given $a+1, a+2, \dots, a+mg.$ We arrange these $mg$ numbers in a rectangular scheme:

(35) 

$a+1 \qquad \qquad \qquad \qquad a+2, \dots, \dots, \dots, a+m$

$a+m+1 \qquad \qquad \qquad a+m+2, \dots,\dots, \dots, a+2m$

$\vdots$

$a+(g-1)m + 1 \qquad a+(g-1)m+2,\dots,\dots,\dots,a+gm$

Each column of (35) consists of numbers belonging to the same residue class $\text{mod}$ $m$. There are exactly $\varphi(m)$ columns whose numbers are all relatively prime to $m$ Let the residue classes be:

(36) $a + r_1, a + r_2, \dots, a + r_{\varphi}$ $(\varphi = \varphi(m))$ 

with $1 \le r_1 < r_2 < \dots < r_{\varphi} \le m$ is relatively prime to $m$. We then extract the following sub-scheme from (35).

(37)

$a + r_1\qquad \qquad \qquad \qquad a + r_2, \dots, \dots, \dots, a + r_{\varphi}$

$a + m + r_1\qquad \qquad \qquad a + m + r_2, \dots, \dots, \dots, a + m + r_{\varphi}$

$\vdots$

$a+(g-1)m + r_1\qquad a+(g-1)m + r_2, \dots, \dots, \dots, a+(g-1)m + r_{\varphi}$

All numbers in (37) are relatively prime to $m$. Now consider any column of (37).

(38)  $a + \gamma m + r_i$; $\gamma = 0, 1, \dots, g-1$; $i \in \{ 1, \dots, \varphi \}$

Because of $(m,n)=1$, there exists a natural number $v_i$  such that:

(39) $a + r_i + v_in \equiv 0 \pmod m$

is fulfilled. Then we look at the consecutive numbers:

(40)  $\frac{a + r_i + v_i n}{m} + \gamma$

Among these numbers, there is always at least one that is relatively prime to $n$. Therefore, in each column of (37) there is at least one number that is relatively prime to $mn$. This gives

(41)  $g(mn) \le mg(n) - \varphi(m) + 1$

Because of the symmetry in $m$ and $n$, Lemma 4 is proved. If $m$ is equal to a prime number $p$, then we get

(42)  $g(pn) \le pg(n) - p + 2$

III We now want to estimate the function $p$ for small values ​​of $k$. We start with

Lemma 5: If $(n,6)=1$; $1 < k \le 11$; Then $g < 2k$

Proof: According to the prerequisite $p_1 \ge 5$. For $k=2,3,4$ is from the numbers $a + 1, a + 2, \dots, a + k + 1$ at most one by $p_1,$ or $p_2, \dots,$ or $p_k$ divisible.

So we have for $1 < k \le 4$

(43)  $k+1 \le g \le k+1$, i.e. $g = k+1 < 2k$

Assume: $5 \le k \le 11$. We have $p_3 \ge 11$ ; $p_4 \ge 13$; $p_5 \ge 17$; $\dots$ so

(44)  $p_{k-2} > 2k$ for $k = 5, \dots 11$

Now consider a sequence of length $2k-1$:

(45)  $a+1, a+2, \dots, a + 2k-1$,

then at most one of these numbers is divisible by $p_k$ or $p_{k-1}$ or $p_{k-2}$.  If $g-1 \ge 2k - 1$, then we could choose the sequence (45) such that of these numbers at least $2k-4$ are not relatively prime to $p_1 p_2 \dots p_{k-3}$. Since none of the prime numbers $p_3 \dots p_{k-3}$ can be contained in more than two of the numbers (45), at least 6 of these numbers must not be relatively prime to $p_1 p_2$. For $k\le 7$ at most two of the numbers are divided by $p_2$ divisible; then follows $2k-1 \ge 16$, thus a contradiction to $k \le 7$. For $k=8, 9, 10, 11$ applies instead of (44)

(46) $p_{k-3} > 2k$

Of the numbers (45) at least $2k-5$ are not relatively prime to $p_1 \dots p_{k-4}$ At least 7 of these numbers do not have to be relatively prime to $p_1 p_2$, at least 4 must be divisible by $p_1$. This gives $p_1 = 5$; $k \ge 9$. For $k=9, 10, 11$:

(47) $p_{k-4} \ge 2k-1$

Of the numbers (45) at least $2k-6$ are not relatively prime to $p_1 \dots p_{k-5}$ At least 8 are not coprime to $p_1 p_2$, at least 5 must be divisible by  $p_1 = 5$. Only the following case remains:

(48) $k=11$; $a+1 \equiv 0 \pmod 5$

Assume that $g(n) \ge 2k-1$ so that none of the numbers $a + \gamma + v\times 5$ $(\gamma = 2, 3, 4, 5$; $v = 0, 1, 2, 3)$ is coprime to $p_2 \dots p_{11}$ At most, 3 of these numbers are divisible by $p_2 \ge 7$ since the numbers are in the range of  $a+2+0*5=a+2$ to $a+5+3*5 = a+20$ and if more than $3$ were divisible by $p_2$, then the fourth  such integer would be greater than $a+2+3*7 = a+23$ which is impossible since it is outside of the range; of the remaining $13$ numbers, one is divisible by $p_{11}$ or $p_{10}$ or $p_9, \dots $ or $p_6 (\ge 19)$ So at least $7$ numbers must be divisibly by $p_3, p_4, p_5$. But $p_3 \ge 11$ which is a contradiction since at most $3$ can be divided by $p_5 > p_4 > p_3 \ge 11$. This completes the proof for Lemma 5.

Theorem 1: For  $1 < k \le 12$, it follows that $g\le k^2$

Proof: Assume $(n,6)=1$ According to Lemma 5, for $1 < k \le 11$

(49)  $g \le 2k - 1 < k^2$

For $k=12, p_1 \ge 7$ we receive directly

(50) $\sum\limits_1^{12} \frac{1}{p_K} < 1 - \frac{1}{3}$

which according to Lemma 2 leads to

(51)  $g \le 34 < k^2$

The case $k=12, p_1 = 5$ leads according to lemmas 4 and 5 to 

(52)  $g \le 5(2\times 11 - 1)  - 3 = 102 < k^2$

Assume $(n,6)=2$. Lemma 4 leads to 

(53)  $g \le 2g(p_2 \dots p_k)$ 

so for $k=2$, $g \le 4 = k^2$ and for $3 \le k \le 12$ according to (49) to

(54)  $g \le 2(2k-3) = 4k-6 < k^2$

Let $(n,6)=3$. One can immediately see that for $k=2$ the equation:

(55)  $g=3$ $(<k^2)$

applies; for $3 \le k \le 12$ is according to (49) and Lemma 4

(56)  $g \le 3(2k-3)-1 = 6k - 10 < k^2$

Finally, $(n,6)=6$, i.e. $p_1 = 2, p_2 = 3$ According to (53) $k=2$ the equation $g=2^2$ fulfilled; for $k=3$ is according to (55) immediately $g \le 2\times 3 < 3^2$ is evident. For $4 \le k \le 13$ we obtain from (56), with $k-1$ instead of $k$,

(57)  $g \le 12k -32 \le k^2$ for $k = 4, 8, 9, 10, 11, 12, 13$

We therefore still have to prove the theorem in the cases

(58)  $k = 5,6,7$; $p_1 = 2, p_2 = 3$

where according to (53) it is sufficient to show that

(59)  $g(p_3 \dots p_k) \le \frac{k^2}{2}$

is fulfilled. According to the fourth proposition,

(60)  $g(p_3 \dots p_k) \le 3g(p_3 \dots p_k) - 1$ 

There $p_3 \ge 5$ must be is for $k=5,6$ also $g(p_3 \dots p_k) = k-1$ what to

(61)  $g \le 2 \times 3(k-1) - 2 = 6k - 8 < k^2$

Finally, for k = 7 we have the estimates

(62)  $g(p_3 \dots p_7) \le 7 = k$; $g \le 6\times 7 - 2 = 40 < k^2$

This proves Theorem 1.

IV. In this section we want to obtain more general results. We start with

Theorem 2: Let $q_1, q_2, \dots$ be the $i$th prime numbers ordered by size; $n=p_1 \dots p_k$ with $p_1 < \dots < p_k$ given such that $p_1 \ge q_{l +  1}, 1 < k \le l^e$ is valid. Then $g \le k^2$

Proof: From B. Rosser [4]:

(Note: B. Rosser showed that the $n$th prime is greater than $n \log n$: link, Pierre Dusart improved on this result in 1999: link)

(63)  $\sum\limits_{v=1}^m \frac{1}{q_v} = \log \log m + B_m$, $B_m > B_{m+1}$ $(m \ge 2)$;

for $m=1$ of course applies 

(64) $\sum\limits_{v=1}^1 \frac{1}{q_v} = \frac{1}{2}$.

For $l \ge 1$ we get, with $q_{l+1} = p_1 < \dots < p_k$,

(65) $\sum\limits_1^k \frac{1}{p_K} \le \sum\limits_{v=l+1}^{l+k} \frac{1}{q_v} = \log \frac{\log( l + k)}{\log l} - \sum\limits_{\gamma = l}^{l+k-1} (B_{\gamma}  - B_{\gamma + 1}),$

According to (63)

(66)  $B_{\gamma} - B_{\gamma + 1} = \log \log (\gamma + 1)  - \log \log \gamma  - \frac{1}{q_{\gamma + 1}}$.

According to Taylor’s theorem,

(67)  $\log \log(\gamma + 1) = \log \log \gamma + \frac{1}{\gamma \log \gamma} - \frac{1}{2} \frac{1 + \log(\gamma + \vartheta_{\gamma})}{(\gamma + \vartheta_{\gamma})^2 {\log}^2 (\gamma + \vartheta_{\gamma}) }$ 

with a certain $\vartheta_{\gamma}$ where $0 < \vartheta_{\gamma} < 1$. This means

(68) $\sum\limits_1^k \frac{1}{p_K} \le \log \frac{\log(l + k)}{\log l} - \sum\limits_{\gamma = l}^{l+k-1} \left( \frac{1}{\gamma \log \gamma} - \frac{1}{q_{\gamma + 1}} - \frac{1}{2} \frac{1 + \log \gamma}{{\gamma}^2 {\log}^2 \gamma} \right)$ 

Note that according to B. Rosser [4]

(69)  $q_{\gamma + 1} > (\gamma + 1)\log(\gamma + 1)$

is fulfilled, then (68) becomes

(70) $\sum\limits_1^k \frac{1}{p_K} < \log \frac{\log(l+k)}{\log l} - \frac{1}{l \log l} + \frac{1}{(l + k)\log(l+k)} + \frac{1}{2} \sum\limits_l^{l+k-1} \frac{1 + \log \gamma}{{\gamma}^2 {\log}^2 \gamma}$,

because still

(71) $\sum\limits_{\gamma = 1}^{l+k-1} \frac{1 + \log \gamma}{{\gamma}^2 {\log}^2 l} \le \frac{1 + \log l}{l^2 {\log}^2 l} + \int_l^{l+k} \frac{1 + \log x}{x^2 {\log}^2 x}{d}x = \frac{1}{l \log l} \left(1 + \frac{1}{l} + \frac{1}{l \log l} + \frac{1}{l \log l} \right) - \frac{1}{(l+k)\log(l + k)}$ 

is correct, (70) also provides the estimate

(72) $\sum\limits_{1}^{k} \frac{1}{p_K} < \log \frac{\log (l + k)}{\log l} + \frac{1}{2(l+k)\log(l+k)} - \frac{1}{2l\log l}\left(1 - \frac{1}{l} - \frac{1}{l \log l}\right) < \log\left( \frac{\log k}{\log l} + \frac{l}{k \log l} \right) + \frac{1}{2(l+k)\log(l + k)} - \frac{1}{2l\log l}\left( 1 - \frac{1}{l} - \frac{1}{l \log l} \right)$.

From Theorem 1, we can assume that $k \ge 13$; $l \ge 3$.

Let:

(73)  $13 \le k \le l^{7/3} - l$, so $l \ge 4$

then we have

(74)  $\frac{\log(l+k)}{\log l} \le 2.334$; $\sum\limits_1^k \frac{1}{p_K} < \log 2.334 + \frac{1}{2(l+k)\log l} - \frac{1}{2l \log l}\left( 1 - \frac{1}{l} - \frac{1}{l \log l}  \right) < 0.85 + \frac{1}{4^2 \log 4} < 0.9 = 1 - \frac{1}{10}$,

which according to Proposition 2 leads to $g < 10(k-1) +2 < 10k < k^2$. 

Let: 

(75)  $l^{7/3} - l < k \le l^{7/3}$, so $l \ge 4$;

According to (72) it follows that $\log \frac{\log(l + l^{7/3})}{\log l} < \log \left( \frac{7}{3} + \frac{1}{l^{4/3}\log l} \right) < \log \frac{7}{3} + \frac{3}{7l^{4/3}\log l}$ also:

(76) $\sum\limits_1^k \frac{1}{p_K} < \log \frac{7}{3} + \frac{3}{7l^{4/3}\log l} + \frac{3}{7l^{7/3}\times 2\log l} - \frac{1}{2l\log l} \left( 1 - \frac{1}{l} - \frac{1}{l \log l} - \frac{6}{7l^{1/3}} - \frac{3}{7l^{4/3}} \right) < 0.9$,

and again to $g < 10k < k^2$ so that: 

(77) $l^{7/3} < k \le l^{5/2} -l$ and $\log \frac{\log(l+k)}{\log l} \le \log \frac{5}{2} < 0.92$

In this case we see from (72)

(78)  $\sum\limits_1^k \frac{1}{p_K} < 0.92 + \frac{3}{14l^{7/3}\log l} - \frac{1}{2l\log l} \left( 1 - \frac{1}{l} - \frac{1}{l \log l}  \right) = 0.92 - \frac{1}{2l \log l} \left( 1 - \frac{1}{l} - \frac{1}{l \log l} - \frac{3}{7l^{4/3}} \right) < 0.92 - \frac{7}{60l \log l} < 1 - \frac{1}{12.5}$

which according to Proposition 2 immediately

(79)  $g < 12.5k < k^2$

delivers. For

(80)  $\text{max} \{ l^{7/3}; l^{5/2}-1  \} < k < l^{5/2}$

becomes

(81)  $\sum \frac{1}{p_K} < 0.92 + \frac{2}{5l^{3/2}\log l} + \frac{1}{5l^{5/2}\log l} - \frac{1}{2l\log l} \left( 1 - \frac{1}{l} - \frac{1}{l \log l} \right) = 0.92 - \frac{1}{2l\log l} \left( 1 - \frac{1}{l} - \frac{1}{l \log l} - \frac{2}{5l^{3/2}} - \frac{4}{5l^{1/2}} \right) < 0.92 + \frac{0.1809}{2l \log l} < 0.95$

for $k \ge 19$ according to Lemma 3, the inequality $g \le k^2$ fulfilled. For $k \le 18$ is $l^{7/3}< 18$ only fulfilled for $l \le 3$  

Then it follows from (80)

(82)  $12 < \text{max} \{ 9 \sqrt[3]{3}; 9\sqrt{3} - 3 \} < k < 9\sqrt{13} < 16$

In the cases $l=3, k=13, 14, 15$ we can estimate directly: 

(83)  $g < 5k < k^2$

We can assume for the rest of the proof

(84)  $l^{5/2} < k \le l^e$

According to (72)

(85)  $\sum \frac{1}{p_K}$ 

$ < \log \left( e + \frac{1}{ll^{e-1}\log l}  \right) + \frac{1}{5l^{5/2}\log l} - \frac{1}{2l\log l} \left( 1 - \frac{1}{l} - \frac{1}{l \log l} \right)$  $< 1 - \frac{1}{2l \log l}$ $ \left( 1 - \frac{1}{l} - \frac{1}{l \log l} - \frac{2}{el^{e-2}} - \frac{2}{5l^{3/2}} \right)$

For $l \ge 5$ is $\frac{1}{l} + \frac{1}{l \log l} + \frac{2}{el^{e-2}} + \frac{2}{5l^{3/2}} < \frac{1}{5}  + \frac{1}{8} + \frac{2}{2.7 \times 5^{3/2}} + \frac{2}{25 \times \sqrt{5}} < 0.62$ i.e. we have the estimates

(86)  $\sum \frac{1}{p_K} < 1 - \frac{0.38}{2l \log l}$; $g < \frac{l \log l}{0.19} k \le k^2$

because $\frac{\log l}{l} \le \frac{\log 5}{5} < 0.322 < 0.19l^{1/2}$ is fulfilled. For $l = 3,4$ we get from (84) and $p_1 \ge q_{l + 1}$

(87)  $p_1 = 7$ or $11$; $16 \le k \le 19$ or $33 \le k \le 53$.

For $l=3$, it follows:

(88)  $\sum\limits_1^{19} \frac{1}{p_K} \le \frac{1}{7} + \frac{1}{11} + \dots + \frac{1}{79} < 0.8$; $g < 5k < k^2$

For $l=4$, it follows:

(89) $\sum\limits_1^{53} \frac{1}{p_K} \le \frac{1}{11} + \frac{1}{13} + \dots + \frac{1}{269} < 1 - \frac{1}{30}$; $g < 30k < k^2$

This confirms the second theorem.

Theorem 3:  Let $n = p_1 \dots p_k$, $1 < k^{0.6} < p_1 < \dots < p_k$ then $g(p_1 \dots p_k) \le k^2$.

Proof: We write 

(90) $\pi(k^{0.6}) = l$

and know from Theorem 2 that $k \le l^{e}$ the assertion of the above theorem follows.  Therefore we now ask the question: For which $l$ is:

(91)  $l < \pi(l^{0.6e})$

fulfilled? Assume first, with $0.6e = \alpha (1.63 < \alpha < 1.632)$

(92)  $l^{\alpha} \ge e^{100} $

Then, according to B. Rosser [4]:

(93)  $\pi(l^{\alpha}) \ge \frac{l^{\alpha}}{\alpha \log l + 2}$

We get

(94)  $l < \frac{l^{\alpha}}{\alpha \log l + 2} \le \pi(l^{\alpha})$

Because $\alpha l \log l + 2l < l^{\alpha}$, $\frac{\alpha}{a-1} \frac{\log l^{\alpha-1}}{l^{\alpha-1}} + \frac{2}{l^{\alpha - 1}} \le \frac{1.632}{0.63} \times \frac{10}{e^{10}} + \frac{2}{e^{10}} < 1$, it is fulfilled. Assume:

(95)  $17 \le l^{\alpha} < e^{100}$

Then we have, according to B. ROSSER [4]

(96)  $\pi(l^{\alpha}) \ge \frac{l^{\alpha}}{\alpha \log l} > l$; $\alpha \log l < l^{\alpha -1}$

because the function $\frac{\log x}{x}$ for $1 < x$ is positive and at $x = e$ the maximum $\frac{1}{e}$ 

Because the above adjustment is equivalent to:

(97)  $\frac{\alpha}{\alpha - 1} \times \frac{\log l^{\alpha - 1}}{l^{\alpha - 1}} \le \frac{\alpha}{\alpha - 1} \times \frac{1}{e} \le \frac{0.6e}{0.63} \times \frac{1}{e} = \frac{60}{63} < 1$

Is now

(98)  $l^{1.63} < l^{\alpha} < 17$; $l < 6$

then we investigate for which $l \le 5$ according to (91)

(99)  $l < \pi(l^{1.6})$

applies. It is

(100)  $5^{1.6} > 13$; $\pi(13) = 6$

For $l=2,3,4$ we carry out the proof directly with estimation of $\sum\limits_1^{k} \frac{1}{p_K}$ and application of Proposition 2. Because of Theorem 1 we can $k \ge 13$; $l = \pi(k^{0.6}) \ge \pi(\sqrt{13}) \ge \pi(3) = 2$ This proves Theorem 3.

Theorem 4: For all $n = p_1 \dots p_k$, $g(n) \le 2^k = \sum\limits_{d|n} 1$. For $k \ge e^{50}$ is $g(n) < 2^{\sqrt{k}}$.

Proof: For $k=1,2$ the statement is correct. So let $k \ge 3$. Assume that:

(101) $p_1 < \dots < p_i \le (k-i)^{0.6} < p_{i+1} < \dots < p_k$.

From Lemma 4, it follows that:

(102)  $g(n) \le p_1 \dots p_i  g(p_{i+1} \dots p_k) - (p_1 - 1) \dots (p_i - 1) + 1$

From Theorem 3 we get

(103)  $g(n) \le p_1 \dots p_i(k-i)^2$

It is known

(104)  $p_1 \dots p_i < 4^{(k-i)^{0.6}}$

Therefore follows

(105)  $g(n) < 2^{2(k-i)^{0.6}} \times (k-i)^2 \le 2^k$ 

if

(106)  $2^{2(k-i)^{0.6}} \times (k-i)^2 \le 2^{2k^{0.6}} \times k^2 \le 2^k$; $k^2 \le 2^{k^{0.6}(k^{0.4}-2)}$; $2\log k \le k^{0.6} (k^{0.4} - 2) \log 2$; $\frac{\log k^{0.6}}{k^{0.6}}\le 0.3 \times (k^{0.4} - 2) \log 2$

applies. Because $\frac{\log k^{0.6}}{k^{0.6}} \le \frac{1}{e} < 0.368 < 0.3 \times 1.8 \log 2$ is correct, it follows that $k^{0.4} - 2 \ge 1.8$; $k \ge 29$ immediately the claim. For $3 \le k \le 12$ the assertion of the theorem is also fulfilled, namely for $k=4, \dots, 12$ according to Theorem 1, for $k=3$ because of $g(p_1 p_2 p_3) \le 6$. Now $13 \le k \le 28$ provided. We get according to (101)

(107)  $p_i \le 28^{0.6} < 10$

With this we have

(108)  $p_1 \dots p_i \le 2 \times 3 \times 5 \times 7 = 210$; $g(n) < 210k^2$

For $k \ge 18$ is:

(109)  $210k^2 \le 2^k$

Because $\frac{\log 210}{k} + \frac{2 \log k}{k} < \frac{5.35 + 5.8}{18} < \log 2$ is fulfilled. For $13 \le k \le 17$, it follows:

(110) $p_i \le 17^{0.6} < 7$; $p_1 \dots p_i \le 30$; $g(n) < 30k^2 \le 2^k$,

because $\frac{\log 30 + 2 \log k}{k} < \frac{3.41 + 5.14}{13} > \log 2$ applies:

For $k \ge e^{50}$ we write, similar to the proof of Theorem 3:

(111)  $l = \pi(k^{0.48})$; $l < \pi(l^{0.48e})$; $\alpha = 0.48e$ $(1.3 < \alpha < 1.31)$

According to B. Rosser [4]

(112)  $\pi(l^{\alpha}) \ge \frac{l^{\alpha}}{\alpha \log l + 2}$; $\frac{\alpha}{\alpha - 1} \times \frac{\log l^{\alpha - 1}}{l^{\alpha - 1}} + \frac{2}{l^{\alpha - 1}} <  \frac{1.31}{0.3} \times \frac{\log l^{\alpha - 1}}{l^{\alpha - 1}} + \frac{2}{l^{\alpha - 1}}$; $k^{0.48} \ge e^{24}$; $l \ge \pi(e^{24}) \ge \frac{e^{24}}{26}$; $l^{\alpha - 1} > l^{0.3} > \left( \frac{e^{24}}{26} \right)^{0.3} > e^{20\times 0.3} = e^6 > 400$; $\frac{131}{30} \times \frac{6}{400} + \frac{2}{400} < 1$

We therefore have the following result:

(113)  For $k \ge e^{50}$; $k^{0.48}< p_1 < \dots < p_k$, it follows that $g(p_1 \dots p_k) \le k^2$

Let $p_1 < \dots < p_j \le (k-j)^{0.48} < p_{j+1} < \dots < p_k$ so it follows that:

$g \le p_1 \dots p_j \times (k-j)^2 < 2k^{0.48} \times k^2 \le 2^{\sqrt{k}}$ 

Then: $2k^{0.48} \log 2 + 2\log k \le \sqrt{k}\log 2$; $2\log k \le k^{0.48}(k^{0.02}-2) \log 2$; $k^{0.02} \ge e > 2.7$; $2 \log k \le 0.7 \times k^{0.48} \log 2$; $\frac{1}{0.24} \times \frac{\log k^{0.48}}{k^{0.48}} < 0.7 \log 2$; $\frac{1}{0.24} \times \frac{24}{e^{24}} < 0.7 \log 2$ is valid. This proves Theorem 4.

As a simple consequence of the last theorem we get:

(114) For $k \ge 18$, it follows that $n > g^4$

Proof: 

Since $k \ge 18$:

(115)  $n \ge 2 \times 3 \times \dots \times 31 \times 37^{k - 11} > 2^{42}\times 37^{k-11} > 2^{5k-18} \ge 2^{4k} \ge g^4$

If we imagine the divisors $d$ of $n$ arranged according to size, then $2^{k-1}$ this divisor is greater than $\sqrt{n} > g^2$ if $k \ge 18$ is fulfilled. For each divisor $d$ from $n$ with $d > g^2$ is either according to (16):

(116) $0 < \Theta_d - \vartheta_d = \frac{g-1}{d} < \frac{g-1}{g^2} < \frac{1}{g}$

or according to (17) and (18)

(117)  $\Theta_d - \vartheta_d = \frac{g-1}{d} - 1$; $0 < 1 + \Theta_d - \vartheta_d < \frac{g-1}{g^2} < \frac{1}{g}$

The estimates in this work can be improved with greater computational effort, in particular it can be shown that $1 < k^{1/2} < p_1 < \dots < p_k$ also $g < k^{1.7}$ it follows for $k > 659^2$ This bound for k can probably be lowered by further calculations.

 

 

 

Solution to the Depressed Cubic Equation

Theorem 9:  Depressed Cubic Equation

If $x^3 + bx = c$, then:

$$x = \sqrt[3]{\frac{c}{2} + \sqrt{\dfrac{c^2}{4} + \frac{b^3}{27}}} + \sqrt[3]{\frac{c}{2} - \sqrt{\dfrac{c^2}{4} + \frac{b^3}{27}}}$$

Proof:

(1)  $x^3 = -bx + c$

(2)  There exists real numbers $u,v$ such that $x = u + v$

(3)  $(u+v)^3 = u^3 + 3u^2v + 3uv^2 + v^3 = 3uv(u+v) + (u^3 + v^3)$

(4)  Since $b = -3uv$, it follows that $v = \dfrac{-b}{3u}$

(5)  $c = u^3 + v^3 = u^3 + \dfrac{-b^3}{27u^3}$

(6)  It follows that:

$$u^6  - u^3c  + \dfrac{-b^3}{27}= 0$$

(7)  Using the solution for the quadratic equation, we have:

$$u^3 = \frac{c \pm \sqrt{c^2 + \frac{4b^3}{27}}}{2} = \frac{c}{2} \pm \sqrt{\left(\frac{c}{2}\right)^2 + \left(\frac{b}{3}\right)^3}$$

(8)  From the symmetry of the equation, we can assume that:

$$u^3 = \frac{c}{2} + \sqrt{\left(\frac{c}{2}\right)^2 + \left(\frac{b}{3}\right)^3}$$

$$v^3 = c - u^3 = c - \frac{c}{2} - \sqrt{\left(\frac{c}{2}\right)^2 + \left(\frac{b}{3}\right)^3} = \frac{c}{2} - \sqrt{\left(\frac{c}{2}\right)^2 + \left(\frac{b}{3}\right)^3}$$

(9)  $x = u + v = \sqrt[3]{\frac{c}{2} + \sqrt{\left(\frac{c}{2}\right)^2 + \left(\frac{b}{3}\right)^3}} + \sqrt[3]{\frac{c}{2} - \sqrt{\left(\frac{c}{2}\right)^2 + \left(\frac{b}{3}\right)^3}}$

Solution to the Quadratic Equation

Theorem 8:  If $ax^2 + bx + c=0$, then:

$$x = \frac{-b \pm \sqrt{b^2 - 4ac}}{2a}$$

Proof:

(1)  $x^2 + \dfrac{bx}{a} + \dfrac{c}{a} = 0$

(2)  $x^2 + \dfrac{bx}{a} = -\dfrac{c}{a}$

(3)  $x^2 + \dfrac{bx}{a} + \left(\dfrac{b}{2a}\right)^2 = -\dfrac{c}{a} + \left(\dfrac{b}{2a}\right)^2$

(4)  $\left(x + \dfrac{b}{2a}\right)^2 = -\dfrac{c}{a} + \left(\dfrac{b}{2a}\right)^2$

(5)  $x + \dfrac{b}{2a} = \pm \sqrt{-\dfrac{c}{a} + \left(\dfrac{b}{2a}\right)^2}$

(6) $x = -\dfrac{b}{2a} \pm \sqrt{-\dfrac{c}{a} + \left(\dfrac{b}{2a}\right)^2} = \dfrac{-b \pm  \sqrt{b^2 - 4ac}}{2a}$

The Square Root of 2 is irrational

Theorem 7: The Square Root of $2$ cannot be represented by the ratio of two integers

Proof:

(1)  Assume that the squre root of $2$ could be represented by a ratio of two integers with $a$ and $b$ the reduced form.

$$\frac{a}{b} = \sqrt{2}$$ 

(2)  Squaring both sides:

$$a^2 = 2b^2$$

(3)  Since $a$ must be even, there exists $c$ such that $a=2c$ and:

$$a^2 = (2c)^2 = 4c^2 = 2b^2$$

(4)  It follows that $b$ must be even since:

$$2c^2 = b^2$$

(5)  Then there exists $d$ such that $b=2d$ and:

$$\sqrt{2} = \frac{2c}{2d} = \frac{c}{d}$$

(6)  But then we have a contradiction since $a$ and $b$ can be reduced to $c$ and $d$.

Infinitude of Prime Numbers

Theorem 6:  Infinitude of Prime Numbers

There are an infinite number of prime numbers.

Proof:

(1)  Assume that there is a a finite number of primes. 

(2)  Let $P$ be the product of all primes.

(3)  Let $q = P+1$

(4)  By the Fundamental Theorem of Arithmetic, either $q$ is prime or $q$ is a product of primes.

(5)  If $q$ is prime, then $q | (P + 1) - P = 1$ which s impossible.

(6)  If $r$ is a prime that divides $q$, then we have the same problem since $r | (P + 1) - P = 1$

Fundamental Theorem of Arithmetic

Theorem 5:  The Fundamental Theorem of Arithmetic

Every integer greater than $1$ is either prime or can be represented as the unique product of powers of prime numbers.

Proof:

(1)  First, prove existence.  It is true for the base case where $n=2$ since $2$ is a prime.

(2)  Assume that it is true for all $i$ with $i \le n$

(3)  For $n+1$, if $n+1$ is prime, then it is true.  If $n+1$ is not prime, then there exists integers $a,b$ such that $n+1 = ab$ with $a \le n$ and $b \le n$.  Since $a \le n$ and $b \le n$, they can be represented by a prime or a product of primes with $a=p_1p_2\dots{p_n}$ and $b=q_1q_2\dots{q_n}$

(4)  Then $n+1 = ab = p_1p_2\dots{p_n}q_1q_2\dots{q_n}$ which means that $n+1$ can be represented as a product of powers of prime numbers.

(5)  Assume that there is an integer that has two different product of powers of prime numbers.

(6)  Let $y$ be the least integer where this is true so that $y = p_1p_2\dots{p_m} = q_1q_2\dots{q_n}$ with $p_1\dots{p_m}$  and $q_1\dots{q_n}$.

(7)  From Euclid's Generalized Lemma, $p_1$ divides $q_i$ where $1 \le i \le n$.  But, then $\frac{y}{p_1} = p_2\dots{p_m} = \frac{q_1q_2\dots{q_n}}{p_1}$ which is smaller than $n$ and contradicts our assumption in step(6).

Euclid's Lemma

Theorem 4:  Euclid's Lemma

If a prime $p$ divides the product $ab$ of two integers $a$ and $b$, then $p$ divides $a$ or $p$ divides $b$

Proof:

(1)  Assume that $p | ab$ but $p \nmid a$

(2)  From Bezout's Identity, there exists $r,s$ such that $rp + sa = 1$

(3)  Multiply both sides by $b$ to get:  $rpb + sab = b$

(4)  Since $p | ab$, it follows that $p | b$

Corollary 4.1:  Euclid's Generalized Lemma

If a prime $p$ divides $a_1a_2\dots{a_m}$, then $p$ divides $a_i$ where $1 \le i \le m$

Proof:

(1)  Base Case:  The base case is Euclid's Lemma.  If $p | a_1a_2$, then $p | a_1$ or $p | a_2$

(2)  Assume that up to $n$ if $p | a_1a_2\dots{a_n}$, then $p|a_i$ with $1 \le i \le n$

(3)  Let $b = a_1a_2\dots{a_n}$.  

(4)  Inductive Case:  From Euclid's Lemma, if $p | ba_{n+1}$, then $p | b$ or $p|a_{n+1}$.

Bezout's Identity

Theorem 3:  Bezout's Identity

Let $a$ and $b$ be nonzero integers with greatest common divisor $d$.  Then, there exists integers $x$ and $y$ such that $ax + by = d$.

Proof:

(1)  For integers $a,b$ let $S$ be a set that includes all $ax+by$ where $ax + by > 0$

(2)  The set is non-empty since it contains either $a$ or $-a$ where $y=0$ and $x=1$ or $x=-1$

(3)  By the Well-Ordering Principle, $S$ has a minimal element $as + bt$ and let $d = as+bt$

(4)  Using Euclid's Divsion Lemma, there exists $q_1, q_2, r_1, r_2$ such that:

• $a = q_1d + r_1$
• $b = q_2d + r_2$

(5)  It follows that:

• $r_1 = a - q_1d = a - q_1(as + bt) = a(1 - q_1s)  + b(-q_1t)$ which must equal $0$ since $r_1 < d$ but $d$ is the least element in $S$.  The same argument applies to $r_2$ so that $r_2 = 0$

(6)  Then, $d$ divides both $a$ and $b$.

(7)  Let $c$ be any common divisor of $a$ and $b$ such that $a =cu$ and $b = cv$

(8)  $d = as + bt = cus + cvt = c(us + vt)$ so that it follows that $c$ divides $d$ and further that $c \le d$

Euclid's Division Lemma

Theorem 2:  Euclid's Division Lemma

Given two integers $a$ and $b$ with $b \ne 0$, there exist unique integers $q$ and $r$ such that:

• $a = bq+r$
• $0 \le r < |b|$

Note:  Where $|b|$ is the absolute value of $b$.

Proof:

(1)  Case 1:  $a \ge 0$

(2)  Let $S$ be the set of all integers $a - bk$ where $k$ is an integer and $a - bk \ge 0$

(3)  $S$ is non-empty since either $a = a - b\times0 \ge 0$ which is in $S$

(4)  By the Well-Ordering Principle, there exists an integer $q$ such that $a - bq$ is the least element in $S$

(5)  Let $r = a - bq$.  $0 \le r$ by definition of $S$.  Further $r < b$ since if $r \ge b$, then it is not the least element since $r - b = a - bq - b = a - b(q+1) \ge 0$ would be less than $r$ and an element in $S$.

(6)  $r,q$ must be unique.  Assume that there exists $r', q'$ such that $a = qb + r = q'b + r'$  and $|r - r'| > 0$ and $|q - q'| > 0$.  Then, $b > |r - r'| = b|q - q'| > b$ which is impossible.

(7)  Case 2:  $a < 0$  In this case, let $a' = -a$.  It now follows that $a' \ge 0$ and there exists unique $r,q$.  It now follows that $a = -(bq +r) = b(-q) -r$  If $r > 0$, then $a = b(-q+1) + (b-r)$ with $0 < b-r < b$

Well-Ordering Principle

Theorem 1:  Well-Ordering Princple

Every non-empty set of non-negative integers contains a least element

Proof:

(1)  Assume that there exists a non-empty set $S$ of positive integers that does not contain a least element.

(2)  Let $P(n)$ be true if $n$ is an element of $S$

(3)  $P(0)$ is false.  If true, then $0$ would be the least element for $S$

(4)  Assume that for all $i \le n, P(i)$ is false. 

(5)  It follows that $P(n+1)$ is false.  If not, then $n+1$ would be the least element for $S$.

(6)  But, then by the Principle of Mathematical Induction, there is no positive integer in $S$

(7)  This contradicts our assumption in (1) that $S$ is non-empty.  Therefore, we can reject our assumption in step (1).

Note:  This is an example of a proof by contradiction.

Principle of Mathematical Induction

Axiom 1:  Principle of Mathematical Induction

A proof by induction consists of 2 steps:

(1)  Base Case:  Proves that the statement is true for one case independent of all other cases.

(2)  Inductive Case: Proves that if the statement holds for any case $n=k$, then it must also hold for $n=k+1$

The principle can be understood with the analogy of a ladder.  if we can climb on the bottom rung of a ladder and for each rung, we can climb to the next, then it follows that we can climb as high as we like up to the top of the ladder. 

This principle is very important in the establishment of advanced mathematical arguments.

The Prime Numbers

The Ancient Greeks loved to classify numbers.  Numbers that could be represented as the ratio of two whole numbers were rational numbers.  Numbers such as $\sqrt{2}$ which could not were irrational numbers.  A perfect number, such as 6,  is equal to the sum of its proper divisors.  Amicable numbers, such as 220 and 284, are pairs of numbers where each is the sum of the proper divisors of the other.

Without a doubt, the most important of these classifications was the concept of a prime number.  A prime number is any positive integer that has exactly two divisors.  $5$ is a prime number but $8$ is not.  $1$ is not, $0$ is not, and negative numbers are not.  While the definition is clear, one might immediately ask, why should one care.

There are two big reasons why we should care.  If mathematics is the study of patterns, some of the most amazing and surprising patterns relate to prime numbers.  Investigating prime numbers turns out to be a royal path to deep mathematical insights.  For example, one of the most important problems in mathematics today is the Reimann Hypothesis which concerns the relationship between prime numbers and the complex zeta function.  By the way, if anyone solves it, there's a million dollar prize waiting to be claimed.

The other reason to care about primes is that their properties have become fundamental to the very running of global eCommerce.   Prime numbers start out very common and become surprisingly rare as one starts to consider very large numbers.  It turns out that determining whether a number is prime can take a significant computation effort if the prime is large enough.  In fact, one of the great pursuits of spare computation capacity is the search for new primes.  Each time a new largest prime is discovered, it is worthy of a news headline.  For example, here is a news headline from NPR in 2018.

Because there are an infinite number of primes (more about that later) and because it is possible to find primes up to the limits of current computational power, they have become an excellent foundation for security.  Indeed, this is the foundation of public key encryption.  For example, RSA, one of the earliest public key encryptions is based on the difficulty of factoring the product of two large prime numbers.

But let's start smaller.  Let's focus on fundamental patterns.  For me, there are two incredibly surprising facts about primes that can serve as a starting point.  Of course, one or both may not be surprising to you.  First, each positive number is characterized by a unique combination of primes.

If I take any set of primes (for example $2,3,5$) at a specific power (for this example, we'll choose the power of $1$), then there is ONLY one number equal to their product.  In this case, $30$.  This property is called unique factorization.  The natural numbers are characterized by unique factorization.  If there is a prime that divides one but not the other number, they are not equal.  If there is a power of a prime that divides one but not the other,  they are not equal.    From this perspective, they provide an opportunity to simplify reasoning about very large numbers.  If I have two very complicated equations which I want to compare, I can quickly see that they are not equal if a prime divides one but does not the other.  For example, I can say without a doubt for all integer values of $x$ and $y$, the following will never be equal:

$$4^x \ne 7^y$$

I mentioned in a previous post that natural numbers are just one of many types of numbers.  One of the most surprising facts for me is that not all number systems are characterized by unique factorization.  In other words, there are numbers where they are products of different primes and yet they are still equal.  With our intuitions about the concept of number from the whole numbers and the integers, this may seem impossible.  If don't believe me, you can check it out for yourself.  For example, not all quadratic integers are characterized by unique factorization.  Even the great genius Leonhard Euler (pronounced Oiler) was not beyond making a bad assumption about unique factorization.  If you are interested, I provide the details of his mistake here.

Unique factorization is such as an important properties of integers that the theorem that establishes unique factorization is called the Fundamental Theorem of Arithmetic.

In my next blog post, I will walk through a simple proof of this fundamental theorem.

The Natural Numbers

A number, as a concept, is a surprisingly ambiguous term.  There are whole numbers, fractions, negative numbers, real numbers, irrational numbers, imaginary numbers, and transcendental numbers.  It may not be intuitively obvious what they all have in common.  There are also mathematical operations that are not defined and are probably not numbers at all such as $\dfrac{1}{0}$ (see here) or $0^0$ (see here).  The concept of infinity is another difficult to nail down concept.  Is it a number?  It turns out that there are different types of infinity.  For example, the number of counting numbers (1, 2, 3, ...) is less than the number of points in an infinitely divisible line (see here).  I will tackle these more advanced topics later

Historically, the concept of number began with the activities of counting and measuring.  Counting led to the whole numbers which did not include 0 at the very beginning and measuring led to simple fractions (more complicated fractions require a more complicated number system).  

The most important historical breakthroughs which we pretty much take for granted today are:

• Invention of number symbols  (typically, the earliest form of writing that comes after use of tally scratches and tally scratch groupings) (For context, see history of writing and history of ancient numeral systems)
• Discovery of zero (For context, see history of zero)
• Positional Notation which allows all numbers to be represented by a finite set of digits (For context, see here)
• Negative numbers (For context, see history of negative numbers)
• Irrational numbers which showed that not all measurements are ratios of whole numbers (For context, see history of irrational numbers)
• The Decimal System (For context, see here.  Not all societies used Base 10.  The Ancient Babylonians for example used a Sexagesimal System which is Base 60).

In mathematics, the set of positive whole numbers and zero is called the Natural Numbers and is represented by N;.    When combined with the set of negative numbers, it becomes the sets of Integers which is represented by Z. (Why Z, it comes from the German word Zahlen for 'numbers')

The study of the properties of Integers is called number theory and this will be the primary focus of this blog.    

In my view, the most surprising and deepest insight in all of mathematics is that natural numbers, despite their appearances of being the simplest of mathematical objects, contain some of the most challenging and important problems known to mathematics.  

These challenges have led to the development of public key cryptography which today powers the global economy.  Innovations such as block chain, which build on top of the complexity of mathematical problems, will further transform our economic, social, and political institutions that depend on hierarchy and centralized authority.  

One popular definition of Mathematics is "the study of patterns" (see here for an interesting overview).  Many of the most surprising and profound patterns can be found in Number Theory.

A Change In Direction

Starting today, I will update this blog on a regular basis.  I will use this blog as an exploration of the fundamental properties of primes as well as an attempt to generalize ideas.

If the past is any indication, my attempts will usually reflect a misunderstanding of a fundamental or a mistake in one step of my argument.  So, when I make my attempts, I will make sure to provide a thorough explanation of the mistakes that I made.

I will organize the blog posts as an attempt at a book.  So, as the blog proceeds, I will re-edit previous blog posts in the attempt to create a consistent narrative.  So, in theory, a person could start on the first blog post and proceed from there or start on what will become the table of contents and jump from there into any topic of interest.

I will start with very elementary ideas.  This will be a very personal journey.  So, I will proceed from the elementary ideas based on my interests and my attempt to generalize standard results.

I hope that others will find this interesting.  I warn everyone that while I am a serious amateur, I will make mistakes.  These blog posts will be primarily interesting to other amateurs.  For serious math students, I strongly recommend going to the blogs of professional mathematicians such as Terence Tao and Andrew Granville who are two of the most amazing writers and brilliant mathematicians.

Since I am an amateur, I will also make every effort to call out my sources and so that if my argument is unclear, it is possible to go to the source to find a professional explanation.

Most importantly, enjoy.  The journey is the purpose.  :-)

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.