Patterns of quadratic residues and nonresidues for infinitely many primes

If S is a nonempty, finite subset of the positive integers, we address the question of when the elements of S consist of various mixtures of quadratic residues and nonresidues for infinitely many primes. We are concerned in particular with the problem of characterizing those subsets of integers that consist entirely of either (1) quadratic residues or (2) quadratic nonresidues for such a set of primes. We solve problem (1) and we show that problem (2) is equivalent to a purely combinatorial problem concerning families of subsets of a finite set. For sets S of (essentially) small cardinality, we solve problem (2). Related results and some associated enumerative combinatorics are also discussed.     

The distribution of quadratic residues and nonresidues in arithmetic progressions

We prove some results concerning the distribution of quadratic residues and nonresidues in arithmetic progressions in the setting \( {{\mathbb{F}}_p}={{\mathbb{Z}} \left/ {{p\mathbb{Z}}} \right.} \) , where p is a large prime.     

Consecutive residues and nonresidues of polynomials

The author examines the distribution of common residues (mod p) of any polynomialsf ₁(x) andf ₂(x) and the distribution of consecutive residues and nonresidues of any degree.Translated from Matematicheskie Zametki, Vol. 7, No. 1, pp. 97–107, January, 1970.     

On sums and products of quadratic residues

The paper deals with some special topics in connection with sums and products of quadratic residues. Some attention is devoted to primitive roots as a useful tool for these problems. Numerical results obtained by aid of a computer will also be presented.     

On consecutive quadratic non-residues: a conjecture of Issai Schur

Issai Schur once asked if it was possible to determine a bound, preferably using elementary methods, such that for all prime numbers p greater than the bound, the greatest number of consecutive quadratic non-residues modulo p is always less than p^1/2. This paper uses elementary methods to prove that 13 is the only prime number for which the greatest number of consecutive quadratic non-residues modulo p exceeds p^1/2.     

On the first occurrence of certain patterns of quadratic residues and non-residues

Effective upper bounds are obtained for the first occurrence of certain mixed patterns of quadratic residues and non-residues using the character sum estimates of D. A. Burgess and a proof of a conjecture of E. Lehmer.     

Cubic residues and binary quadratic forms

Let p>3 be a prime, u,v,d∈Z, gcd(u,v)=1, p?u²−dv² and , where is the Legendre symbol. In the paper we mainly determine the value of by expressing p in terms of appropriate binary quadratic forms. As applications, for we obtain a general criterion for and a criterion for εd to be a cubic residue of p, where εd is the fundamental unit of the quadratic field . We also give a general criterion for , where {Un} is the Lucas sequence defined by U₀=0, U₁=1 and Un+1=PUn−QUn−1 (n?1). Furthermore, we establish a general result to illustrate the connections between cubic congruences and binary quadratic forms.     

Quartic residues and binary quadratic forms

Let be a prime, m∈Z and . In this paper we obtain a general criterion for m to be a quartic residue in terms of appropriate binary quadratic forms. Let d>1 be a squarefree integer such that , where is the Legendre symbol, and let ε_d be the fundamental unit of the quadratic field . Since 1942 many mathematicians tried to characterize those primes p so that ε_d is a quadratic or quartic residue . In this paper we will completely solve these open problems by determining the value of , where p is an odd prime, and . As an application we also obtain a general criterion for , where {u_n(a,b)} is the Lucas sequence defined by and .     

Simple arguments on consecutive power residues

By some extremely simple arguments, we point out the following:

(i)

If n is the least positive kth power non-residue modulo a positive integer m, then the greatest number of consecutive kth power residues mod m is smaller than m/n.

(ii)

Let OK be the ring of algebraic integers in a quadratic field with d∈{−1,−2,−3,−7,−11}. Then, for any irreducible π∈OK and positive integer k not relatively prime to , there exists a kth power non-residue ω∈OK modulo π such that .

     

On the quadratic character of quadratic units

Let be a prime. Let a,b∈Z with p?a(a²+b²). In the paper we mainly determine by assuming p=c²+d² or p=Ax²+2Bxy+Cy² with AC−B²=a²+b². As an application we obtain simple criteria for εD to be a quadratic residue , where D>1 is a squarefree integer such that D is a quadratic residue of p, εD is the fundamental unit of the quadratic field with negative norm. We also establish the congruences for and obtain a general criterion for p|U(p−1)/4, where {Un} is the Lucas sequence defined by U₀=0, U₁=1 and Un+1=bUn+k²Un−1(n?1).     

On long runs of heads and tails II

In a string ofn independent coin tosses we consider the difference between the lengths of the longest blocks of consecutive heads resp. tails. A complete characterization of the a.s. limit properties of this quantity is proved.     

Diophantine equations with products of consecutive values of a quadratic polynomial

Let a, b, c, d be given nonnegative integers with a,d?1. Using Chebyshev?s inequalities for the function π(x) and some results concerning arithmetic progressions of prime numbers, we study the Diophantine equation

     

New pseudorandom sequences constructed by quadratic residues and Lehmer numbers

Let be an odd prime. Define

where is the multiplicative inverse of modulo such that . This paper shows that the sequence is a ``good" pseudorandom sequence, by using the properties of exponential sums, character sums, Kloosterman sums and mean value theorems of Dirichlet -functions.

     

On quadratic congruences

It is proved that under appropriate assumptions, the solutions f of quadratic congruences Q(f) ≡ 0 (mod n), n ≤ x, with (f|n) = ±1, are distributed asymptotically equally as x → ∞. Bibliography: 5 titles. Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 357, 2008, pp. 195–200.     

On quadratic forms

The present paper is related to the Jordan—von Neumann characterization of inner product spaces, to the Halperin problem concerning quadratic forms, to some results of the present author on quadratic and sesquilinear forms and to recently obtained results of C. T. Ng and of J. Vukman.Dedicated to Professor Otto Haupt with best wishes on his 100th birthday.