Questions tagged [quadratic-reciprocity]
In number theory, the law of quadratic reciprocity is a theorem about modular arithmetic that gives conditions for the solvability of quadratic equations modulo prime numbers. (Ref: http://en.m.wikipedia.org/wiki/Quadratic_reciprocity)
267
questions
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
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
0
votes
1
answer
49
views
Proof of quadratic reciprocity from Artin reciprocity
I just read the proof of the quadratic reciprocity from the Artin reciprocity here Eisenstein and Quadratic Reciprocity as a consequence of Artin Reciprocity, and Composition of Reciprocity Laws given ...
- 337
3
votes
1
answer
119
views
A proof of quadratic reciprocity law.
I am reading Cox's Primes of the Form $x^2+ny^2$ and solving Exercise 1.13, which depends on Lemma 1.14.
Lemma 1.14. If $D\equiv 0, 1\pmod{4}$ is a nonzero integer, then there is a unique ...
- 3,511
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
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
0
votes
0
answers
5
views
Enumerating odd Quadratic Residues modulo $p, p^m, n$
I has asked this question recently and this came up as a followup question.
Q1. Is there a way to efficiently enumerate odd quadratic residues less than $a$ modulo $p$?
I know we can use quadratic ...
- 2,182
2
votes
0
answers
58
views
Sign of fundamental unit in real quadratic number fields with 1 mod 4 discriminant factors
Let $K$ be a real quadratic number field of discriminant $D$ with fundamental unit $\varepsilon$. Further, I want to assume that each positive factor $n$ of $D$ satisfies $n \equiv 1 \pmod 4$. (For ...
- 5,906
0
votes
1
answer
33
views
What's the maximum order of $A \in SL_2(\mathbb{Z}/p\mathbb{Z})$ if $tr(A)+2$ and $tr(A)-2$ are both either quadratic residue modp or non quad. res??
I have already proved that $SL_2(\mathbb{Z}/p\mathbb{Z})$ is a group with the product of matrices. I also proved that $|SL_2(\mathbb{Z}/p\mathbb{Z})|=p^3-p$ using the first isomorphism theorem and the ...
user1097270
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 ...
- 85
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
3
votes
1
answer
72
views
History of special quadratic reciprocity $(-3/p)_2$ and $(5/p)_2$
https://hsm.stackexchange.com/questions/14533/special-quadratic-reciprocity-3-p-2-and-5-p-2-in-addition-to-1-p-2
asks about the history of special cases of quadratic reciprocity that are ...
- 49.3k
-1
votes
1
answer
43
views
Problem regarding quadratic recidues that I cannot solve [duplicate]
The problem is as follows:
Let $p$ be a prime and assume that $p=1$ mod 5. Let $c\in\left(\mathbb{Z}/p\mathbb{Z}\right)^{\times}$ be an element of order 5 and let $g=2(c+c^{-1})+1$
Show that $g^2=5$ ...
- 15
1
vote
0
answers
47
views
Quadratic Reciprocity as an Analytic Statement
I was told an interesting fact that quadratic reciprocity follows from the modularity of the theta function $\theta(z) = \sum_{n \in \mathbb{Z}}e^{2\pi in^{2}z}$:
$$\theta(\gamma z) = \left(\frac{c}{d}...
user427380
1
vote
1
answer
61
views
Show ${\sum_{i=1}^{\frac{p-1}{2}} \lfloor \frac{2iq}{p} \rfloor + {\sum_{i=1}^{\frac{q-1}{2}}} {\lfloor \frac{2ip}{q} \rfloor}}=(p-1)/2\cdot(q-1)/2$
Let $E = {\sum_{i=1}^{\frac{p-1}{2}}} {\lfloor \frac{2iq}{p} \rfloor + {\sum_{i=1}^{\frac{q-1}{2}}} {\lfloor \frac{2ip}{q} \rfloor}}$ and $E'= \frac{p-1}{2} \frac{q-1}{2}$
Im trying to show that they ...
- 186
1
vote
1
answer
55
views
square root of $a$ mod n when $a$ and n are not relatively prime
When finding whether there exists a solution for $x^2 \equiv a \pmod n $, one way is to calculate it with the Jacobi symbol. However, Jacobi symbol requires that $(a,n) = 1$. So I wonder when $(a,n) \...
- 496
0
votes
0
answers
57
views
Quadratic reciprocity law property of primes of the form $4k+1$ depending from $2$ being a square modulo $p$
Let us consider the following two properties (cases) of a prime $p$ that has the form $4k+1$ and a natural (not necessarily square-free) number $n<p$:
$2$ is a square modulo $p$: If $n$ is a ...
- 1,554
1
vote
0
answers
35
views
Particular case of the law of quadratic reciprocity
Let $\mathbb{F}_q$ be a finite field of characteristic $p \neq 2,5$ .
What I've shown so far :
$x \in\mathbb{F}_q^* $ is a root of $\Phi_5 = X^4 + X^3 +X^2+X+1$ if and only if $x$ is of order 5 in $\...
- 309
0
votes
0
answers
88
views
How to find squares mod $m$, i.e $x$ in $x^2 \equiv a \mod m$, without factoring $m$?
I have very large integers $m$, where ( $\log_2(m)> 630$), and I need to find square roots modulo m. I am aware of several theorems that allow me to find the roots $\mod m$ when m is a power of a ...
- 1,002
2
votes
1
answer
80
views
$2^n$-th rational reciprocity laws
Let $p,q$ be odd coprime primes. We are familiar with the quadratic reciprocity law:
$\left(\frac{p}{q}\right)\left(\frac{q}{p}\right)=(-1)^{\frac{(p-1)(q-1)}{4}}$.
This is generalized (see for ...
- 1,848
3
votes
1
answer
94
views
Finite set of quadratic forms representing all prime numbers
I ask if one can determine a finite set of quadratic forms
$$mx^2+ny^2$$
with $\,m\,$ and $\,n\,$ positive integers s.t. $(m,n)=1$, capable to represent all prime numbers.
We could choose, for ...
- 1,828
3
votes
0
answers
67
views
If $p$ is an odd prime, how to decide the value of $\prod_{i=1}^{(p-1)/2} \cos(2i\pi / p)$
This question is taken from A Classical Introduction to Modern Number Theory by Kenneth Ireland and Michael Rosen, exercise 32, chapter 5.
The original question asks one to prove $(2/p) = \prod_{j=1}^{...
- 31
1
vote
0
answers
35
views
Non-geometric proof to lemma for quadratic reciprocity
There is a common result that for odd, relatively prime positive integers $a,b,$ $\sum\limits_{x=1}^{\frac{b-1}{2}}\lfloor\frac{ax}{b}\rfloor+\sum\limits^{\frac{a-1}{2}}_{y=1}\lfloor\frac{by}{a}\...
- 51
1
vote
0
answers
597
views
Is 219 is a quadratic residue mod 383 (Legendre symbols)
The notes of my course have the example below, but I think there is a mistake.
Isn't the 3rd = from the bottom up supposed to be
$\left(\frac{2}{383}\right)\left(\frac{3}{383}\right)^2$
And then,
$=\...
- 157
0
votes
1
answer
173
views
Question on proving Quadratic Reciprocity with Gauss sums
I'm trying to understand the proof of Quadratic Reciprocity on Wikipedia (this link: https://en.wikipedia.org/wiki/Proofs_of_quadratic_reciprocity#Proof_using_algebraic_number_theory, then the section ...
- 1,443
1
vote
3
answers
58
views
Has the equation $x^2-21 = 17y$ integer solutions?
Has the equation $x^2-21 = 17y$ integer solutions?
Attempt:
I saw this: The equation $x ^ 2 + py + a = 0$ can be solved as an integer precisely, if $-a$ is a quadratic remainder modulo p.
I get: $x^2-...
- 303
1
vote
1
answer
101
views
Extending the Supplement of Eisenstein Reciprocity
One of the supplements of Eisenstein Reciprocity states the following:
Supplement: If $m$ is an odd prime and $a$ is a rational integer relatively prime to $m$, then
$\left(\frac{1-\zeta_m}{a }\right)...
1
vote
1
answer
152
views
Primes of the form $p=X^2+3Y^2$
I'm trying to work in $\mathbb{Z}\left[\frac{1+\sqrt{-3}}{2}\right]$ to show that an odd prime $p\in\mathbb{Z}$, $p\neq 3$ is of the form $p=X^2+3Y^2$ if and only if $p\equiv1$ mod $3$. The hint is to ...
- 690
0
votes
1
answer
68
views
Gaussian sets modulo $p$.
I have the following problem, given the definition:
Let $p$ be an odd prime, and let $S$ be a set of $(p-1)/2$ integers. We call $S$ gaussian set modulo $p$ if $S\cup-S=S\cup\{-s\mid s\in S\}$ Is a ...
- 353
2
votes
1
answer
49
views
Is there an archive or a collection of quadratic reciprocity proofs?
After Pythagorean theorem the quadratic reciprocity has the largest amount of proofs, I heard there are more than 160 proofs of quadratic reciprocity. I have seen a few of these proofs but I was ...
- 125
0
votes
1
answer
208
views
Proving first supplement of the quadratic reciprocity law [duplicate]
I'm trying to prove the first supplement of the quadratic reciprocity law in its particular form:
$$-\bar{1} \text{is a square in} \mathbb{Z}/p\mathbb{Z} \iff p \equiv 1 \pmod 4$$
For the forward part,...
- 414
2
votes
1
answer
166
views
Prove a formula to evaluate Legendre Symbol $(\frac{-3}{p})$ using quadratic Gauss Sums (i.e. without using quadratic reciprocity)
I've been trying to find a question similar to this, but have failed to find any. The full statement is let $\zeta = e^{\frac{2\pi i}{3}}$, and use the fact that $(2 \zeta + 1)^2 = -3$ and quadratic ...
1
vote
1
answer
101
views
Use the quadratic reciprocity to show that 5 is a square modulo $M_l$ if and only if $l$ ≡ 1 (mod 4).
Let $l$ be an odd prime such that $M_l = 2^l − 1$ is a Mersenne prime. Use the quadratic reciprocity to show that 5 is a square modulo $M_l$ if and only if $l$ ≡ 1 (mod 4).
Here's what I know: Using ...
- 27
0
votes
1
answer
73
views
Is it possible to derive the quadratic reciprocity law from the decomposition law in a quadratic extension?
How can I derive the quadratic reciprocity law from the decomposition law for a prime in a quadratic extension?
There is no need to read the following texts.
I know the necessary and sufficient ...
0
votes
2
answers
76
views
Question 9 of 9.3 Elementary number theory David Burton
I am trying section 9.3 of David Burton Elementary Number Theory and got struck on this problem.
If $p$ and $q$ are odd primes satisfying $p=q+4a$ for some a establish that $\big(\frac{a}{p}\big)$ = $...
- 1
0
votes
2
answers
66
views
Question 9.27 david M burton elementary number theory
This question is from David burton section: Quadratic reciprocity law, page 184.
Question: If p is an odd prime, show that $\sum_{a=1}^{p-2} (a(a+1) /p) =-1$ .
I can only say that a, a+1 are always ...
- 1
0
votes
1
answer
127
views
Integers that are square modulo all powers of 2
If an integer is odd, it is square modulo all powers of $2$ if and only if it is a square modulo $8$ if and only if it is equivalent to $1$ modulo $8$.
How do we determine if an integer $a$ is square ...
- 1,585
1
vote
1
answer
127
views
Nice lemma regarding factorials and quadratic residues
IMPORTANT: I posted this as I thought I found a generalized result, which turned out to be false (by a trivial flaw), but a nice lemma still remains (however, this can be closed now)
Lemma:
If $p\...
user799688
1
vote
1
answer
92
views
Law of Quadratic Reciprocity for primes that are congruent 3 or 1 modulo 4
I have a question regarding some claims I read about the Law of Quadratic Reciprocity that I can't fully understand. The law itself is written as follows:
For all odd numbers $P,Q \in \mathbb{N}$ with ...
- 301
5
votes
2
answers
121
views
Let $p=40k+9$ be prime. Does $10$ always have even order mod $p$?
This came up while answering a question on the period of the decimal expansion of $1/p$. The critical factor was whether the period (aka the order of $10$ mod $p$) is even or odd, equivalently ...
- 24.5k
2
votes
1
answer
83
views
Show for any odd prime $p\geq 5,$ $(-3/p)=1$ or $ -1$ [duplicate]
Show for any odd prime $$p\geq 5,$$
$$\left ( \frac{-3}{p} \right ) =\begin{cases}
1 & \text{ if } p\equiv 1,-5\pmod{12} \\
-1& \text{ if } p\equiv -1,5\pmod{12}
\end{cases}$$
So far I have ...
- 71
5
votes
3
answers
111
views
Finding roots of a polynomial using quadratic reciprocity
Does the polynomial $X^2− X + 19$ have a root in $\mathbb Z/61\mathbb Z$? I am unsure of how to go about this problem but I outlined the way I have been approaching these problems in the problem below....
2
votes
2
answers
169
views
If $p\equiv 1 \;\text{mod}\; 3$, then show that one can find an integer $k$ satisfying $k^2-k+1=p\cdot M\;$ with $M<p$
If $p\equiv 1 \;\text{mod}\; 3$, then show that one can find an integer $k$ satisfying $k^2-k+1=p\cdot M\;$ with $M<p$ ($p$ is a prime)
I don't have any clue on how to work this problem. Also, if ...
4
votes
2
answers
842
views
When is $-3$ a quadratic residue mod $p$?
Going over a past exam in my elementary number theory course, I noticed this question that caught my attention. The question asked for the conditions that allowed $-3$ to be a quadratic residue mod $p$...
- 93
1
vote
1
answer
52
views
Are $3$ and $19$ the only primes representable by the principal form with discriminant $-57$?
I'm trying to see if there are other primes, but so far I only managed to get $3$ and $19$ by factoring $57$. How would I find other primes, if they do indeed exist?
- 11
0
votes
1
answer
74
views
Determine if $n$ could be represented by a quadratic form of discriminant $d$
So, I know this is only possible whenever $d$ is a square $\pmod{4\cdot |n|}$, but can that be simplified any further?
As an example, if I am given that $d=-39$ and $n=500$, this reduces to solving $x^...
0
votes
0
answers
113
views
Computational complexity of finding a quadratic nonresidue modulo a prime
For a prime $N$, there are precisely $\frac{N-1}{2}$ quadratic nonresidues modulo $N$. Picking a base randomly, one would expect a $1/2$ chance of choosing a quadratic nonresidue. Excluding perfect ...
- 1,848
2
votes
0
answers
72
views
Finding solutions to $x^2\equiv a$ mod $8k+1$, $8k+1$ prime
For $N=4k+3$ prime, a solution can easily be found as $x=a^{k+1}$. This is because:
$x^2=a^{2k+2}=a^{2k+1}\cdot a=a^{\frac{N-1}{2}}\cdot a\equiv a\mod N$.
A similar construction can be done for $N=8k+...
- 1,848
4
votes
1
answer
168
views
Prove that there exist infinitely many primes $p$ such that $13 \mid p^3+1$
$\textbf{Question:}$Prove that there exist infinitely many primes $p$ such that $13 \mid p^3+1$
I could easily see that the given is equivalent to showing that there are infinitely many primes $p$ ...
- 1,776