Consecutive Quadratic Residues And Quadratic Nonresidue Modulo $p$

Let $p>3$ be a prime, and let $(\frac{\cdot}p)$ be the Legendre symbol. Let $b\in\mathbb Z$ and $\varepsilon\in\{\pm 1\}$. We mainly prove that $$\left|\left\{N_p(a,b):\ 1<a<p\ \text{and}\ \left(\frac ap\right)=\varepsilon\right\}\right|=\frac{3-(\frac{-1}p)}2,$$ where $N_p(a,b)$ is the number of positive integers $x<p/2$ with $\{x^2+b\}_p>\{ax^2+b\}_p$, and $\{m\}_p$ with $m\in\mathbb{Z}$ is the least nonnegative residue of $m$ modulo $p$.

We say that a set $S$ is additively decomposed into two sets $A$ and $B$ if $S = \{a+b : a\in A, \ b \in B\}$. A. S\'ark\"ozy has recently conjectured that the set $Q$ of quadratic residues modulo a prime $p$ does not have nontrivial decompositions. Although various partial results towards this conjecture have been obtained, it is still open. Here we obtain a nontrivial upper bound on the number of such decompositions.

For positive integers $q$, Dirichlet's theorem states that there are infinitely many primes in each reduced residue class modulo $q$. A stronger form of the theorem states that the primes are equidistributed among the $\varphi(q)$ reduced residue classes modulo $q$. This paper considers patterns of sequences of consecutive primes $(p_n, p_{n+1}, \ldots, p_{n+k})$ modulo $q$. Numerical evidence suggests a preference for certain prime patterns. For example, computed frequencies...

Let $p$ be a prime and $p_1,\ldots, p_r$ be distinct prime divisors of $p-1$. We prove that the smallest positive integer $n$ which is a simultaneous $p_1,\ldots,p_r$-power nonresidue modulo $p$ satisfies $$ n<p^{1/4 - c_r+o(1)}\quad(p\to\infty) $$ for some positive $c_r$ satisfying $c_r\ge e^{-(1+o(1))r} \; (r\to \infty).$

Let $q\geq 1$ be any integer and let $ \epsilon \in [\frac{1}{11}, \frac{1}{2})$ be a given real number. In this short note, we prove that for all primes $p$ satisfying $$ p\equiv 1\pmod{q}, \quad \log\log p > \frac{\log 6.83}{\frac{1}{2}-\epsilon} \mbox{ and } \frac{\phi(p-1)}{p-1} \leq \frac{1}{2} - \epsilon, $$ there exists a quadratic non-residue $g$ which is not a primitive root modulo $p$ such that $gcd\left(g, \frac{p-1}{q}\right) = 1$.

While the sequence of primes is very well distributed in the reduced residue classes (mod $q$), the distribution of pairs of consecutive primes among the permissible $\phi(q)^2$ pairs of reduced residue classes (mod $q$) is surprisingly erratic. This paper proposes a conjectural explanation for this phenomenon, based on the Hardy-Littlewood conjectures. The conjectures are then compared to numerical data, and the observed fit is very good.

We study the quadratic residue problem known as an NP complete problem by way of the prime number and show that a nondeterministic polynomial process does not belong to the class P because of a random distribution of solutions for the quadratic residue problem.

We investigate the linear complexities of the periodic 0-1 infinite sequences in which the periods are the sequence of the parities of the spacings between quadratic residues modulo a prime p, and the sequence of the parities of the spacings between primitive roots modulo p, respectively. In either case, the Berlekamp-Massey algorithm running on MAPLE computer algebra software shows very good to perfect linear complexities.

This is a survey article on the Hardy-Littlewood conjecture about primes in quadratic progressions. We recount the history and quote some results approximating this hitherto unresolved conjecture.

Let $p$ be an odd prime number. In this article, we study the number of quadratic residues and non-residues modulo $p$ which are multiples of $2$ or $3$ or $4$ and lying in the interval $[1, p-1]$, by applying the Dirichlet's class number formula for the imaginary quadratic field $\mathbb{Q}(\sqrt{-p})$.