Return to Answer

We have by inclusion-exclusion and Bombieri-Vinogradov theorem, we have

Lemma 1

Let $0<N<1/2$. Let $B(x)$ be the set of primes $p\leq x$ in the residue class $5$ mod $8$ and there is an odd prime number $1<q\leq (\log x)^N$ which divides $p-1$, and $b(x)$ be the cardinality of $B(x)$. Then $$ b(x)=\frac{\textrm{Li}(x) }{\phi(8)}+O\left(\frac{\textrm{Li}(x) }{\log\log x}\right).$$

Proof of Lemma 1

Denote by $P(q)$ the largest prime factor of $q$. If we have $0<N<1/2$, then for any $M>0$, we have $T:=(\log x)^{N (\log x)^N}\ll \sqrt x (\log x)^{-M}$. So, the values of $q$ are within the range of $q$ provided by Bombieri-Vinogradov. By inclusion-exclusion and Mertens' estimate, we have for any $K>0$,

$$\begin{align*} b(x)&=\textrm{Li}(x) \left(-\sum_{\substack{{1<q\leq T, q \textrm{ is odd}} \\ {P(q)\leq (\log x)^N}}} \frac{\mu(q)}{\phi(8q)}\right)+O\left(x(\log x)^{-K}\right)\\ &=\frac{\textrm{Li}(x)}{\phi(8)} \left( 1-\prod_{\substack{{q\leq (\log x)^N}\\{q \textrm{ is odd prime}}}}\left(1-\frac1{\phi(q)} \right)\right)+O\left(x(\log x)^{-K}\right)\\ &=\frac{\textrm{Li}(x)}{\phi(8)} + O\left(\frac{\textrm{Li}(x) }{\log\log x}\right). \end{align*}$$ The sledgehammer for this problem is a result by Erdos-Murty (or by Parpalardi)

Theorem 1

There exists $\alpha, \delta >0$ such that $$ \mathrm{ord}_p(a)\geq \sqrt p \exp((\log p)^{\delta}) $$ for all but $O(x/(\log x)^{1+\alpha})$ primes $p\leq x$.

The theorem is stated with a fixed $a$, but by modifying Erdos & Murty's proof, we can relax $a$ up to a fixed power of $\log x$. For the main problem, we have the result by combining the above theorem with Lemma 1. In Lemma 1, we take $N=\min(\alpha/2,1/2)$. By counting the exceptional primes, we obtain

Theorem

Let $\alpha, \delta >0$ be the numbers in Theorem 1. Let $A$ be the set of primes $p\leq x$ in the residue class $5$ mod $8$ such that there is an odd prime number $q\leq (\log x)^N$ which divides $p-1$ and $$M_p\geq \mathrm{ord}_q(p)\geq \sqrt p \exp((\log p)^{\delta})$$ Then $$ |A|=\frac{\textrm{Li}(x)}{\phi(8)}+O\left(\frac{\textrm{Li}(x) }{\log\log x}\right). $$

We have by inclusion-exclusion and Bombieri-Vinogradov theorem, we have

Lemma 1

Let $0<N<1/2$. Let $B(x)$ be the set of primes $p\leq x$ in the residue class $5$ mod $8$ and there is an odd prime number $1<q\leq (\log x)^N$ which divides $p-1$, and $b(x)$ be the cardinality of $B(x)$. Then $$ b(x)=\frac{\textrm{Li}(x) }{\phi(8)}+O\left(\frac{\textrm{Li}(x) }{\log\log x}\right).$$

Proof of Lemma 1

Denote by $P(q)$ the largest prime factor of $q$. If we have $0<N<1/2$, then for any $M>0$, we have $T:=(\log x)^{N (\log x)^N}\ll \sqrt x (\log x)^{-M}$. So, the values of $q$ are within the range of $q$ provided by Bombieri-Vinogradov. By inclusion-exclusion and Mertens' estimate, we have for any $K>0$,

$$\begin{align*} b(x)&=\textrm{Li}(x) \left(-\sum_{\substack{{1<q\leq T, q \textrm{ is odd}} \\ {P(q)\leq (\log x)^N}}} \frac{\mu(q)}{\phi(8q)}\right)+O\left(x(\log x)^{-K}\right)\\ &=\frac{\textrm{Li}(x)}{\phi(8)} \left( 1-\prod_{\substack{{q\leq (\log x)^N}\\{q \textrm{ is odd prime}}}}\left(1-\frac1{\phi(q)} \right)\right)+O\left(x(\log x)^{-K}\right)\\ &=\frac{\textrm{Li}(x)}{\phi(8)} + O\left(\frac{\textrm{Li}(x) }{\log\log x}\right). \end{align*}$$ The sledgehammer for this problem is a result by Erdos-Murty (or by Parpalardi)

Theorem 1

There exists $\alpha, \delta >0$ such that $$ \mathrm{ord}_p(a)\geq \sqrt p \exp((\log p)^{\delta}) $$ for all but $O(x/(\log x)^{1+\alpha})$ primes $p\leq x$.

The theorem is stated with a fixed $a$, but by modifying Erdos & Murty's proof, we can relax $a$ up to a fixed power of $\log x$. For the main problem, we have the result by combining the above theorem with Lemma 1. In Lemma 1, we take $N=\min(\alpha/2,1/2)$. By counting the exceptional primes, we obtain

Theorem

Let $\alpha, \delta >0$ be the numbers in Theorem 1. Let $A$ be the set of primes $p\leq x$ in the residue class $5$ mod $8$ such that there is an odd prime number $q\leq (\log x)^N$ which divides $p-1$ and $$M_p\geq \mathrm{ord}_p(q)\geq \sqrt p \exp((\log p)^{\delta})$$ Then $$ |A|=\frac{\textrm{Li}(x)}{\phi(8)}+O\left(\frac{\textrm{Li}(x) }{\log\log x}\right). $$

We have by inclusion-exclusion, Bombieri-Vinogradov theorem, and Halberstam's result on the number of prime divisors of $p-1$, we have

Lemma 1

Let $T=\exp(\sqrt{\log\log x})$. Let $B(x)$ be the set of primes $p\leq x$ in the residue class $5$ mod $8$ and there is an odd prime number $1<q\leq (\log x)^N$ divides $p-1$, and $b(x)$ be the cardinality of $B(x)$. Then for any $N,K>0$, there is $c>0$ depending on $N, K$ such that \begin{align*} b(x)&=\textrm{Li}(x) \left(-\sum_{\substack{{1<q\leq (\log x)^{NT}, q \textrm{ is odd}} \\ {w(q)<T}}} \frac{\mu(q)}{\phi(8q)}\right)+O\left(x(\log x)^{-K}\right)\\ &=\frac{\textrm{Li}(x) }{\phi(8)}+O\left(\textrm{Li}(x) \exp(-c\sqrt{\log\log x})\right)\end{align*}

The sledgehammer for this problem is a result by Erdos-Murty (or by Parpalardi)

Theorem 1

There exists $\alpha, \delta >0$ such that $$ \mathrm{ord}_p(a)\geq \sqrt p \exp((\log p)^{\delta}) $$ for all but $O(x/(\log x)^{1+\alpha})$ primes $p\leq x$.

For the main problem, we have the result by combining the above theorem with Lemma 1. In Lemma 1, we take $N=\alpha/2$.

Theorem

Let $\alpha, \delta >0$ be the numbers in Theorem 1. Let $A$ be the set of primes $p\leq x$ in the residue class $5$ mod $8$ such that there is an odd number $1<q\leq (\log x)^{\alpha/2}$ which divides $p-1$ and $$M_p\geq \mathrm{ord}_q(p)\geq \sqrt p \exp((\log p)^{\delta})$$ Then there is $c>0$ such that $$ |A|=\frac{\textrm{Li}(x)}{\phi(8)}+O\left(\textrm{Li}(x)\exp(-c\sqrt{\log\log x} )\right) $$

We have by inclusion-exclusion and Bombieri-Vinogradov theorem, we have

Lemma 1

Let $0<N<1/2$. Let $B(x)$ be the set of primes $p\leq x$ in the residue class $5$ mod $8$ and there is an odd prime number $1<q\leq (\log x)^N$ which divides $p-1$, and $b(x)$ be the cardinality of $B(x)$. Then $$ b(x)=\frac{\textrm{Li}(x) }{\phi(8)}+O\left(\frac{\textrm{Li}(x) }{\log\log x}\right).$$

Proof of Lemma 1

Denote by $P(q)$ the largest prime factor of $q$. If we have $0<N<1/2$, then for any $M>0$, we have $T:=(\log x)^{N (\log x)^N}\ll \sqrt x (\log x)^{-M}$. So, the values of $q$ are within the range of $q$ provided by Bombieri-Vinogradov. By inclusion-exclusion and Mertens' estimate, we have for any $K>0$,

$$\begin{align*} b(x)&=\textrm{Li}(x) \left(-\sum_{\substack{{1<q\leq T, q \textrm{ is odd}} \\ {P(q)\leq (\log x)^N}}} \frac{\mu(q)}{\phi(8q)}\right)+O\left(x(\log x)^{-K}\right)\\ &=\frac{\textrm{Li}(x)}{\phi(8)} \left( 1-\prod_{\substack{{q\leq (\log x)^N}\\{q \textrm{ is odd prime}}}}\left(1-\frac1{\phi(q)} \right)\right)+O\left(x(\log x)^{-K}\right)\\ &=\frac{\textrm{Li}(x)}{\phi(8)} + O\left(\frac{\textrm{Li}(x) }{\log\log x}\right). \end{align*}$$ The sledgehammer for this problem is a result by Erdos-Murty (or by Parpalardi)

Theorem 1

There exists $\alpha, \delta >0$ such that $$ \mathrm{ord}_p(a)\geq \sqrt p \exp((\log p)^{\delta}) $$ for all but $O(x/(\log x)^{1+\alpha})$ primes $p\leq x$.

The theorem is stated with a fixed $a$, but by modifying Erdos & Murty's proof, we can relax $a$ up to a fixed power of $\log x$. For the main problem, we have the result by combining the above theorem with Lemma 1. In Lemma 1, we take $N=\min(\alpha/2,1/2)$. By counting the exceptional primes, we obtain

Theorem

Let $\alpha, \delta >0$ be the numbers in Theorem 1. Let $A$ be the set of primes $p\leq x$ in the residue class $5$ mod $8$ such that there is an odd prime number $q\leq (\log x)^N$ which divides $p-1$ and $$M_p\geq \mathrm{ord}_q(p)\geq \sqrt p \exp((\log p)^{\delta})$$ Then $$ |A|=\frac{\textrm{Li}(x)}{\phi(8)}+O\left(\frac{\textrm{Li}(x) }{\log\log x}\right). $$

We have by inclusion-exclusion, Bombieri-Vinogradov theorem, and Halberstam's result on the number of prime divisors of $p-1$, we have

Lemma 1

Let $B(x)$ be the set of primes $p\leq x$ in the residue class $5$ mod $8$ and there is an odd prime number $1<q\leq (\log x)^N$ divides $p-1$, and $b(x)$ be the cardinality of $B(x)$. Then for any $N,K>0$, there is $c>0$ depending on $N, K$ such that \begin{align*} b(x)&=\textrm{Li}(x) \left(-\sum_{\substack{{1<q\leq (\log x)^N, q \textrm{ is odd}} \\ {w(q)<\exp(\sqrt{\log\log x})}}} \frac{\mu(q)}{\phi(8q)}\right)+O\left(x(\log x)^{-K}\right)\\ &=\frac{\textrm{Li}(x) }{\phi(8)}+O\left(\textrm{Li}(x) \exp(-c\sqrt{\log\log x})\right)\end{align*}

The sledgehammer for this problem is a result by Erdos-Murty (or by Parpalardi)

Theorem 1

There exists $\alpha, \delta >0$ such that $$ \mathrm{ord}_p(a)\geq \sqrt p \exp((\log p)^{\delta}) $$ for all but $O(x/(\log x)^{1+\alpha})$ primes $p\leq x$.

For the main problem, we have the result by combining the above theorem with Lemma 1. In Lemma 1, we take $N=\alpha/2$.

Theorem

Let $\alpha, \delta >0$ be the numbers in Theorem 1. Let $A$ be the set of primes $p\leq x$ in the residue class $5$ mod $8$ such that there is an odd number $1<q\leq (\log x)^{\alpha/2}$ which divides $p-1$ and $$M_p\geq \mathrm{ord}_q(p)\geq \sqrt p \exp((\log p)^{\delta})$$ Then there is $c>0$ such that $$ |A|=\frac{\textrm{Li}(x)}{\phi(8)}+O\left(\textrm{Li}(x)\exp(-c\sqrt{\log\log x} )\right) $$

We have by inclusion-exclusion, Bombieri-Vinogradov theorem, and Halberstam's result on the number of prime divisors of $p-1$, we have

Lemma 1

Let $T=\exp(\sqrt{\log\log x})$. Let $B(x)$ be the set of primes $p\leq x$ in the residue class $5$ mod $8$ and there is an odd prime number $1<q\leq (\log x)^N$ divides $p-1$, and $b(x)$ be the cardinality of $B(x)$. Then for any $N,K>0$, there is $c>0$ depending on $N, K$ such that \begin{align*} b(x)&=\textrm{Li}(x) \left(-\sum_{\substack{{1<q\leq (\log x)^{NT}, q \textrm{ is odd}} \\ {w(q)<T}}} \frac{\mu(q)}{\phi(8q)}\right)+O\left(x(\log x)^{-K}\right)\\ &=\frac{\textrm{Li}(x) }{\phi(8)}+O\left(\textrm{Li}(x) \exp(-c\sqrt{\log\log x})\right)\end{align*}

The sledgehammer for this problem is a result by Erdos-Murty (or by Parpalardi)

Theorem 1

There exists $\alpha, \delta >0$ such that $$ \mathrm{ord}_p(a)\geq \sqrt p \exp((\log p)^{\delta}) $$ for all but $O(x/(\log x)^{1+\alpha})$ primes $p\leq x$.

For the main problem, we have the result by combining the above theorem with Lemma 1. In Lemma 1, we take $N=\alpha/2$.

Theorem

Let $\alpha, \delta >0$ be the numbers in Theorem 1. Let $A$ be the set of primes $p\leq x$ in the residue class $5$ mod $8$ such that there is an odd number $1<q\leq (\log x)^{\alpha/2}$ which divides $p-1$ and $$M_p\geq \mathrm{ord}_q(p)\geq \sqrt p \exp((\log p)^{\delta})$$ Then there is $c>0$ such that $$ |A|=\frac{\textrm{Li}(x)}{\phi(8)}+O\left(\textrm{Li}(x)\exp(-c\sqrt{\log\log x} )\right) $$