Skip to main content

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)

Filter by
Sorted by
Tagged with
0 votes
1 answer
61 views

Simplifying a reciprocal of a product of two quadratics using modular arithmetic

This is the fraction I'm trying to simplify mod q: $\frac{1}{(k^{2a} + k^a + 1)(k^{2b} + k^b +1)}$ and we have that $k^5 = 1 \bmod q$, $k ≠ 1 \bmod q$, and that $a$ and $b$ are integers where $a ≠ b$ ...
Polom Mata's user avatar
5 votes
1 answer
152 views

About the solutions of $ \dfrac{x^p - y^p}{x - y} = a^2+pb^2 $

Using theorem $IV$ from this article, is possible to prove that when $p$ is a prime $p ≡ 3\bmod4$, $x ≢ y\bmod{p}$ and $\gcd(x,y) = 1$, then the equation $ \dfrac{x^p - y^p}{x - y} = a^2+pb^2 $ ever ...
user967210's user avatar
0 votes
1 answer
81 views

How to prove the roots of $ax^2 + bx + a$ are reciprocals of each other? [closed]

How to prove the roots of $ax^2 + bx + a$ are reciprocals of each other? I tried using quadratic formula to find the two roots but got stuck at the part on how to prove they are reciprocal. Please ...
user1274605's user avatar
0 votes
2 answers
51 views

How to show a quadratic polynomial with complex roots has solutions mod $p$?

When the discriminant is $-k$ or ${-1\over k}$: As long as $-1$ and $k$ are both squares $\bmod p$ (trivial) or are both not squares, there are solutions mod $p$. How can this be explained/proven? e.g....
Older Amateur's user avatar
1 vote
0 answers
51 views

Conceptual explanation for extra/missing $p$ solutions to $x^2+y^2=a \pmod p$ at $a=0$

Throughout, $p$ will denote a prime integer, and $k$ an arbitrary integer. I have worked through V. Lebesgue's proof of quadratic reciprocity outlined by Keith Conrad in this MO thread, and I feel ...
D.R.'s user avatar
  • 8,945
2 votes
0 answers
36 views

Determining which primes satisfy a set of quadratic divisibility conditions

I have a [hypothetical] prime $\phi$ which satisfies the divisibility conditions $$\phi \mid (2a^2-1)$$ $$\phi \mid (b^2-2)$$ $$\phi \mid (c^2-8)$$ $$\phi \mid (2d^2-289)$$ $$\phi \mid (e^2-1682)$$ $$\...
Kieren MacMillan's user avatar
0 votes
0 answers
61 views

Stuck in a quadratic reciprocity problem

I've recently started studying elementary number theory. Now I'm going through the topic of quadratic reciprocity. I'm having trouble trying to show that $n$ and $k$ are even numbers whenever $60k+7$ ...
dwhydtea's user avatar
  • 101
3 votes
0 answers
81 views

prime divisors of number of the form $32z^4+1$

In a proof I‘m working on, I’m trying to characterize a prime $\phi$ which divides three numbers: one of the form $2x^2+1$, one of the form $2y^4+1$, and one of the form $32z^4+1$. Using various ...
Kieren MacMillan's user avatar
2 votes
0 answers
56 views

Intuition behind Eisenstein's proof of quadratic reciprocity using a function of a complex variable

I have read about one of Eisenstein's proof of quadratic reciprocity using a function of a complex variable, presented here (chapter 2.2, pp.11-15), which I summarized below. It's quite ingenious, and ...
zyy's user avatar
  • 1,001
2 votes
2 answers
81 views

Show that $z^2$ is a fourth power mod $q$ if and only if $\left(\frac{z}{q}\right) = 1$, given that $q \equiv 1 \pmod{4}$.

Show that $z^2$ is a fourth power mod $q$ if and only if $\left(\frac{z}{q}\right) = 1$, given that $q \equiv 1 \pmod{4}$. Here $\left(\frac{z}{q}\right)$ is the Legendre symbol whose value of 1 ...
TSpoon's user avatar
  • 339
3 votes
1 answer
97 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 $\...
mathquester's user avatar
0 votes
1 answer
169 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 ...
Ja_1941's user avatar
  • 558
4 votes
2 answers
239 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 ...
bfhaha's user avatar
  • 3,771
1 vote
0 answers
46 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$. ...
vvg's user avatar
  • 3,341
1 vote
1 answer
63 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 = ...
vvg's user avatar
  • 3,341
2 votes
0 answers
92 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 ...
principal-ideal-domain's user avatar
0 votes
1 answer
40 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 ...
user avatar
0 votes
1 answer
131 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 ...
confusedTurtle's user avatar
0 votes
0 answers
46 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 ...
Tony Erwin's user avatar
5 votes
1 answer
113 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 ...
paul garrett's user avatar
  • 53.2k
-1 votes
1 answer
47 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$ ...
An0ku's user avatar
  • 15
1 vote
0 answers
61 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}...
user avatar
1 vote
1 answer
90 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 ...
CHTM's user avatar
  • 308
1 vote
1 answer
69 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) \...
wsz_fantasy's user avatar
  • 1,732
0 votes
0 answers
60 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 ...
Eldar Sultanow's user avatar
1 vote
0 answers
47 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 $\...
Kieran McShane's user avatar
0 votes
0 answers
143 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 ...
ReverseFlowControl's user avatar
1 vote
1 answer
100 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 ...
Tejas Rao's user avatar
  • 1,950
3 votes
1 answer
141 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 ...
Augusto Santi's user avatar
3 votes
0 answers
69 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}^{...
梁健哲's user avatar
1 vote
0 answers
38 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}\...
mauCheese's user avatar
1 vote
0 answers
1k 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, $=\...
TheVoiceInMyHead's user avatar
0 votes
1 answer
449 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 ...
tomos's user avatar
  • 1,662
1 vote
3 answers
65 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-...
Vek's user avatar
  • 303
1 vote
1 answer
139 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)...
Sohail Farhangi's user avatar
1 vote
1 answer
211 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 ...
Saegusa's user avatar
  • 772
0 votes
1 answer
86 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 ...
ibs_bernal's user avatar
2 votes
1 answer
86 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 ...
Matin Yousefi's user avatar
0 votes
1 answer
283 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,...
RFTexas's user avatar
  • 414
2 votes
1 answer
217 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 ...
Michael Borrello's user avatar
1 vote
1 answer
141 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 ...
lexren17's user avatar
0 votes
1 answer
88 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 ...
Tireless and hardworking's user avatar
0 votes
2 answers
83 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)$ = $...
user avatar
0 votes
2 answers
78 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 ...
user avatar
0 votes
1 answer
186 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 ...
HumbleStudent's user avatar
1 vote
1 answer
147 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\...
user avatar
1 vote
1 answer
193 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 ...
Rebronja's user avatar
  • 301
5 votes
2 answers
138 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 ...
Erick Wong's user avatar
  • 25.3k
2 votes
1 answer
110 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 ...
adrianna's user avatar
5 votes
3 answers
148 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....
Sapphirelemma's user avatar

1
2 3 4 5 6