Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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)

5
votes
1answer
65 views

Proof that $x^4 - qy^4 = az^2$ has no integral solution

This is a question from Takashi Ono's book, Problem 1.45 to be exact. The question is Let $q$ be a prime such that $q = 1 \mod 8$ and $a$ be an integer such that $p^2\not\mid a$ for any prime $p$ and ...
0
votes
1answer
47 views

if $19a^2 \equiv b^2 \pmod 7$ then $19a^2 \equiv b^2 \pmod {7^2}$

I am stuck with this problem. All what I can tell is that $19a^2 \equiv 5a^2 \equiv b^2 \pmod 7$ and $5$ is not a quadratic residue$\pmod 7$. Any hints please,,
1
vote
2answers
66 views

Solutions to $x^2+x-1\equiv 0$ mod $p$

The problem is to find all prime number p such that the above congruence has solutions. I started this problem by rearranging the equation such that: $$ x(x+1)\equiv 1 \pmod{p} $$ The hint given was ...
2
votes
2answers
134 views

What are the Legendre symbols $\left(\frac{10}{31}\right)$ and $\left(\frac{-15}{43}\right)$?

I have the following two Legendre symbols that need calculated: $\left(\frac{10}{31}\right)$ $=$ $-\left(\frac{31}{10}\right)$ $=$ $-\left(\frac{1}{10}\right)$ $=$ $-(-1)$ $=$ $-1$ $\left(\frac{-15}{...
1
vote
1answer
42 views

Writting Legendre Symbol as an element of group cohomology of $\mathbb{Q}$

Is it possible to write the Legendre symbol as an element of the cohomology of some kind? We certainly have that it is multiplicative in both numerator and denominator: $$ \left( \frac{a}{p} \right)\...
2
votes
1answer
42 views

Diophantine equations for septic $(7$th$)$ power reciprocity

Let $p$ be a prime, and $p-1=fd$. There is exactly one unique subfield of $\mathbb{Q}(\zeta_p)$ which is of degree $d$. The defining polynomial $P_d(x)$ for this subfield has the root: $$\sum_{r=1}^{...
2
votes
1answer
85 views

Prove that $\forall x\in\mathbb{N}\ \text{ there always exists a prime }p\equiv1 \pmod 6 \text{ s.t. }p|(2x)^2+3;$

I want to prove the following: $$\forall x\in\mathbb{N}\ \text{ there always exists a prime }p\equiv1 \pmod 6 \text{ s.t. }p|(2x)^2+3;$$$\ \text{i.e. } (2x)^2\equiv-3 \pmod p$ where $p$ is ...
2
votes
1answer
72 views

Condition for Quintic Reciprocity

Let $p=x^2+11x-1=1\pmod 5$ be a prime. Show that $x$ is a quintic residue $\pmod p$. It holds for $x<200$ and should hold for all such $x$. Any proof ideas? Thanks in advance.
3
votes
2answers
82 views

Find the set of primes $p$ which $6$ is a quadratic residue $\mod p$

Since $6$ is not prime (law of quadratic reciprocity could have been used), how does one find the set of primes $p$ for which $6$ is a quadratic residue $\pmod p$? I noticed that $6$ is a quadratic ...
-2
votes
1answer
38 views

Quadratic Reciprocity problem.. help! [closed]

If $p$ is an odd prime, evaluate $\left(\frac{1\times2}{p}\right)+\left(\frac{2\times3}{p}\right)+\cdots+\left(\frac{(p-2)\times(p-1)}{p}\right)$ I don't know how I use properties of Legendre symbol. ...
2
votes
1answer
52 views

$3$ is a quadratic residue $\bmod p$ iff $ p \equiv \pm 1 \bmod12$

Could anyone give me any hints as to how to prove this? I've tried using Euler's formula $3^\frac{p-1}{2} \equiv \left(\frac{3}{p}\right)\bmod p$, and quadratic reciprocity but I'm not getting ...
1
vote
3answers
34 views

Use quadratic reciprocity to decide whether the following congruences are solvable

The first one is: $x^2 \equiv109(\mod157)$. The second one is: $x^2 \equiv141(\mod181)$ I tried using some properties but didn't really get anywhere... $ \frac{109}{157} = \frac{157}{109} = \frac{...
0
votes
0answers
42 views

Prove that there exists a number $x$ such that $x^2 \equiv 2$ (mod $p$) and $x^2 \equiv 3$ (mod $q$)

Let $p$ and $q$ be distinct odd primes for which $(2/p)$ and $(3/q)$ are both $1$. Prove that there exists a number $x$ such that $x^2 ≡ 2$ (mod $p$) and $x^2 ≡ 3$ (mod $q$). This is my attempt to ...
0
votes
0answers
33 views

Elementary Number Theory: Quadratic Reciprocity

Note that $2717 = 11*13*19$ and determine if $x^2 \equiv 295$ (mod $2717$) is solvable. I know I have to spilt this up into three different congruences $x^2 \equiv 295$ (mod $11$), $x^2 \equiv 295$ (...
1
vote
1answer
68 views

Prove $\sum\limits_{j=1}^{p-1} j\left(\frac{j}{p}\right) = 0 $ for an odd prime $p$ with $p\equiv 1\text{ mod } 4$

I want to show for an odd prime $p$ with $p\equiv 1\text{ mod } 4$, that $$\sum\limits_{j=1}^{p-1} j\left(\frac{j}{p}\right) = 0 $$ where $\left(\frac{j}{p}\right) $ is the Jacobi symbol. I got ...
2
votes
1answer
41 views

Why is it the case that if $a$ is a primitive root of $x^p=1$, then $\frac{x^p-1}{x-1}=(x-a^2)(x-a^4)…(x-a^{2(p-1)})=1+x+x^2+…+x^{p-1}$?

If $p$ is an odd prime. Why is it the case that if $a$ is a primitive root of $x^p=1$, then $\frac{x^p-1}{x-1}=(x-a^2)(x-a^4)...(x-a^{2(p-1)})=1+x+x^2+...+x^{p-1}$? I can see why $\frac{x^p-1}{x-1}=1+...
1
vote
1answer
39 views

Prime factors of $16k^4 +1$ mod $8$

I need to show that for $k \in \mathbb{Z}$ there exists no prime factor $p$ of $16k^4 + 1$ with $p \equiv -1 \pmod 8$. How would I approach this problem?
1
vote
1answer
78 views

How can we summarize Legendre symbol $(\frac{11}{p})$

We note that $11\equiv 3 \pmod 4$. So by using the law of quadratic reciprocity to get $(\frac{p}{11})$, we need to discuss the residue of $p\pmod 4$. I'm wondering how to give a specific formula ...
4
votes
1answer
196 views

Zolotarev's Lemma and Quadratic Reciprocity

The law of quadratic reciprocity is unquestionably one of the most famous results of mathematics. Carl Gauss, often called the "Prince of Mathematicians", referred to it as "The Golden Theorem". He ...
4
votes
1answer
322 views

Discovering Quadratic Reciprocity

Is there anything similar to this (page written by Field Medalist Timothy Gowers) for quadratic reciprocity ? I mean, the link there explains how you can figure out the solution of cubic equation by ...
0
votes
2answers
74 views

The set of odd primes p such that -5 is a quadratic residue mod p

For any odd prime p -5 is a quadratic residue mod p $\Leftrightarrow$ $(\frac{-5}{p})$=1 By multiplicaticity of the legendre symbol $(\frac{-5}{p})$=$(\frac{-1}{p})$*$(\frac{5}{p})$ What i know: $(...
0
votes
1answer
51 views

how to determine $x^2 \equiv a \pmod m$ solvable if m,a not coprime

I am reading books about Number theory now. It's hard to me. Seems I use quadratic residues to determine if $x^2 \equiv a\pmod m$, but I don't know how when m, a not coprime. More specifically, like: ...
0
votes
1answer
56 views

Legendre/Jacobi symbol, reciprocity laws etc.

Is there a good textbook that will help me understand the motivation for defining the Legendre symbol (and it's Jacobi generalization), and applications of them to number theory? I have a math degree ...
3
votes
3answers
217 views

Quadratic residues in finite field

For an integer $a$ and a finite field $F_{q}$ of odd order, what is the efficient algorithm to determine $a$ is Quadratic residue or not?
0
votes
2answers
44 views

For which primes $p$ is $-3\in Q_p$?

I'm really bad at doing these for some reason, just need some help, this is not a hw question. I just need to do these smaller problems to gain some understanding. For which primes $p$ is $-3\in Q_p$ ...
1
vote
0answers
71 views

What is wrong with my proof of the law of quadratic reciprocity for the Jacobi Symbol?

With $n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$, both $a$ and $n$ as positive, odd integers, and defining the Jacobi symbol as (where on the right hand side we have the Legendre symbol): $$\left( \...
3
votes
1answer
55 views

How can I prove that $\left( \frac{5}{p} \right) = 1$ given that $p \equiv 1 \pmod{5}$ (where $\left( \frac{p}{q} \right)$ is the Legendre symbol)?

I know how to prove this using the law of quadratic reciprocity, but the book suggests proving $(c^4 + c)^2 + (c^4 + c) - 1 = 0$, using $c \in (\mathbb{Z}/p\mathbb{Z})^*$ such that $c^5 \equiv 1 \pmod{...
5
votes
1answer
74 views

Reference request for text containing proof of quadratic reciprocity law over function fields

While I have found a number of sources online (e.g. this) that prove the law of quadratic reciprocity for polynomials over finite fields, I am looking for a book on the subject or at least has a ...
5
votes
3answers
266 views

If $p\mid (3^n+1)$, then $p\equiv 1\pmod{3}$

Show that if $p> 2$ is a prime, $n > 1$ is odd and $p\mid (3^n+1)$, then $p\equiv 1\pmod{3}$. Since $n$ is odd, we have $3^{n+1} \equiv -3 \pmod{p}$ is a quadratic residue. Then I thought ...
0
votes
0answers
52 views

Proofs regarding cubic reciprocity

How do I go about these proofs? I can't find much online about cubic reciprocity. Suppose $p \geq 5$. If $p \equiv 1, 7 \pmod{12} $, then the number of distinct nonzero cubic residues (mod p) is $(p-...
1
vote
1answer
38 views

Quadratic residues mod 100000

I was trying to solve a problem and it reduced to proving that none of the numbers $19910,19911,19912,...,19919$ were quadratic residues$\mod 10^5$. I found that the only quadratic residue mod 100 in ...
0
votes
2answers
83 views

How do I use the Law of Quadratic Reciprocity to solve a congruence?

If I have a congruence like the following: $$3x^2 + 5x + 1 \equiv 0 \pmod{q}$$ How would I use the law of quadratic reciprocity to determine if it has a solution? I really have no idea where to go ...
1
vote
1answer
53 views

Show that set of reduced residue classes is a subgroup of the multiplicative group of reduced residue classes

Let m $\in Z^+$ and let G denote the set of those residue classes a(mod m) such that $a^\frac{m-1}{2} = \left(\frac{a}{m}\right)$ (mod m). Show that if a $\in$ G and b $\in$ G then ab $\in$ G. Also ...
0
votes
2answers
199 views

For any prime $p$ of the form $4k + 3$, prove that $x^2 + \frac{p+1}{4} \equiv 0 \;(\text{mod }p)$ is not solvable

I tried using quadratic reciprocity to simplify $$\left(\frac{-\frac{p+1}{4}}{p}\right)$$ and tried replacing $p$ by $k$ $(\text{as in}\, p = 4k + 3)$, but don't know how to proceed after that.
1
vote
0answers
46 views

Why $\sqrt p \in\mathbb Q(\xi_p)$?

If $p\equiv 1 \, \mathrm {mod} \, 4$ is a prime, then $\sqrt p \in\mathbb Q(\xi_p)$ where $\xi_p$ is the $p$-th root of unity. How to prove the above claim? (I need this fact to prove quadratic ...
1
vote
1answer
96 views

Prove that the Zolotarev symbol is the same as Legendre and Jacobi symbols

There are only a handful of resources that discuss the Zolotarev proof of the quadratic reciprocity law. Let $n \in \mathbb{Z}$, $a \in \mathbb{Z}/n\mathbb{Z}$, and $(a, n) = 1$. We can define a ...
3
votes
1answer
63 views

Solve $ x^2 \equiv 3 \pmod {10007}$ using quadratic reciprocity

I am trying to find whether there is a solution to: $$ x^2 \equiv 3\pmod {10007}$$ So I used quadratic reciprocity and found $$ \left( \frac{3}{10007}\right) \left( \frac{10007}{3}\right) = (-1)^{\...
0
votes
1answer
135 views

$n^6$ does not divide $6^n$

Find the number of positive integers $n=2^a3^b\, \, (a,b\geq 0)$ such that $n^6$ doesn't divide $6^n$. I have not encountered such types of question before and so I donot know how to even approach ...
0
votes
0answers
100 views

Using Gauss's Lemma to determine primes of a quadratic residue

The problem I'm attempting to solve is: Apply Gauss's Lemma to determine the primes of which -2 is a quadratic residue. I'm completely lost.
1
vote
0answers
101 views

$2$ is a primitive root of $p = 2q+1$ when $p = 8t+3$

I'm working through exercises in Ireland & Rosen textbook. I'm having trouble understanding the idea behind Exercise 4.7: Suppose that $p$ is a prime of the form $8t + 3$ and that $q = (p - 1)/...
1
vote
1answer
45 views

Relation between reciprocity laws and split places

Let $F$ be a (totally real if necessary) number field and $E$ a (totally imaginary if necessary) quadratic extension of $F$. Why are half the places of $F$ split in $E$? I mainly do not grasp the ...
-1
votes
1answer
54 views

Show that for any prime p, there are integers $x, y$ such that $p| x^2+y^2+1$ [closed]

Show that for any prime p, there are integers $x, y$ such that $p\mid x^2+y^2+1$
-2
votes
2answers
182 views

show that if p is a prime divisor of $839$ and $(5/p)=1$ then $839$ is a prime number [closed]

Show that if p is a prime divisor of $839$ = $38^2$ - $5*11^2$ then $(5/p)=1$. Use this fact to conclude that $839$ is a prime number.
3
votes
1answer
78 views

Show that if $x^2 + y^2 = z^2$, then at leeast one of x and y is a multiple of 3.

Show that if $x^2 + y^2 = z^2$, then at least one of $x$ and $y$ is a multiple of 3. Attempt: Given $x,y,z$ is pyhagorean triple, $$ x^2+y^2=z^2. $$ Assume neither $x$ nor $y$ is divisible by $3$. ...
0
votes
1answer
137 views

Properties of Legendre Symbols and Quadratic Reciprocity

I'm still a little bit confused about solving these types of problems. I have the formulas but still not able to apply them properly: Use properities of the legebdre symbol and quadratic reciprocity ...
-1
votes
2answers
70 views

Solving Congruency Using Quadratic Reciprocity

Use quadratic reciprocity to show that if p is an odd prime different from 5, then 5 is a quadratic residue (mod p) if and only if p $\equiv\pm$ 1 (mod 5).
3
votes
1answer
268 views

Find all primes $p$ so that 3 is a quadratic nonresidue modulo $p$

I know how to find the quadratic residues modulo a fixed $p$, but I'm not sure how to find all the primes such that an integer, such as 3, is a quadratic nonresidue modulo $p$.
1
vote
2answers
227 views

Show that $\left(\frac{2}{p}\right) = \large(-1)^{\frac{p^2-1}{8}\large}$

I'm working on the following problem that is using the Legendre Symbol: Show that $$\left(\frac{2}{p}\right) = \large(-1)^{\frac{p^2-1}{8}\large}$$ So I know that $\left(\frac{2}{p}\right) = \left\{ ...
0
votes
2answers
182 views

Use the Law of Quadratic Reciprocity and the Chinese Remainder Theorem to determine when $6$ is a quadratic residue modulo $p$.

I'm working on the following problems concerning quadratic reciprocity. a) Use the Law of Quadratic Reciprocity and the Chinese Remainder Theorem to determine for which primes $p$, $-50$ is a ...
1
vote
1answer
51 views

$\sum_{i=1}^{[ a/2]} [\frac {ib}{a} ] + \sum_{i=1}^{[ b/2]} [\frac {ja}{b} ] = [a/2][b/2] + [(a,b)/2].$

Show that if $a$ and $b$ are positive integers then $$\sum_{i=1}^{[ a/2]} [\frac {ib}{a} ] + \sum_{i=1}^{[ b/2]} [\frac {ja}{b} ] = [a/2][b/2] + [(a,b)/2].$$ I was trying by taking cases with ...