Questions tagged [quadratic-residues]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
11 votes
2 answers
512 views

Jacobi symbols for two-square sums of primes

Given a prime $p\equiv 1\pmod 4$, Fermat's two-squares theorem discovered by Girard states that there exists two integers $A,B$ such that $p=A^2+B^2$. For all primes up to $10^7$ the integers $A$ and $...
Roland Bacher's user avatar
8 votes
4 answers
841 views

A cubic equation, and integers of the form $a^2+32b^2$

I am trying to determine whether there are any integers $x,y,z$ such that $$ 1+2 x+x^2 y+4 y^2+2 z^2 = 0. \quad\quad\quad (1) $$ It is clear that $x$ is odd. We can consider this equation as quadratic ...
Bogdan Grechuk's user avatar
0 votes
1 answer
118 views

On a summation in "Artin's conjecture for primitive roots" by Heath-Brown

This is a question on the paper: D. R. Heath-Brown. Artin's conjecture for primitive roots. Quarterly J. Math. 37 (1): 27–38, 1986. At the beginning of the proof of his main theorem on page 35, Heath-...
David R's user avatar
2 votes
2 answers
257 views

Expressions for binomial residue sum $\sum_{k=0}^n {n \choose k} x^k \left( \frac{k}{q} \right)$

I'm interested in the sum: $$\sum_{k=0}^n {n \choose k} x^k \left( \frac{k}{q} \right)$$ where $q$ is a prime number. This is just the binomial expansion with an extra weight on quadratic residues ...
mtheorylord's user avatar
1 vote
0 answers
85 views

Functions that take quadratic residues to non quadratic residues

Let $p$ be prime and $Q$ be the set of integers $x$ mod $p$ so that $x^2-1$ is a quadratic residue. Let $Q^c$ be the complement of $Q$. If we don't consider $x = 1$ then these two sets have the same ...
mtheorylord's user avatar
2 votes
0 answers
125 views

Distribution of square roots (mod m) on small intervals (with respect to m)

Fix a large positive integer $m$. Let $A$ be small positive number typically $\sim m^{1/3}$. Suppose $S(A, m)$ be set of solutions (normalized by dividing by $m$) to the quadratic congruences $x^2 = a ...
Melanka's user avatar
  • 577
0 votes
0 answers
113 views

Quadratic residue problem involving prime divisors of a polynomial

Let $n$ be a square-free natural number, and let $f\in\mathbb{Z}[x]$ be monic and irreducible of degree $\geq2$. I am trying to determine whether there always exists a prime $p$, $p\nmid n$, ...
Jack's user avatar
  • 1
2 votes
1 answer
194 views

Mod n, are all higher powers also lower powers?

Since there are only finitely many residues mod $n$, there is some function $H(n) \le n$ such that for all integers $n>1$, $r$, and $e>H(n)$, if $r$ is an $e$-th power mod $n$ then there is some ...
Charles's user avatar
  • 8,984
-1 votes
1 answer
173 views

Set of all primes $p$ that split in $\mathbb{Q}\left(\sqrt{-k}\right)$

Let $k$ be a squarefree positive integer. We know that a prime $p$ splits in $K=\mathbb{Q}(\sqrt{-k})$ if and only if $-k$ is a quadratic residue mod $p$. My question is: can we explicitly determine ...
user491084's user avatar
3 votes
1 answer
170 views

Largest subset of quadratic residues with no pair of elements differing by 1

In $\mathbb{F_p}$, $p$ prime what is the larget subset $S$ of quadratic residues with no pair of elements differing by 1? In this related question Seva gives an example: "...assuming $p\equiv\...
Ivan Meir's user avatar
  • 4,792
2 votes
1 answer
513 views

Quadratic non-residue problem

For a positive integer $n$, let $a(n)$ the smallest number $k>0$ such that $-n$ is not a quadratic residue modulo $k$. Using CRT, we can prove that all values of $a(n)$ are prime powers, and every ...
uvdose's user avatar
  • 593
5 votes
0 answers
502 views

Two conjectures for primes $p\equiv 1\pmod 8$

Motivated by my paper Quadratic residues and quartic residues modulo primes [Int. J. Number Theory 16 (2020), 1833-1858], here I pose two new conjectures for primes $p\equiv1\pmod8$ based on my ...
Zhi-Wei Sun's user avatar
  • 14.5k
1 vote
0 answers
83 views

How to describe the automorphisms of $\mathbb{Q}(\theta)$ that fix $\mathbb{Q}(\sqrt{-m})$

Suppose $m > 0$ is a square free integer and $m \equiv 1 $mod $4$. Then the $K = \mathbb{Q}(\sqrt{-m})$ is a subfield of $L = \mathbb{Q}(\theta)$, where $\theta$ is a primitive $4m$-th root of ...
matt stokes's user avatar
1 vote
1 answer
140 views

Sum of an arithmetic sequence involving Euler factors

I am trying to find an asymptotic formula for the following sum as $T \to \infty$. $$ \sum_{t = 1}^{T} \prod_{\substack{p \; \textrm{prime} \\ p | t}} \rho(p) \frac{1 - \frac{1}{p^2}}{1 - \frac{\rho(p)...
Melanka's user avatar
  • 577
0 votes
0 answers
97 views

Primes in residue classes [duplicate]

For which sets of residue classes are there easy elementary proofs that there are infinitely many primes in them, which don’t require the machinery of proofs of Dirichlet’s theorem? Example: it’s ...
Joe Shipman's user avatar
1 vote
0 answers
87 views

Evaluate $\det[[\lfloor\frac{aj-(a+1)k}n\rfloor]_q]_{1\le j,k\le n}$ and $\det[[\lceil\frac{(a+1)j-ak}n\rceil]_q]_{1\le j,k\le n}$

The $q$-analogue of an integer $m$ is defined by $[m]_q=(1-q^m)/(1-q)$. Note that $\lim_{q\to1}[m]_q=m$. I have formulated the following conjecture on determinants involving the floor function and the ...
Zhi-Wei Sun's user avatar
  • 14.5k
11 votes
0 answers
421 views

effective and unconditional upper bound for the smallest quadratic residue

Let $p$ be a prime number, and let $r=r(p)$ be the smallest prime number with $(r/p)=1$. The classical result of Linnik-Vinogradov (based on Burgess) implies that $r\ll_\epsilon p^{1/4+\epsilon}$, but ...
Yuri Bilu's user avatar
  • 1,130
4 votes
1 answer
227 views

Counting squares modulo $p$ that are also prime in an interval

What would be the best lower bound for the number of squares modulo $p$ in an interval $[1,N]$ with $N<p$ that are prime? Via the Burgess bound, I can find a lower bound for the number of squares ...
pali's user avatar
  • 41
3 votes
1 answer
406 views

Does each prime $p>541$ have a quadratic residue $x^4+y^4<p$?

For any prime $p>5$, one of the numbers $$1^2+1=2,\ \ 2^2+1=5,\ \ 3^2+1=10=2\times5$$ is a quadratic residue modulo $p$. In 2014 I conjectured that each prime $p$ has a primitive root $g<p$ of ...
Zhi-Wei Sun's user avatar
  • 14.5k
3 votes
1 answer
222 views

Pythagorean triples and quadratic residues modulo primes

QUESTION. Are my following conjectures true? How to prove them? Conjecture 1. For each prime $p>100$, there are $a,b,c\in\{1,\ldots,p-1\}$ such that $$\left(\frac ap\right)=\left(\frac bp\right)=\...
Zhi-Wei Sun's user avatar
  • 14.5k
4 votes
1 answer
252 views

Dominating sets in subtournaments of the Paley tournament

For a tournament $T$, let $\mathrm{dom}(T)$ be the order of a smallest dominating set in $T$. Let $q$ be a prime power congruent to 3 mod 4 and let $T_q$ be the Paley tournament on $q$ vertices. Is ...
Louis D's user avatar
  • 1,666
12 votes
1 answer
738 views

On sums of quadratic residues

Let $p>3$ be a prime. We set $R=\{x\in\mathbb{Z}: (x/p)=1\}$, where $(\cdot/p)$ is the Legendre symbol. When $p\equiv3\pmod4$, by class formulae of imaginary quadratic fields $\mathbb{Q}(\sqrt{-p})$...
user avatar
4 votes
1 answer
218 views

Distribution of quadratic residues in an interval

For a prime (or prime power) $p$ and some absolute constant $C$ (say $C$ = 100), consider the set $A$ of all $1 \leq a \leq p/C$ such that $1 \leq a^2 \leq p/C$ modulo $p$. Is it known that $|A| = \...
Lior Gishboliner's user avatar
8 votes
1 answer
782 views

Is it possible to find a (nonsquare) integer which is a quadratic residues modulo a given infinite list of primes?

I'm wondering if it's possible, given a prime p and an infinite list of primes $q_1$, $q_2$, ... to find an integer d which (1) is not a square mod p, but (2) is a square mod $q_i$ for all i. Always, ...
Joshua Holden's user avatar
16 votes
0 answers
388 views

Quadratic non-residues in elliptic divisibility sequences

Let $E: y^2 = x^3 + ax + b$ be an elliptic curve over $\mathbb{Q}$ with $a,b \in \mathbb{Z}$. Recall that any rational point $P = (x,y)$ can be written uniquely as $P = (u/d^2, v/d^3)$ with $u,v,d \in ...
Daniel Loughran's user avatar
9 votes
3 answers
636 views

Does the expression $x^4 +y^4$ take on all values in $\mathbb{Z}/p\mathbb{Z}$?

As the title asks: does there exist $N$ such that, for any prime $p$ larger than $N$, the expression $x^4 +y^4$ takes on all values in $\mathbb{Z}/p\mathbb{Z}$? I have been thinking about this ...
Junsukim's user avatar
  • 141
2 votes
0 answers
81 views

quadratic residues and cubic polynomials [closed]

I'm really not sure about this, but I've heard somewhere that for any prime $p$, $|\sum_{x=0}^{p-1} (\frac{ax^3 +bx^2 +cx +d}{p} ) |\le \sqrt{2p}$ holds. Does anyone know a proof for this inequality ...
Junsukim's user avatar
  • 141
2 votes
0 answers
119 views

On the set $\{n>0:\ n\ \text{is a quadratic nonresidue modulo the}\ n\text{th prime}\}$

Let $S$ denote the set of positive integers $n$ with $n$ a quadratic nonresidue modulo the $n$th prime $p_n$. The first 20 elements of $S$ are $$2,\, 3,\, 6,\, 7,\, 8,\, 10,\, 11,\, 13,\, 15,\, 18,\, ...
Zhi-Wei Sun's user avatar
  • 14.5k
4 votes
0 answers
163 views

Primitive roots modulo primes related to Fibonacci numbers or Lucas numbers

The Fibonacci numbers $F_0,F_1,F_2,\ldots$ and the Lucas numbers $L_0,L_1,L_2,\ldots$ are given by $$F_0=0,\ F_1=1,\ \text{and}\ F_{n+1}=F_n+F_{n-1}\ (n=1,2,3,\ldots)$$ and $$L_0=2,\ L_1=1,\ \text{...
Zhi-Wei Sun's user avatar
  • 14.5k
5 votes
1 answer
197 views

applications of finding least quadratic nonresidue mod $p$?

I saw some papers from famous mathematicians (assuming GRH or without it) which are devoted to finding bound for least quadratic nonresidues modulo prime number $p$. My question is that why it is so ...
asad's user avatar
  • 841
9 votes
1 answer
962 views

A conjecture on primitive tenth roots of unity

QUESTION. How to solve my following conjecture involving primitive tenth roots of unity? Conjecture. Let $\zeta$ be any primitive tenth root of unity. Then $$\prod_{k=1}^{(p-1)/2}(\zeta-e^{2\pi ik^2/...
Zhi-Wei Sun's user avatar
  • 14.5k
4 votes
0 answers
232 views

On the values of $\prod_{k=1}^{(p-1)/2}(e^{2\pi i/12}-e^{2\pi i k^2/p})$ for primes $p>3$

In a recent preprint, I investigated $$S_p(x):=\prod_{k=1}^{(p-1)/2}(x-e^{2\pi ik^2/p}),$$ where $p$ is an odd prime and $x$ is a root of unity. Motivated by Question 337879 and Question 338325, ...
Zhi-Wei Sun's user avatar
  • 14.5k
4 votes
2 answers
678 views

On the product $\prod_{k=1}^{(p-1)/2}(x-e^{2\pi i k^2/p})$ with $x$ a root of unity

Let $p$ be an odd prime. Dirichlet's class number formula for quadratic fields essentially determines the value of the product $\prod_{k=1}^{(p-1)/2}(1-e^{2\pi ik^2/p})$. I think it is interesting to ...
Zhi-Wei Sun's user avatar
  • 14.5k
9 votes
1 answer
445 views

A conjectural formula for the class number of the field $\mathbb Q(\sqrt{-p})$ with $p\equiv3\pmod8$

Question. Is my following conjecture new? How to prove it? Conjecture. Let $p>3$ be a prime with $p\equiv3\pmod 8$, and let $h(-p)$ denote the class number of the imaginary quadratic field $\...
Zhi-Wei Sun's user avatar
  • 14.5k
6 votes
1 answer
360 views

Is $|\{(j,k):\ 1\le j<k\le\frac{p-1}2:\ \&\ (j^{16}\ \text{mod}\ p)>(k^{16}\ \text{mod}\ p)\}|$ even for each prime $p\equiv1\pmod {16}$?

In my paper http://arxiv.org/abs/1809.07766, I determined the parity of $$\left|\left\{(j,k):\ 1\le j<k\le\frac{p-1}2\ \&\ (j^2\ \text{mod}\ p)>(k^2\ \text{mod}\ p)\right\}\right|$$ for any ...
Zhi-Wei Sun's user avatar
  • 14.5k
1 vote
0 answers
446 views

Legendre Symbol of a Very, Very Large Value

I'm trying to use FLINT (Fast Library for Number Theory) to calculate the Legendre Symbol of the following: $$\left(\frac{n! + 1}{p}\right)$$ In my case, $p$ is a positive, odd prime (specifically $...
Jacob G.'s user avatar
  • 119
0 votes
1 answer
213 views

Shifting quadratic residues

Let $p\equiv 3\pmod 4$ and $G$ be the set of nonzero quadratic residues modulo $p$ (so $G=(p-1)/2$). For $1\leq a\leq p-1$, let $G_a=\{(a+g)\pmod p\mid g\in G\}$. What is the size of $G_0\cap G_a$? I ...
doe's user avatar
  • 77
6 votes
0 answers
202 views

Primes $p\in(n,2n)$ with $(\frac{-n}p)=-1$

Bertrand's postulate proved by Chebyshev states that for any $x>1$ there is a prime $p$ in the interval $(x,2x)$. In 2012 I considered some refinements of this by imposing additional requirement ...
Zhi-Wei Sun's user avatar
  • 14.5k
5 votes
0 answers
190 views

On the determinants $\det\left[(i\pm j)\left(\frac{i\pm j}p\right)\right]_{1\le i,j\le(p-1)/2}$

Let $p$ be an odd prime and define $$D_p^+:=\det\left[(i+j)\left(\frac{i+j}p\right)\right]_{1\le i,j\le(p-1)/2}$$ and $$D_p^{-}:=\det\left[(i-j)\left(\frac{i-j}p\right)\right]_{1\le i,j\le(p-1)/2},$$ ...
Zhi-Wei Sun's user avatar
  • 14.5k
1 vote
0 answers
146 views

On $\det\left[\frac1{i^2-ij+j^2}\right]_{1\le i,j\le p-1}$ and $\det\left[\frac1{i^2-ij+j^2}\right]_{1\le i,j\le (p-1)/2}$

QUESTION. Is my following conjecture true? If true, how to prove it? Conjecture. Let $p$ be a prime with $p\equiv5\pmod 6$, and define the matrices $A_p$ and $B_p$ by $$A_p:=\left[\frac1{i^2-ij+j^2}\...
Zhi-Wei Sun's user avatar
  • 14.5k
7 votes
2 answers
927 views

A new formula for the class number of the quadratic field $\mathbb Q(\sqrt{(-1)^{(p-1)/2}p})$?

I have the following conjecture involving a possible new formula for the class number of the quadratic field $\mathbb Q(\sqrt{(-1)^{(p-1)/2}p})$ with $p$ an odd prime. Conjecture. Let $p$ be an odd ...
Zhi-Wei Sun's user avatar
  • 14.5k
3 votes
0 answers
119 views

Does $(p-1)^2$ divide $\det[(\frac{i^2+cij+dj^2}p)]_{0\le i,j\le p-1}$ when $(\frac dp)=-1$?

Let $p$ be an odd prime. As in my paper, for $c,d\in\mathbb Z$ let us define $$[c,d]_p:=\det\left[\left(\frac{i^2+cij+dj^2}p\right)\right]_{0\le i,j\le p-1},$$ where $(\frac{\cdot}p)$ is the Legendre ...
Zhi-Wei Sun's user avatar
  • 14.5k
2 votes
1 answer
212 views

On the determinant $\det[(\frac{i^2+dj^2}p)]_{0\le i,j\le(p-1)/2}$ with $(\frac dp)=-1$

Let $p$ be an odd prime. For $d\in\mathbb Z$ we define $$T(d,p):=\det\left[\left(\frac{i^2+dj^2}p\right)\right]_{0\le i,j\le(p-1)/2},$$ where $(\frac{\cdot}p)$ is the Legendre symbol. By (1.17) of my ...
Zhi-Wei Sun's user avatar
  • 14.5k
8 votes
1 answer
353 views

Is the permanent of the matrix $[(\frac{i+j}{2n+1})]_{0\le i,j\le n}$ always positive?

Recall that the permanent of an $n\times n$ matrix $A=[a_{i,j}]_{1\le i,j\le n}$ is defined by $$\operatorname{per}A=\sum_{\sigma\in S_n}\prod_{i=1}^n a_{i,\sigma(i)}.$$ In 2004, R. Chapman [Acta ...
Zhi-Wei Sun's user avatar
  • 14.5k
4 votes
1 answer
473 views

A series of conjectures on $\sum_{x=0}^{(p-1)/2}(\frac{x^5+cx^3+dx}p)$ (III)

As in Question 319254, for an odd prime $p$ and integers $c,d$ we define $$S_p(c,d):=\sum_{x=0}^{(p-1)/2}\left(\frac{x^5+cx^3+dx}p\right),$$ where $(\frac{\cdot}p)$ is the Legendre symbol. In my ...
Zhi-Wei Sun's user avatar
  • 14.5k
1 vote
0 answers
117 views

A series of conjectures on $\sum_{x=0}^{(p-1)/2}(\frac{x^5+cx^3+dx}p)$ (II)

As in Question 319254, for an odd prime $p$ and integers $c,d$ we let $$S_p(c,d):=\sum_{x=0}^{(p-1)/2}\left(\frac{x^5+cx^3+dx}p\right).$$ If $p\equiv1\pmod4$, then we obviously have \begin{align}&\...
Zhi-Wei Sun's user avatar
  • 14.5k
1 vote
0 answers
169 views

A series of conjectures on $\sum_{x=0}^{(p-1)/2}(\frac{x^5+cx^3+dx}p)$ (I)

Let $p$ be an odd prime. Here I introduce the sum $$S_p(c,d):=\sum_{x=0}^{(p-1)/2}\left(\frac{x^5+cx^3+dx}p\right)$$ with $c,d\in\mathbb Z$, where $(\frac{\cdot}p)$ is the Legendre symbol. I have a ...
Zhi-Wei Sun's user avatar
  • 14.5k
0 votes
2 answers
281 views

Permutations of squares and finite fields

Let $S_n$ be the symmetric group of all permutations of $\{1,\ldots,n\}$, and let $$S(n)=\bigg\{\sum_{k=1}^nk^2\pi(k)^2:\ \pi\in S_n\}.$$ Motivated by Question 316142 of mine, here I ask the following ...
Zhi-Wei Sun's user avatar
  • 14.5k
2 votes
1 answer
228 views

Does $\det[\lfloor(i^2+j^2)/p\rfloor]_{1\le i,j\le(p-1)/2}$ vanish for each prime $p>7$ with $p\equiv3\pmod4$?

Let $\lfloor x\rfloor$ be the floor function. QUESTION: Does the determinant $$D_p=\det\left[\left\lfloor\frac{i^2+j^2}p\right\rfloor\right]_{1\le i,j\le(p-1)/2}$$ vanish for each prime $p>7$ with ...
Zhi-Wei Sun's user avatar
  • 14.5k
2 votes
1 answer
418 views

On triangular numbers modulo primes

Let $p$ be an odd prime. For $a\in\mathbb Z$ let $\{a\}_p$ denote the least nonnegative residue of $a$ modulo $p$. The list $\{1^2\}_p,\ldots,\{((p-1)/2)^2\}_p$ is a permutation of all the quadratic ...
Zhi-Wei Sun's user avatar
  • 14.5k