MHB Test whether the integer is a prime

[evinda]

I think we're only talking about the upper bound instead of the actual size of the table.
In the first iteration we will have $m[2 \dots 2^{1}]$, then $m[2 \dots 2^{2}]$, and so on.
Generally we have $m[2 \dots 2^{i}]$, meaning that $2^i+1$ is not in the table. (Thinking)

A ok. So when we have the table $m[2 \dots 2^{i}]$, the table will have $2^i-1$ elements, at the next iteration it will have $2^{i+1}-1$ elements, and so on. Right? (Thinking)

 

[I like Serena]

A ok. So when we have the table $m[2 \dots 2^{i}]$, the table will have $2^i-1$ elements, at the next iteration it will have $2^{i+1}-1$ elements, and so on. Right?

Yep. (Nod)

 

[evinda]

Yep. (Nod)

So when we execute the algorithm and we have at the beginning $r=2$, we create the table $m[2 \dots 2^1]=m[2]$.
Then we get $r=3$ and we create the table $m[3 \dots 2^2]=m[3 \ 4]$.
Then we get $r=4$ and we just have to look at the previous table we created, and so on, Right?

 

[I like Serena]

So when we execute the algorithm and we have at the beginning $r=2$, we create the table $m[2 \dots 2^1]=m[2]$.
Then we get $r=3$ and we create the table $m[3 \dots 2^2]=m[3 \ 4]$.
Then we get $r=4$ and we just have to look at the previous table we created, and so on, Right?

Wouldn't the table still start at 2 in every iteration? (Wondering)

 

[evinda]

Wouldn't the table still start at 2 in every iteration? (Wondering)

Oh yes, right.
So when $r=2$ we create the table $m[2]$, when $r=3$ we create the table $m[2 \ 3 \ 4]$, when $r=4$ we verify with 3 steps using the previous table that it is composite. Then when $r=5$ we get the table $m[2 \ 3 \ 4 \ 5 \ 6 \ 7 \ 8]$.
We check what holds for the numbers $k=6,7,8$ with the last table that we got with $k-1$ steps. Right?
So the number of arithmetic operations done is $\sum_{1 \leq i \leq \lceil \log{(\rho(n))}\rceil} O(i \cdot 2^i)+O(i)= \sum_{1 \leq i \leq \lceil \log{(\rho(n))}\rceil} O(i \cdot 2^i)$.

Right? (Thinking)

 

[I like Serena]

Oh yes, right.
So when $r=2$ we create the table $m[2]$, when $r=3$ we create the table $m[2 \ 3 \ 4]$, when $r=4$ we verify with 3 steps using the previous table that it is composite. Then when $r=5$ we get the table $m[2 \ 3 \ 4 \ 5 \ 6 \ 7 \ 8]$.
We check what holds for the numbers $k=6,7,8$ with the last table that we got with $k-1$ steps. Right?
So the number of arithmetic operations done is $\sum_{1 \leq i \leq \lceil \log{(\rho(n))}\rceil} O(i \cdot 2^i)+O(i)= \sum_{1 \leq i \leq \lceil \log{(\rho(n))}\rceil} O(i \cdot 2^i)$.

Right?

That looks about right yes. (Nod)

 

[evinda]

That looks about right yes. (Nod)

Nice. (Happy) Then we calculate $n^i \mod{r}$, for $i=1,2, \dots, 4 \lceil \log{n}\rceil^2$.
Why is the number of multiplications modulo $r$ $O((\log{n})^2)$ for one $r$ and not $O(\log{i})$?
How do we deduce this? (Thinking)

 

[I like Serena]

Nice. (Happy) Then we calculate $n^i \mod{r}$, for $i=1,2, \dots, 4 \lceil \log{n}\rceil^2$.
Why is the number of multiplications modulo $r$ $O((\log{n})^2)$ for one $r$ and not $O(\log{i})$?
How do we deduce this? (Thinking)

$O(\log{i})$ would be for fast exponentiation for a single $i$, wouldn't it?
But don't we need it for all $i$?
And can't we use the previous result $n^{i-1}$ to find $n^i$? (Wondering)

 

[evinda]

$O(\log{i})$ would be for fast exponentiation for a single $i$, wouldn't it?

Yes, right... (Nod)

But don't we need it for all $i$?
And can't we use the previous result $n^{i-1}$ to find $n^i$? (Wondering)

Yes, so we make $4 \lceil \log{n}\rceil^2-1$ multiplications, right? (Thinking)

And $4 \lceil \log{n}\rceil^2-1 \leq 4 (\log{n}+1)^2-1=O(\log^2{n})$, right?

 

[I like Serena]

Yes, so we make $4 \lceil \log{n}\rceil^2-1$ multiplications, right? (Thinking)

And $4 \lceil \log{n}\rceil^2-1 \leq 4 (\log{n}+1)^2-1=O(\log^2{n})$, right?

Right. (Nod)

 

[evinda]

Then we check how many times the while-loop is executed. There is the following lemma.

View attachment 7628

First of all, how do we get that $\Omega\left(\frac{x}{\log{x}}\right)=\Omega((\log{n})^3 (\log{\log{n}})^2)$ ?

I got that $\frac{x}{\log{x}}=\frac{8 \lceil \log{n}\rceil^3 (\log{\log{n}})^3}{\log{8}+3 \log{(\lceil \log{n}\rceil)+3 \log{(\log{\log{n}})}}}$... But is this in $\Omega((\log{n})^3 (\log{\log{n}})^2)$ ?

Also how do we get that $n^{\frac{x^{\frac{2}{3}}}{3}} <\Pi<n^{x^{\frac{2}{3}}}$ ? (Thinking)

 

[I like Serena]

Then we check how many times the while-loop is executed. There is the following lemma.

First of all, how do we get that $\Omega\left(\frac{x}{\log{x}}\right)=\Omega((\log{n})^3 (\log{\log{n}})^2)$ ?

I got that $\frac{x}{\log{x}}=\frac{8 \lceil \log{n}\rceil^3 (\log{\log{n}})^3}{\log{8}+3 \log{(\lceil \log{n}\rceil)+3 \log{(\log{\log{n}})}}}$... But is this in $\Omega((\log{n})^3 (\log{\log{n}})^2)$ ?

Don't we have $\frac{x}{\log{x}}=\frac{8 \lceil \log{n}\rceil^3 (\log{\log{n}})^3}{\log{8}+3 \log{(\lceil \log{n}\rceil)+3 \log{(\log{\log{n}})}}}
\ge \frac{8 \lceil \log{n}\rceil^3 (\log{\log{n}})^3}{4 \log{(\lceil \log{n}\rceil)}}$ for sufficiently large $n$? (Wondering)

Also how do we get that $n^{\frac{x^{\frac{2}{3}}}{3}} <\Pi<n^{x^{\frac{2}{3}}}$ ? (Thinking)

Let $X=\lfloor x^{1/3}\rfloor$.
Then:
$$\mathit\Pi = \prod_{i=1}^X (n^i-1) < \prod_{i=1}^X n^X = n^{X^2}$$
and:
$$\mathit\Pi = \prod_{i=1}^X (n^i-1) > \prod_{i=1}^X n^{i-1} = n^{\sum (i-1)} = n^{\frac 12 X(X-1)} > n^{\frac 13 X^2}$$
Isn't it? (Wondering)

 

[evinda]

Don't we have $\frac{x}{\log{x}}=\frac{8 \lceil \log{n}\rceil^3 (\log{\log{n}})^3}{\log{8}+3 \log{(\lceil \log{n}\rceil)+3 \log{(\log{\log{n}})}}}
\ge \frac{8 \lceil \log{n}\rceil^3 (\log{\log{n}})^3}{4 \log{(\lceil \log{n}\rceil)}}$ for sufficiently large $n$? (Wondering)

This holds when $\lceil \log{n}\rceil \geq \frac{(\log{\log{n}})^3}{8}$, right? If so, how can we easily prove this? Do we use induction?

Then we have the following.

$$\frac{x}{\log{x}} \geq \frac{8 \lceil \log{n}\rceil^3 (\log{\log{n}})^3}{4 \log{(\lceil \log{n}\rceil)}}\geq \frac{8 \lceil \log{n}\rceil^3 (\log{\log{n}})^3}{4 \log{(\log{n}+1)}} (\star)$$

We have that $4 \log{(\log{n}+1)} \leq 4 \log{(2 \log{n})}=4(\log{2}+\log{(\log{n})})=4(1+\log{(\log{n})}) \leq 4(2 \log{(\log{n})})=8 \log{(\log{n})}$.

So we get that $(\star) \geq \frac{8 \lceil \log{n}\rceil^3 (\log{\log{n}})^3 }{8 \log{(\log{n})}}=\lceil \log{n}\rceil^3 (\log{\log{n}})^2$.

Right? Or have I done something wrong? (Thinking)

Let $X=\lfloor x^{1/3}\rfloor$.
Then:
$$\mathit\Pi = \prod_{i=1}^X (n^i-1) < \prod_{i=1}^X n^X = n^{X^2}$$

I see... (Nod)

$$\mathit\Pi = \prod_{i=1}^X (n^i-1) > \prod_{i=1}^X n^{i-1} = n^{\sum (i-1)} = n^{\frac 12 X(X-1)} > n^{\frac 13 X^2}$$
Isn't it? (Wondering)

Why does it hold that $\prod_{i=1}^X (n^i-1) > \prod_{i=1}^X n^{i-1}$ ?

The last inequality holds for $X>3$, right?

 

[I like Serena]

This holds when $\lceil \log{n}\rceil \geq \frac{(\log{\log{n}})^3}{8}$, right? If so, how can we easily prove this? Do we use induction?

Can't we use that $\log n > \log\log n > \log\log\log n > 8$ for sufficiently large $n$? (Wondering)

Then we have the following.

$$\frac{x}{\log{x}} \geq \frac{8 \lceil \log{n}\rceil^3 (\log{\log{n}})^3}{4 \log{(\lceil \log{n}\rceil)}}\geq \frac{8 \lceil \log{n}\rceil^3 (\log{\log{n}})^3}{4 \log{(\log{n}+1)}} (\star)$$

We have that $4 \log{(\log{n}+1)} \leq 4 \log{(2 \log{n})}=4(\log{2}+\log{(\log{n})})=4(1+\log{(\log{n})}) \leq 4(2 \log{(\log{n})})=8 \log{(\log{n})}$.

So we get that $(\star) \geq \frac{8 \lceil \log{n}\rceil^3 (\log{\log{n}})^3 }{8 \log{(\log{n})}}=\lceil \log{n}\rceil^3 (\log{\log{n}})^2$.

Right? Or have I done something wrong?

All correct. (Nod)

Why does it hold that $\prod_{i=1}^X (n^i-1) > \prod_{i=1}^X n^{i-1}$ ?

The last inequality holds for $X>3$, right?

Doesn't it hold for any $X$ as long as $n \ge 2$?
That is:
$$n^i -1 = n^{i-1}(n-n^{-(i-1)})>n^{i-1}$$
(Thinking)

 

[evinda]

Can't we use that $\log n > \log\log n > \log\log\log n > 8$ for sufficiently large $n$? (Wondering)

So is it as follows?

$$\log{8}+3 \log{(\lceil \log{n}\rceil)}+3 \log{(\log{\log{n}})} \leq \log{(\log{n})}+3 \log{(\log{n}+1)}+3 \log{(\log{n})} \leq 4 \log{(\log{n})}+3 \log{(2 \log{n})}=7\log{(\log{n})}+3 \log{2}\leq 7 \log{(\log{n})}+3 \log{(\log{n})}=10 \log{\log{n}}$$

Thus, we have $\frac{x}{\log{x}}\geq \frac{8 \lceil \log{n}\rceil^3 (\log{\log{n}})^3}{10 \log{\log{n}}}=\frac{8}{10} \lceil \log{n}\rceil^3 (\log{\log{n}})^2= \Omega(\lceil \log{n}\rceil^3 (\log{\log{n}})^2)$.

Right?

Doesn't it hold for any $X$ as long as $n \ge 2$?
That is:
$$n^i -1 = n^{i-1}(n-n^{-(i-1)})>n^{i-1}$$
(Thinking)

This holds only when $n-n^{-(i-1)}>1 \Rightarrow n^i-n^{i-1}-1>0$, right? (Thinking)

 

[I like Serena]

So is it as follows?

$$\log{8}+3 \log{(\lceil \log{n}\rceil)}+3 \log{(\log{\log{n}})} \leq \log{(\log{n})}+3 \log{(\log{n}+1)}+3 \log{(\log{n})} \leq 4 \log{(\log{n})}+3 \log{(2 \log{n})}=7\log{(\log{n})}+3 \log{2}\leq 7 \log{(\log{n})}+3 \log{(\log{n})}=10 \log{\log{n}}$$

Thus, we have $\frac{x}{\log{x}}\geq \frac{8 \lceil \log{n}\rceil^3 (\log{\log{n}})^3}{10 \log{\log{n}}}=\frac{8}{10} \lceil \log{n}\rceil^3 (\log{\log{n}})^2= \Omega(\lceil \log{n}\rceil^3 (\log{\log{n}})^2)$.

Right?

Yep. (Nod)

This holds only when $n-n^{-(i-1)}>1 \Rightarrow n^i-n^{i-1}-1>0$, right?

Yes.
And $-(i-1)\le 0$, so with $n\ge 2$ we have that $n^{-(i-1)} \le 1$. (Thinking)

 

[evinda]

Yes.
And $-(i-1)\le 0$, so with $n\ge 2$ we have that $n^{-(i-1)} \le 1$. (Thinking)

So we have that $n^i-1>n^{i-1}$ only if $n-n^{-(i-1)}>1$.

And taking into consideration that $n \geq 2$ and $-(i-1) \leq 0$, we get that $n^{-(i-1)} \leq 1 \Rightarrow -n^{-(i-1)}\geq -1 \Rightarrow n-n^{-(i-1)} \geq n-1>1$, right?Do you maybe have an idea how we get that $k=O\left( \frac{\log{(\Pi)}}{\log{\log{(\Pi)}}}\right)$ ?

 

[I like Serena]

So we have that $n^i-1>n^{i-1}$ only if $n-n^{-(i-1)}>1$.

And taking into consideration that $n \geq 2$ and $-(i-1) \leq 0$, we get that $n^{-(i-1)} \leq 1 \Rightarrow -n^{-(i-1)}\geq -1 \Rightarrow n-n^{-(i-1)} \geq n-1>1$, right?

Just nitpicking, but shouldn't that last inequality be $\geq n-1\ge 1$? (Wondering)

Do you maybe have an idea how we get that $k=O\left( \frac{\log{(\Pi)}}{\log{\log{(\Pi)}}}\right)$ ?

What is the argument following lemma 3.6.8? (Wondering)

 

[evinda]

Just nitpicking, but shouldn't that last inequality be $\geq n-1\ge 1$? (Wondering)

Yes, right...

$$\mathit\Pi = \prod_{i=1}^X (n^i-1) > \prod_{i=1}^X n^{i-1} = n^{\sum (i-1)} = n^{\frac 12 X(X-1)} > n^{\frac 13 X^2}$$

Doesn't $n^{\frac 12 X(X-1)} > n^{\frac 13 X^2}$ only hold when $\frac{1}{2}X^2-\frac{1}{2}X>\frac{1}{3}X^2 \Rightarrow X>3$ ?

Also having shown that $\mathit\Pi > n^{\frac{1}{3}X^2}=n^{\frac{1}{3} \lfloor x^{\frac{1}{3}}\rfloor^2}$ we haven't shown yet that $\mathit\Pi > n^{\frac{1}{3}x^{\frac{2}{3}}}$, do we?

What is the argument following lemma 3.6.8? (Wondering)

View attachment 7630

For $x>1$, with $\pi(x)$ we denote the number of primes $p \leq x$.

 

[I like Serena]

Doesn't $n^{\frac 12 X(X-1)} > n^{\frac 13 X^2}$ only hold when $\frac{1}{2}X^2-\frac{1}{2}X>\frac{1}{3}X^2 \Rightarrow X>3$ ?

Also having shown that $\mathit\Pi > n^{\frac{1}{3}X^2}=n^{\frac{1}{3} \lfloor x^{\frac{1}{3}}\rfloor^2}$ we haven't shown yet that $\mathit\Pi > n^{\frac{1}{3}x^{\frac{2}{3}}}$, do we?

Indeed. (Thinking)

For $x>1$, with $\pi(x)$ we denote the number of primes $p \leq x$.

That leads up to $\mathit\Pi > (2k/e)^k$.
Taking logs brings us basically to $k\log k <c\cdot N$, where $N=\log\mathit\Pi$ and $c$ is some constant.
From there we are supposed to get to $k<c\cdot \frac{N}{\log N}=c\cdot \frac{\log\mathit\Pi}{\log\log\mathit\Pi}$.
It seems that is explained right after your fragment with 'an indirect argument'.
What comes after? (Thinking)

 

[evinda]

Indeed. (Thinking)

How else could we get the lower bound? (Thinking)

That leads up to $\mathit\Pi > (2k/e)^k$.
Taking logs brings us basically to $k\log k <c\cdot N$, where $N=\log\mathit\Pi$ and $c$ is some constant.
From there we are supposed to get to $k<c\cdot \frac{N}{\log N}=c\cdot \frac{\log\mathit\Pi}{\log\log\mathit\Pi}$.
It seems that is explained right after your fragment with 'an indirect argument'.
What comes after? (Thinking)

View attachment 7631

 

[I like Serena]

Also having shown that $\mathit\Pi > n^{\frac{1}{3}X^2}=n^{\frac{1}{3} \lfloor x^{\frac{1}{3}}\rfloor^2}$ we haven't shown yet that $\mathit\Pi > n^{\frac{1}{3}x^{\frac{2}{3}}}$, do we?

How else could we get the lower bound?

We have to tweak it a little.
Something like:
$$
\mathit\Pi > n^{\frac{1}{2}X(X-1)}>n^{\frac{1}{2}(X-1)^2}
=n^{\frac{1}{2}(\lfloor x^{1/3}\rfloor-1)^2}
>n^{\frac{1}{2}(x^{1/3}-2)^2}
>n^{\frac{1}{3}x^{2/3}}
$$
for sufficiently large $x$. (Thinking)

Do you maybe have an idea how we get that $k=O\left( \frac{\log{(\Pi)}}{\log{\log{(\Pi)}}}\right)$ ?

And indeed, the argument is a long one, but it seems to be all there, doesn't it? (Wondering)

 

[evinda]

We have to tweak it a little.
Something like:
$$
\mathit\Pi > n^{\frac{1}{2}X(X-1)}>n^{\frac{1}{2}(X-1)^2}
=n^{\frac{1}{2}(\lfloor x^{1/3}\rfloor-1)^2}
>n^{\frac{1}{2}(x^{1/3}-2)^2}
>n^{\frac{1}{3}x^{2/3}}
$$
for sufficiently large $x$. (Thinking)

The last inequality holds when $\frac{1}{2}(x^{\frac{1}{3}}-2)^2>\frac{1}{3}x^{\frac{2}{3}} \Rightarrow x^{\frac{2}{3}}-4x^{\frac{1}{3}}+4>\frac{2}{3}x^{\frac{2}{3}} \Rightarrow x^{\frac{2}{3}}-12x^{\frac{1}{3}}+12 > 0$.

So does $x$ have to be such that $x^{\frac{1}{3}}>\frac{12+ \sqrt{3 \cdot 2^5}}{2}$? (Thinking)

And indeed, the argument is a long one, but it seems to be all there, doesn't it? (Wondering)

But in our case we don't have that $k=\pi(\mathit\Pi )$, do we? (Thinking)

 

[I like Serena]

The last inequality holds when $\frac{1}{2}(x^{\frac{1}{3}}-2)^2>\frac{1}{3}x^{\frac{2}{3}} \Rightarrow x^{\frac{2}{3}}-4x^{\frac{1}{3}}+4>\frac{2}{3}x^{\frac{2}{3}} \Rightarrow x^{\frac{2}{3}}-12x^{\frac{1}{3}}+12 > 0$.

So does $x$ have to be such that $x^{\frac{1}{3}}>\frac{12+ \sqrt{3 \cdot 2^5}}{2}$? (Thinking)

Yep.

But in our case we don't have that $k=\pi(\mathit\Pi )$, do we? (Thinking)

Indeed. That's why the argument is similar. (Thinking)

 

[evinda]

Indeed. That's why the argument is similar. (Thinking)

Don't we have that $k \leq \pi(\mathit \Pi)$ and so $k=O{\left( \frac{\mathit \Pi}{\log{ \mathit \Pi}}\right)}$ ? Or am I wrong? (Thinking)

 

[evinda]

Taking logs brings us basically to $k\log k <c\cdot N$, where $N=\log\mathit\Pi$ and $c$ is some constant.
From there we are supposed to get to $k<c\cdot \frac{N}{\log N}=c\cdot \frac{\log\mathit\Pi}{\log\log\mathit\Pi}$.
(Thinking)

It seems that $O\left(\frac{\log{N}}{\log{\log{N}}}\right)$ is a known upper bound for the number of distince prime divisors of $N$, but I haven't understood how we can show this... (Thinking)

 

[I like Serena]

Isn't the first step where it says in the proof in http://mathhelpboards.com/number-theory-27/test-whether-integer-prime-22804-post103344.html#post103344 that $\mathit\Pi > 2^k\cdot k! > (2k/e)^k$ by lemma 3.6.8? (Wondering)

Yes. Do we use this somehow to conclude that $k=O{\left( \frac{\log{\mathit\Pi}}{\log{\log{\mathit\Pi}}}\right)}$ ? (Thinking)

Yes. Can't the next step be similar to what we have in post http://mathhelpboards.com/number-theory-27/test-whether-integer-prime-22804-post103372.html#post103372?
That is, we're taking logarithms,
$$\ln\mathit\Pi > k\cdot (\ln k + \ln 2 - 1)\tag{3.6.19a}$$
(Thinking)

So then we suppose that $k \geq \frac{\ln{\mathit\Pi}}{\ln{\ln{\mathit\Pi}}}$, in order to get a contradiction.

Using the relation $\ln{\mathit\Pi}>k(\ln{k}+\ln{2}-1)$ we get that

$$\ln{\mathit\Pi}> \frac{\ln{\mathit\Pi}}{\ln{\ln{\mathit\Pi}}}\left( \ln{\ln{\mathit\Pi}}-\ln{\ln{\ln{\Pi}}}+\ln{2}-1\right) \\ \Rightarrow \ln{\mathit\Pi} \ln{\ln{\mathit\Pi}}> \ln{\mathit\Pi} \ln{\ln{\mathit\Pi}}-\ln{\mathit\Pi} \ln{\ln{\ln{\mathit\Pi}}}+ \ln{2} \ln{\mathit\Pi}-\ln{\mathit\Pi} \\ \Rightarrow \ln{\mathit\Pi} (\ln{(\ln{\ln{\mathit\Pi}})}+1-\ln{2})>0$$

Do we now look at the function $f(x)= \ln{x}(\ln{\ln{\ln{x}}}+1-\ln{2})$ ?

If so, accrding to Wolfram, it has one solution and its derivate has no solution. What can we get from this? (Thinking)

Isn't that expression true for sufficiently large $x$? And the function positive as well?
Then it won't lead to a contradiction. (Worried)In the argument given in http://mathhelpboards.com/number-theory-27/test-whether-integer-prime-22804-post103374.html#post103374, we assumed that $k \ge \frac{2N}{\ln N}$. Note the extra factor $2$.

So let's first define $M=\ln\mathit\Pi$, and let's assume that $k\ge \frac{2M}{\ln M}$ for a contradiction.
Then we get:
$$M>k\cdot(\ln k + \ln 2 - 1) \tag{3.6.19a}$$
and it follows, when $\ln M > 0$, that:
$$M>\frac{2M}{\ln M}\cdot\left(\ln\left(\frac{2M}{\ln M}\right) + \ln 2 - 1\right) \\
\Rightarrow\quad\frac 12\ln M > \ln\left(\frac{2M}{\ln M}\right)+ \ln 2 - 1 \\
\Rightarrow\quad\frac 12\ln M > \ln M - \ln\ln M+ 2\ln 2 - 1 \\
\Rightarrow\quad(1-\frac 12)\ln M < \ln\ln M-2\ln 2 + 1$$
so by obvious transformations,
$$(1-\frac 12)\ln M < \ln\ln M-2\ln 2 + 1\tag{3.6.20a}$$

Now we can look at the function $f: x \mapsto (1-\frac 12)\ln x - \ln\ln x + 2\ln 2 - 1$, which is defined for $x > 1$, can't we? (Wondering)

 

[evinda]

In the argument given in http://mathhelpboards.com/number-theory-27/test-whether-integer-prime-22804-post103374.html#post103374, we assumed that $k \ge \frac{2N}{\ln N}$. Note the extra factor $2$.

So let's first define $M=\ln\mathit\Pi$, and let's assume that $k\ge \frac{2M}{\ln M}$ for a contradiction.
Then we get:
$$M>k\cdot(\ln k + \ln 2 - 1) \tag{3.6.19a}$$
and it follows, when $\ln M > 0$, that:
$$M>\frac{2M}{\ln M}\cdot\left(\ln\left(\frac{2M}{\ln M}\right) + \ln 2 - 1\right) \\
\Rightarrow\quad\frac 12\ln M > \ln\left(\frac{2M}{\ln M}\right)+ \ln 2 - 1 \\
\Rightarrow\quad\frac 12\ln M > \ln M - \ln\ln M+ 2\ln 2 - 1 \\
\Rightarrow\quad(1-\frac 12)\ln M < \ln\ln M-2\ln 2 + 1$$
so by obvious transformations,
$$(1-\frac 12)\ln M < \ln\ln M-2\ln 2 + 1\tag{3.6.20a}$$

Now we can look at the function $f: x \mapsto (1-\frac 12)\ln x - \ln\ln x + 2\ln 2 - 1$, which is defined for $x > 1$, can't we? (Wondering)

We have that $f(x)>0$ for $x>1$.

Then $f'(x)=\frac{\ln{x}-2}{2 x \ln{x}}$.

$f'(x)=0 \Rightarrow x=e^2$.

For $x> e^2$ we have that $f'(x)>0$ and so $f$ is increasing.

For $1<x<e^2$ we have that $f'(x)<0$ and so $f$ is decreasing.

So we get that for any $x>1$, $f(x)>f(e^2)=\ln{2} \Rightarrow \frac{1}{2} \ln{x}-\ln\ln x+ 2\ln 2-1>\ln{2}>0$, contradicting the relation $(3.6.20a)$.

Is everything right? (Thinking)

 

[I like Serena]

We have that $f(x)>0$ for $x>1$.

We don't have this yet. It's what we want to prove don't we? (Wondering)

Then $f'(x)=\frac{\ln{x}-2}{2 x \ln{x}}$.

$f'(x)=0 \Rightarrow x=e^2$.

For $x> e^2$ we have that $f'(x)>0$ and so $f$ is increasing.

For $1<x<e^2$ we have that $f'(x)<0$ and so $f$ is decreasing.

So we get that for any $x>1$, $f(x)>f(e^2)=\ln{2} \Rightarrow \frac{1}{2} \ln{x}-\ln\ln x+ 2\ln 2-1>\ln{2}>0$, contradicting the relation $(3.6.20a)$.

Yep. (Nod)

(Although shouldn't it be $f(x)\ge f(e^2)$?)

 

[evinda]

We don't have this yet. It's what we want to prove don't we? (Wondering)

Yes, right... (Nod)

Yep. (Nod)

(Although shouldn't it be $f(x)\ge f(e^2)$?)

Yes, I see... (Nod)

View attachment 7642

How do we see that $q$ must divide $ord_r{(n)}$ ? (Thinking)