Questions tagged [quadratic-residues]
An integer $a$ is a quadratic residue modulo $p$ if $a \equiv x^2 \pmod p$ for some integer $x$. If $a$ is not a quadratic residue modulo $p$, it is said to be a quadratic nonresidue modulo $p$.
762
questions
1
vote
0
answers
32
views
Number of Residues of $x^n \pmod{p}$
I wanted to prove that when $n<\frac{p-1}{2}$ for prime $p$, then $x^n$ takes on more than or less than, but not equal to $3$ residues modulo $p$, for $x$ over the integers.
Obviously when $p\mid x$...
0
votes
1
answer
63
views
Curious about the meaning of the term '&c' in Legendre's paper [closed]
In Legendre's paper "De Nouvelles Méthodes pour la Détermination des Orbites des Comètes", the term $\&c$ is used. I'm not familiar with that terminology, but it seems to me that it ...
- 130
0
votes
1
answer
43
views
How can one go about determining which primes $p>3$ satisfy the Jacobi symbol $(\frac{-3}{p})=1$? [closed]
I know how to do this for a positive 3, but the -3 is throwing me off a little. I’m not exactly sure how to proceed with determining the primes to satisfy that Jacobi symbol. Thanks for any help
user1158569
-1
votes
1
answer
61
views
What's the link from $2^u-1$ to the multiplicative order?
I am reading this paper, but I will write everyting I need for my question here.
So, long story short, we have a proth-number $n$, i.e. $n = h\cdot 2^k+1$ for odd $h<2^k$.
We are looking for ...
- 140
0
votes
0
answers
28
views
First Element $D$ such that $\left(\frac{D}{n}\right) \neq 1$ for given $n$.
I am reading this paper, but for my question, you don't have to.
Let $n$ be a Proth-number, i.e. $n = h\cdot 2^k+1$ for $k\geq 2$ and an odd $h$ and $h<2^k.$
Now I am looking for elements $D$ such ...
- 140
1
vote
1
answer
52
views
Infinitely many primes $q$ such that $p$ is a quadratic residue modulo $q$
For primes $p,q\equiv 1\pmod 4$, I want to know if there are infinitely many $q$ such that $p$ is a quadratic residue modulo $q$?
This question is important to me for understanding whether the ...
- 942
4
votes
0
answers
60
views
Given a sequence $\left(\tfrac{x}{p}\right),\left(\tfrac{x+1}{p}\right),\dots,$ how hard it is to find an $x$ that fits?
Let $p$ be some 1000-bit prime number.
Given a sequence $1$'s and $-1$'s
$$\left(\tfrac{x}{p}\right),\left(\tfrac{x+1}{p}\right),\dots,\left(\tfrac{x+80}{p}\right)$$ how hard it is to find an $x \in \...
3
votes
1
answer
84
views
Generalized Pépin-Test (Problem understanding a paper)
I am reading this paper (but you don't need to, I will write down what is needed for the question), and I have difficulty understanding a certain conclusion.
$(1.1)\ \ $ $n = 2^k+1$ is prime $\...
- 140
1
vote
0
answers
31
views
A cycle of $x^2 \bmod p$ must contain both numbers greater than half of $p$ and numbers less than half of $p$
Let us define $f(x) = x^2 \bmod p$, $x=0,1,\cdots,p-1$, where $p$ is a given prime number ($p>2$).
Define $G (V,E)$ to be a directed graph where $V=\{0,1,\cdots p-1\}$ and $E=\{(x \to f(x)) \mid x \...
- 11
5
votes
1
answer
89
views
Decomposition of rational primes, why work over ring of algebraic integers?
The proof of Thm. 6.1 in this article https://people.reed.edu/~jerry/361/lectures/iqclassno.pdf actually proves the following generalization of Thm. 6.1 beyond quadratic number fields (copied from the ...
- 7,174
1
vote
1
answer
40
views
What can we tell about quadratic residues modulo $an+b$ ($n=1,2,\dots$)?
I only know a little about quadratic residues, and I have a question that: What can we say about quadratic residues modulo $an+b$, for example, $30n+1$? $(n=1,2,\dots)$
Of course, $0,1,4,9,16,25$ are ...
- 1,946
2
votes
2
answers
111
views
For what integers $n$, do we have $30n+11=6x^2+5y^2$ for some integers $x,y$?
I am trying to find all integers $m$ such that $m$ is relatively prime to 30, and $m=6x^2+5y^2$ for some integers $x,y$. Note that we must have: $y$ is odd, $(y,3)=1=(x,5)$. Using these conditions, I ...
- 1,946
1
vote
0
answers
94
views
Constructions for finding two squares which sums to a prime
This question is related to Efficiently finding two squares which sum to a prime.
The following 3 methods are found in Chapter 5.3 of The Higher Arithmetic by H. Davenport. However, I failed to ...
- 41
0
votes
0
answers
13
views
Inverse chinese theorem $x \in Qr(n) \iff x \in Qr(p) \wedge x \in Qr( q)$ [duplicate]
I found this sentence in a paper :
Let $n=pq$ where $p, q$ are primes and let $Qr(n) = \{x^2 \mod n | \; x \in Z_n^*\}$ the set of quadratic residues in $Z^*_n$.
By Chinese remainder theorem we get :$$...
- 729
0
votes
0
answers
26
views
Is there a relationship between the least quadratic non-residue modulo $n$ and factoring $n$
The following theorem shows square roots mod $n$ is equivalent to factoring $n$.
Theorem 1. If $n=pq$, where $p$ and $q$ are primes $\equiv 3 \pmod4$, and $y$ is a number relatively prime to $n$ which ...
- 2,182
1
vote
1
answer
62
views
Expressing the number of solutions of $ax^2+by^2\equiv$1(mod $p$) in terms of Legendre symbol
If $p$ is a prime and $a,b$ are integers both coprime to $p$, then prove that $ax^2+by^2\equiv$1(mod $p$) has $p-(\frac{-ab}{p})$ solutions where $(\frac{a}{p})$ denotes the Legendre's symbol.
My ...
1
vote
0
answers
25
views
On the Least Quadratic Non-residue and Integer Factoring
A result by Chowla/Fridlender/Salié says that (with a
constant $c \gt 0$) there are infinitely many primes such that
all integers $a$ with $1 \le a \le c \cdot \log(p)$ are quadratic residues
mod $p$.
...
- 2,182
1
vote
1
answer
24
views
Are Quadratic residues modulo $n \equiv 1 \bmod 4$ symmetric about $n \over 2$
If $p \equiv 1 \bmod 4$ is a prime, then the quadratic residues modulo $p$ are symmetric about $\frac p 2$. i.e., $a$ is a QR iff $p-a$ is a QR. Does this property carryover to composite modulus $n = ...
- 2,182
-2
votes
2
answers
118
views
Solving $x^2\equiv x \pmod{12}$
I was requested to solve $x^2\equiv x \pmod{12}$. I'm fairly new to modular arithmetic and wanted to see if my solution is correct. Besides, I'm pretty sure there is a simpler solution and I'm ...
- 2,648
0
votes
1
answer
54
views
Prove the properties of Fibonacci sequence $F_p$ $F_{p-1}$ $F_{p+1}$ mod p for prime p
p is a prime and Let $F_{n}$ denotes the Fibonacci sequence.
I want to show the following properties of $F_p$:
$F_p\equiv\left (\frac{p}{5} \right ) (mod ~p)\tag{0}$
And for $F_{p+1}$:
$F_{p+1}\...
- 369
0
votes
1
answer
68
views
Prove that if $X^2 ≡ b\pmod{p^e}$ has a solution for some for $p \geq 3$ , then $X^2 ≡ b\pmod{p^{e+1}}$ has a solution for all $e \geq 1$ [duplicate]
Let $p \geq 3$ be a prime and suppose that the congruence $X^2 ≡ b\pmod{p^e}$ (1) has a solution.
$\pmod{p^e}$
Prove that for every exponent $e \geq 1$ the congruence $X^2 ≡ b\pmod{p^{e+1}}$ (2) has a ...
1
vote
1
answer
73
views
Proving $(a/p) = -1$ for infinitely many $p$, without Dirichlet's Theorem.
I'm trying to find a proof of the following claim, without using Dirichlet's Theorem on the arithmetic progression of primes:
Claim: If $a$ is not a square, then there are infinitely many odd primes $...
- 432
2
votes
1
answer
86
views
How to compute product of Jacobi symbols
Let $m>1$ be odd. I want to find the product for:
$$\prod_{\substack{(a,m)=1 \\ 1 \leq a \leq m}} \left(\frac{a}{m}\right)$$ where $\left(\frac{a}{m}\right)$ is a Jacobi symbol.
I know that each of ...
- 162
5
votes
1
answer
196
views
An interesting Legendre symbol identity: $\left (\frac{a}{p} \right ) = \prod_{h\in\mathscr{H}}^{}\frac{\sin(2\pi ah/p)}{\sin(2\pi h/p)}$
If we call $\mathscr{H}$ a one-half set of reduced residues (mod $p$), $p$ is a prime, if $\mathscr{H}$ has the property that:
$h \in \mathscr{H}$ if and only if $-h \notin \mathscr{H}$
Let $\...
- 369
1
vote
1
answer
74
views
Prove that $\sum_{y=0}^{p-1}\left(\frac{y}{p}\right)\left(\frac{y+d}{p}\right)=-1$
The question is from The number of solutions of $ax^2+by^2\equiv 1\pmod{p}$ is $ p-\left(\frac{-ab}{p}\right)$
And I wonder how to prove the following equation although someone gives the trick:
\begin{...
- 369
0
votes
1
answer
107
views
Find all primes $p$ such that $ 3x^2-1\equiv 0 \mod{p}$ has a solution
So I generally know how to do this for equations where $x^2$'s coefficient is $1$. Completing squares and then using quadratic reciprocity I can find that primes for which there are solutions depend ...
- 87
-1
votes
1
answer
52
views
The number of $x$ for which $-4x$ and $-4x+1$ are quadratic residues mod some odd prime number
Let $p$ be an odd prime number. What is the number $N_p$ of $x\in (\mathbb{Z}/p\mathbb{Z})^{\times}$ for which $-4x$ and $-4x+1$ are quadratic residues modulo $p$?
Some computations give me :
$$N_3=...
- 61
0
votes
0
answers
45
views
finding if a number $a$ is a quadratic residue mod $p$ computationally
In a cryptography class, I'm required to write code to check if a number is a quadratic residue mod p. I'm trying to do this by using the Legendre symbol but I'm having some trouble with one exercise ...
- 3,959
0
votes
0
answers
38
views
Missing link in Wikipedia's proof of quadratic reciprocity law
Gauss' well-known law of quadratic reciprocity states the following:
Main Theorem. Given two disttinct primes, $p$ and $q$, if at least one of $p-1$ and $q-1$ is divisable by $4$, then the congruency ...
- 37
0
votes
1
answer
81
views
Quadratic residues modulo pq
Let us say we have the sets of quadratic residues $X = \lbrace x^2 \pmod{p}\rbrace$ and $Y = \lbrace y^2 \pmod{q}\rbrace$.
Is there a way to construct the set of quadratic residues $Z_{\beta} = \...
- 2,182
0
votes
0
answers
21
views
Legendre symbol and formula for 2 quadratic residue modulo p
$$\left(\frac{2}{p}\right) = (-1)^{(p^2-1)/8}$$
I am trying to understand the proof of the above result from the book of Rosen. The same proof is also given in the following link. But how the exponent ...
- 646
1
vote
1
answer
113
views
A primitive root modulo p is a primitive root modulo $p^2$ if and only if $g^{p-1} \not\equiv 1 \mod{p^2}$
$p$ is an odd prime. I'm starting with number theory and I'm completly stuck with this question. In general, I don't really know how to approach the proves. Then I'm also supposed to prove that either ...
- 87
0
votes
0
answers
29
views
If $p$ is a prime where $p=4k+3$ and $a$ is a quadratic residue modulo $p$, then exactly one if its roots is a QR modulo $p$?
I recall encountering a theorem which stated something like: if $p$ is a prime of the form $p=4k+3$ and $a$ is a quadratic residue (QR) modulo $p$, then exactly one if its roots is a QR modulo $p$.
I ...
- 1,555
0
votes
0
answers
18
views
How to find the following quadratic residue - help with partial progress
I'm trying to solve the following question, but was only able to obtain a partial solution:
Let $p$ be an odd prime and $a$ a quadratic residue modulo $p^2$, with $y^2=a \mod p^2$ for $y=sp+t \mod p^...
- 1,555
0
votes
0
answers
31
views
Quadratic residues and their using in proving the Édouard Lucas theorem related to Fermat numbers. [duplicate]
I was doing a study on Fermat Numbers when I came across this theorem by Édouard Lucas (unproven in my reference material):
Every prime divisor of $F_n = 2^{2^{n}} + 1$ is of the form $k \cdot{2^{n+2}...
- 148
0
votes
0
answers
70
views
solve diophantine equation $a+b+2ab=n$
I need to find the samllest positive integer value of a for which $(n - a) / (1 + 2 a)$ is an integer. where n is a given natural number .
In other words solve diophantine equation for postive $a$, $b$...
user1080747
0
votes
0
answers
25
views
Because it is enough to calculate these values to find the quadratic residue $x^2 ≡ a (mod 13)$ [duplicate]
Let $m$ be a positive integer and $a$ any integer such that $(a, m) = 1$. Then $a$ is a quadratic residue of $m$ if the congruence $x^2 ≡ a (mod m)$ is solvable; otherwise, it is a quadratic ...
- 2,733
2
votes
0
answers
37
views
What is the number of quadratic residues in $Z_{11^4}$? [closed]
I am stuck on this question.
We know there exists (p-1)/2 number of quadratic residues in $Z_{p}$, how about in $Z_{p^a}$? Can we approach it by Hensel's Theorem?
For example, What is the number of ...
- 21
3
votes
2
answers
120
views
Is there any way to predict the largest number of consecutive quadratic or cubic residues modulo prime $p$?
We all know that $a$ is a quadratic residue modulo $p$ if and only if $a^{(p-1)/2} \equiv 1 \pmod p$,
also $a$ is a cubic residue modulo $p$ if and only if $a^{(p-1)/3} \equiv 1 \pmod p$.
Now, for a ...
6
votes
1
answer
214
views
number of solutions to $x^2 + xy + y^2 = 0\mod p$
Let $p$ be an odd prime congruent to $2$ modulo $3$ and $c$ an integer between $1$ and $p-1$. Let $\chi(x)$ denote $\left(\dfrac{x}{p}\right)$ (the Legendre symbol modulo $p$ for $x$). How many ...
- 1,127
3
votes
1
answer
99
views
Proving $b^n-1$ is not a perfect square for any $b, n \geq 2$
I am currently attempting to prove that $b^n - 1$ is not a perfect square for any integers $b$ and $n$ greater than 1. I've gotten most of the way using a straightforward argument using quadratic ...
- 333
0
votes
0
answers
81
views
Quadratic residue and Chinese Remainder Theorem [duplicate]
I have been casually reading a set of notes (page 30 in reader) on number theory, but I am not certain on one of the steps in the reasoning. Here is a quote:
What can we say about $w^2 ≡ −3\mod 4n$? ...
- 1,412
2
votes
1
answer
99
views
Sum of squares and quadratic residues
I found the following statement:
"If sum of three numbers which are squares is divisible by $9$, then difference of two of these three numbers is divisible by $9$."
This can be proved by ...
- 341
2
votes
0
answers
190
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 ...
user14479
2
votes
0
answers
59
views
Explicit description of primes for which $2$ is a quartic residue?
According to this SE question (and the internet more generally), $2$ is a quartic residue modulo a prime $p\equiv 1\pmod{4}$ if and only if $p$ may be written in the form $a^2 + 64b^2$ for integers $a$...
- 3,647
1
vote
1
answer
72
views
Evaluate a kronecker symbol sum: $\sum\limits_{n=1}^\infty \frac {\big(\frac n x\big)}n$ and $\sum\limits_{n=1}^\infty \frac {\big(\frac xn\big)}n$
The Kronecker Symbol $\left(\frac nm\right)$ has a range of $\{-1,0,1\}$ and $\sum\limits_{n=1}^\infty\frac{(-1)^n}n=-\ln(2)$, so we combine to find the following with the using software. Also note ...
- 7,804
0
votes
1
answer
27
views
Equal Legendre symbols.
Any hints for proving that if $p$ and $q$ are odd primes such that $p=4a+q$ for some integer $a$ then $\left(\frac{a}{p}\right) = \left(\frac{a}{q}\right)$? I have tried using quadratic reciprocity ...
- 78
14
votes
3
answers
621
views
Can we generalize the quadratic formula to modular arithmetic?
Does the quadratic formula $\displaystyle x = \frac{-b \pm \sqrt{b^2-4ac}}{2a}$ hold modulo $n$ for $ax^2 + bx + c \equiv 0 \pmod n$?
Computing the square root would require factoring $n$ and using ...
- 267
1
vote
1
answer
121
views
Number of solution of $x^2+1 \equiv 0 \pmod p$ where $p\equiv 1 \pmod 4$ and p is a prime
This question is to be used in a theorem of Algebraic Number Theory and I am struck on this.
Question: Prove that there are 2 solutions of the equation $x^2 +1 \equiv 0 \pmod p$ . Here $p\equiv 1 \...
user1060925
1
vote
1
answer
31
views
Efficient computation of Jacobsthal matrix / quadratic character in GF(q)
Is there an efficient algorithm to compute the quadratic character $\chi$ on GF($q$) in order to get the Jacobsthal matrix
$$
J_{i,j} = \chi(i-j) = \begin{cases} ~0 & \rm if & i = j\\ ~1 &...
- 397