Stack Exchange Network

Stack Exchange network consists of 175 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)

2
votes
1answer
31 views

Solution to equation modulo p

Under the assumptions that $$p\cong 1 \mod 5$$ and $$g = 2(c+c^{-1})+1$$ where $c$ has order $5$ modulo $p$. I need to show that $g^2 \cong 5 \mod p$. I have that $$g^2=4(c^4+c^3+c^2+c)+9$$ I know ...
2
votes
1answer
36 views

Quadratic reciprocity in Langlands program

I know quadratic reciprocity is the easiest example of langlands correspondence. Langlands correspondence gives some relation between automorphic forms and artin representations. My question is: what ...
1
vote
1answer
24 views

Quadratic reciprocity and decomposition of primes in cyclotomic fields

In Neukirch's Algebraic Number Theory, there is a proof of the quadratic reciprocity which makes use of proposition $10.5$: $$p\text{ is totally split in }\mathbb{Q}(\sqrt{\ell^*})\Leftrightarrow p\...
2
votes
0answers
8 views

Generalization of Jacobi symbol for composite $n$

Suppose $n$ and $m$ are relatively prime integers. Define the symbol (sort of like the Jacobi symbol) U$(n,m)=1$ if and only if each prime $p|n$, there is an integer $k$ such that $n^k = p\pmod m$, ...
3
votes
1answer
53 views

A Fibonacci Number problem(please help me that 1 answer is mine)

The Fibonacci sequence is defined as follows: $F_0=0$, $F_1=1$, and $F_n=F_{n-1}+F_{n-2}$ for all integers $n\ge 2$. Find the smallest positive integer $m$ such that $F_m\equiv 0 \pmod {127}$ and $F_{...
3
votes
1answer
189 views

Show that $n = 3^{100} + 2$ is not a prime number.

So I have to prove that $n = 3^{100} + 2$ is not a prime number while we assume that $X^2 - 53$ has no zeroes in $\mathbb{Z}/n\mathbb{Z}$. Because we are working with quadratic reciprocity in this ...
2
votes
1answer
43 views

Prove that if $a^{(n-1)/2}\equiv\pm1\pmod{n}$, then $\left(\frac{a}{n}\right)\equiv a^{(n-1)/2}\pmod{n}$

Let $a,n\ \in \mathbb Z$ and suppose that $n>1$ is odd, $n\equiv3\pmod{4}$, and that $\gcd(a,n)=1$. Prove that if $a^{(n-1)/2}\equiv\pm1\pmod{n}$, then $$\left(\frac{a}{n}\right)\equiv a^{(n-1)...
0
votes
0answers
24 views

Alternative formulation of quadratic reciprocity

I was reading a book on number theory and came across the following theorem. Theorem: Let $a$ be a positive integer and $p,q$ odd primes. 1) If $p \equiv q$ (mod $4a$), then $\left(\dfrac{a}{p}\...
6
votes
1answer
140 views

If $d$ divides $a^4+a^3+2a^2-4a+3$, prove that $d$ is a fourth power modulo $13$

If $d$ divides $f(a)=a^4+a^3+2a^2-4a+3$, prove that $d$ is a fourth power modulo $13$. $f(a)\equiv{(a-3)}^4\pmod {13}$. But how can we prove any divisor of $f(a)$ is a fourth power? If we prove that ...
11
votes
0answers
222 views

Is there a proof of quadratic reciprocity using $p$-adic numbers?

I know that the quadratic reciprocity can be regarded as a special case of Artin reciprocity (class field theory), and we can get it by considering the cyclotomic extension of $\mathbb{Q}_{p}$. ...
5
votes
1answer
72 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
56 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
67 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
335 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
43 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
49 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
101 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
83 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
175 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
57 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
57 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
51 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
45 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
36 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
87 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 ...
1
vote
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
42 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
84 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
247 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
338 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
107 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
69 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
275 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
76 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
56 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
85 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
275 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
57 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
49 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
134 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
72 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
263 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
56 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
132 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
67 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
155 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
104 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
116 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)/...