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)

learn more… | top users | synonyms

1
vote
1answer
16 views

Is there a general method to solve diophantine equations of the form $x^2+Ay=C$

For example $$x^2+7y=9$$I'm thinking something maybe along the lines of Pell's equation but not sure. Any help appreciated, been several years since I've last dealt with Pell equations and quadratic ...
1
vote
1answer
36 views

Prove that p is a quadratic residue mod $\frac{p^2+3p-2}{2}$

Let p be a prime number. Suppose that $q = \frac{p^2+3p-2}{2}$ is also a prime number. Prove that there is some integer $x$ so that $x^2 \equiv p$ (mod q). I assume I'm supposed to use quadratic ...
1
vote
2answers
37 views

For which primes $p\not=2$ is $5$ a square mod $p$?

For which primes $p\not=2$ is $5$ a square mod $p$? Using the Legendre symbol, $5$ is a square modulo $p$ if $$\left(\frac{5}{p}\right)=5^{\dfrac{p-1}{2}} \equiv 1 \pmod{p}$$ Now we have ...
1
vote
1answer
22 views

let $q$ be a prime of the form $q=3r+1$ and assume that $p=4q+1$ is also a prime. Show that $3$ is a primitive root of $p$

How to even begin? The proof for if $p$ is an odd prime then $(\frac{2}{p})=(-1)^{\frac{p^{2}-1}{8}}$ seems useful but not sure how to adapt it
1
vote
2answers
29 views

Help solving a question using Quadratic Reciprocity?

How do i solve this equation using Quadratic reciprocity? How many solutions does the quadratic equation $\bar{x}^{2} = \bar{2}$ have in $\mathbb{Z}_{47}$? I have no idea how to go about this i ...
2
votes
1answer
77 views

Prove that a perfect square (also a perfect square backwards) is divisible by 121

Suppose that $n=x^2$ is a perfect square with an even number of base-10 digits. Assume that when n is written backwards, you get another perfect square $y^2$. Prove that 121|n. (Use the mod 11 ...
1
vote
2answers
35 views

If p is a prime with p > 5, then 5 is a quadratic residue modulo p if and only if the last decimal digit of p is 1 or 9.

Use the law of quadratic reciprocity to show that if p is a prime with p > 5, then 5 is a quadratic residue modulo p if and only if the last decimal digit of p is 1 or 9. So far, I got x$^2$ = 5(mod) ...
0
votes
0answers
37 views

Calculate $(\frac{3}{11})$ in the following ways…

Evaluate $(\frac{3}{11})$ Currently going through a study set on a Quadratic Reciprocity, I have to evaluate $(\frac{3}{11})$ in the following three ways: (1) Computing the squares modulo 11 (2) ...
1
vote
0answers
10 views

Finding a prime in range with the largest minimal non quadratic residue

Given k, I'm trying to find the k-bit prime that has the largest minimal non-quadratic residue. I was wondering if there's any construction like that. Perhaps some use of the CRT?
1
vote
1answer
21 views

Let p be an odd prime with $(a,p) = 1$ and $(\frac{a}{p})$ = 1. show that $x^2$ ≡ a (mod p)

Let p be an odd prime with $(a,p) = 1$ and $(\frac{a}{p})$ = 1. show that $x^2$ ≡ a (mod p) has precisely two incongruent solutions mod p. Having a bit of trouble with this question, we are ...
3
votes
1answer
51 views

Is $x^2 ≡ 295$ (mod 2717) solvable?

Is $x^2 ≡ 295$ (mod 2717) solvable? -Having a tough time with this problem, currently covering a section on Quadratic Reciprocity Law of Gauss. After coming back to my professor, his hint was to ...
2
votes
3answers
35 views

For what odd prime p is -3 a quadratic residues? Non-residue?

For what odd prime p is -3 a quadratic residues? Non-residue? Having a bit of trouble with this question, we are currently covering a section on quadratic reciprocity and didn't really see anything ...
1
vote
0answers
63 views

Are there infinitely many pairs of primes, $p$ and $q$, such that $q = 4p + 1$?

How close can one come to proving that there are infinitely many primes, $p$ and $q$, such that $q = 4p + 1$? The idea for this question came from reading the question and answers posed by ...
1
vote
2answers
69 views

Quadratic reciprocity: Tell if $c$ got quadratic square root mod $p$

I am reading the wiki article about Quadratic reciprocity and I don't understand how can I tell if some integer $c$ got quadratic root mod $p$? So far I am using brute search to find $y$ such that ...
2
votes
0answers
38 views

Fermat's little theorem and Euler's criterion

Is it possible to find the solution of this congruence by Fermat's little theorem and how ? $$15125^{2401}\pmod {72}$$ Can somebody tell me how to do it by Euler's criterion?
0
votes
2answers
40 views

Quadratic Reciprocity and Congruences

I have to find the result of congruences : $$(a)\left(\frac{34}{73}\right)$$ $$(b)\left(\frac{36}{73}\right)$$ $$(c)\left(\frac{1356}{2467}\right)$$ By the way,I found that Theorem of Quadratic ...
0
votes
1answer
20 views

If $p>3$ and $x^2+3y^2=p$, prove $\left(\frac{-3}{p}\right)=1$ and $p\equiv 1\pmod{6}$.

If $p>3$ and $x^2+3y^2=p$, prove $\left(\frac{-3}{p}\right)=1$ and $p\equiv 1\pmod{6}$. $$\left(\frac{-3}{p}\right)=\left(\frac{-1}{p}\right)\left(\frac{3}{p}\right)$$ We know that ...
1
vote
1answer
23 views

Quadratic congruence with linear term

I'm trying to determine whether the congruence $x^2+x-1\equiv0\pmod{61}$ has a solution. I know how to do this without the linear term, for instance, $x^2-5\equiv0\pmod{61}$. I can solve it just by ...
7
votes
0answers
121 views

Irreducibility in a polynomial related to quadratic residues

From Romania TST 2004 Day 5 P3, I was introduced to the polynomial $$f(x)=\sum_{i=1}^{p-1} \left( \frac{i}{p} \right)x^{i-1}$$ This polynomial is clearly not irreducible - $x=1$ is a root. Even more ...
3
votes
1answer
42 views

Let $p> 7$, prove that $\left(\frac{2}{q}\right) = (-1)^{\frac{q^2-1}{8}}$ with $q$ an odd prime

Let $p> 7$, prove that $\left(\frac{2}{q}\right) = (-1)^{\frac{q^2-1}{8}}$. with $q$ an odd prime. We can by using the following verifications: $$\left(\frac{2}{p}\right) = ...
2
votes
1answer
71 views

If $n\in\Bbb Z^+$ is not a square, prove exist infinitely many primes $p$ such that $\left(\frac{n}{p}\right)=-1$.

If $n\in\Bbb Z^+$ is not a square, prove exist infinitely many primes $p$ such that $\left(\frac{n}{p}\right)=-1$. Note that if $p\nmid n$ and $n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots ...
1
vote
1answer
31 views

Prove that $\sum^{P}_{k=1} \lfloor\frac {ka}{p}\rfloor = \frac{p^{2} - 1}{8} + \mu(a,p)$ mod$(2)$

I can prove that $\sum^{P}_{k=1} \lfloor\frac {ka}{p}\rfloor = \mu(a,p)$ mod$(2)$ where $p$ is an odd prime, $P = \frac {p-1}{2}$, $a$ is an integer not divisible by $p$, and $\mu(a,p)$ is the ...
1
vote
2answers
55 views

verify if $8x^2 - 2x - 3 \equiv 0 \pmod{75}$ has solutions or not.

verify if $8x^2 - 2x - 3 \equiv 0 \pmod{75}$ has solutions or not. I tried to write the left term in a form $y^2 \equiv a \pmod{75}$, where $a \in \mathbb{Z}$ so then I can use quadratic repriocity ...
0
votes
0answers
24 views

Missing link in proof of quadratic reciprocity law

I am trying to figure out the proof of the quadratic reciprocity law in Serre's book A Course in Arithmetic. I think my question is possible to answer independent of the book though: Let $l$ and $p$ ...
4
votes
1answer
60 views

Gauss' original proof of quadratic reciprocity

Is the original proof of quadratic reciprocity due to Gauss available anywhere online? I've been looking for quite a while now, but with no results. Most papers seem not to include it because of it ...
3
votes
0answers
37 views

Technological incompetence [closed]

I am a high school student going into my junior year. Earlier this summer, I went to a math camp at Ohio State University, and one of the assignments was to prove quadratic reciprocity. I was told ...
1
vote
1answer
31 views

Quadratic reciprocity in the case $a=-1$

I am reading the proof the for odd prime $p$, $$ \left ( \frac{-1}{p} \right)_2 = (-1)^{\frac{p-1}{2}} = \begin{cases} 1 \hspace{2mm} \text{for} \hspace{2mm} p \equiv 1 \operatorname{mod} 4 \\ -1 ...
0
votes
1answer
32 views

Verifying quadratic reciprocity for the Jacobi symbol

I am trying to prove: If $m,n$ are odd coprime positive integers, then $$\Big(\frac mn\Big)\Big(\frac nm\Big)=(-1)^{\large\frac{m-1}2\frac{n-1}2},$$ where $\big(\frac mn\big)$ is the Jacobi ...
1
vote
1answer
58 views

What is the probability of having a quadratic residue?

Let $a$ be a random integer and $p$ be a prime. What is the probability of $\left(\frac{a}{p}\right)=1$, as $p$ goes to infinity. And similarly, what about $\left(\frac{a}{p}\right)=-1$ or $0$?
3
votes
2answers
74 views

Describe all odd primes p for which 7 is a quadratic residue

I need to describe all odd primes $p$ for which $7$ is a quadratic residue. Now let $\left(\frac{a}{b}\right)$ be the Legendre Symbol. Then if $7$ is a quadratic residue $p$ we must have: ...
1
vote
2answers
34 views

quadratic reciprocity

I know $x^2\equiv-7\pmod7$ has solutions. How can I check if $x^2\equiv-7\pmod{49}$ has solutions? I know $-7\equiv42\pmod{49}$ but $49$ isn't a prime so I can't use Euler's criterion. How shall I do ...
-1
votes
2answers
45 views

When is $2$ a quadratic residue mod $p$?

For which prime numbers $p$ is $2$ a quadratic residue modulo $p$. I know that $2$ is a quadratic reside iff $$2^{\frac{p-1}{2}} =1 \; \bmod \;(p) $$ so $$2^{p-1} =1 \; \mod \; (p). $$ But I ...
4
votes
1answer
82 views

Describe the set of odd primes such that $\left(\frac{-5}{p}\right) = 1$ (Legendre Symbol)

Okay, so $\left(\frac{-5}{p}\right) = 1$. I am assuming that I can start this by saying $\left(\frac{-5}{p}\right) = \left(\frac{5}{p}\right) \times \left(\frac{-1}{p}\right)$. There are well ...
6
votes
2answers
63 views

Quadratic Reciprocity

I've been asked to see if $x^2\equiv83$ $(\mathrm {mod} \ 101^{2000})$ has solutions. Now I know $x^2\equiv(\mathrm{mod} \ 101)$ has no solutions since the quadratic reside symbol ...
0
votes
1answer
53 views

Calculating the Legendre symbols $\left(\frac{295}{401}\right)$ and $\left(\frac{713}{1009}\right)$ using quadratic reciprocity

Evaluate the following Legendre symbols using quadratic reciprocity: $\left(\frac{295}{401}\right)$ $\left(\frac{713}{1009}\right)$ I know that can flip the numbers and reduce because both $401$ ...
1
vote
2answers
56 views

Find conditions for $\left(\frac{-3}{p}\right)=1$

$\left(\frac{-3}{p}\right)=\left(\frac{-1}{p}\right)\left(\frac{3}{p}\right)=\left(\frac{-1}{p}\right)\left(\frac{p}{3}\right)^{\frac{p-1}{2}}$ $=\begin{cases}1,\:p\equiv 1\pmod{4}\text{ or ...
0
votes
1answer
49 views

Find all primes $p$ such that $\left( \frac{-19}{p} \right) = 1$

Find all primes $p$ such that -19 is a quadratic residue $\bmod p$. solution: We have that $(\frac{-19}{p})=(\frac{p}{19})$, so that if $-19$ is a quadratic residue modulo $p$, then $p$ is a ...
3
votes
1answer
42 views

What is $\left[\frac{1}{2}(p-1)\right]! \;(\text{mod } p)$ for $p = 4k+1$?

Theorem #114 in Hardy and Wright says if $p = 4k+3$ then $$ \left[\frac{1}{2}(p-1)\right]! \equiv (-1)^\nu \mod p$$ where $\nu = \# \{ \text{non residues mod } p\text{ less than }p/2\}$. Is ...
0
votes
2answers
28 views

Quadratic reciprocity: $\left( \dfrac{-1}{p}\right) = (-1)^{\frac{p-1}{2}}$

Prove $\left( \dfrac{-1}{p}\right) = (-1)^{\frac{p-1}{2}}$, where $p$ is an odd prime, and the LHS is the legendre symbol. I've got $-1 = x^2 \pmod p \implies (-1)^{\frac{p-1}{2}} = x^{p-1} = 1 = ...
1
vote
2answers
97 views

Different formulations of the Law of Quadratic Reciprocity

The law of quadratic reciprocity is given as: $(\frac{p}{q})(\frac{q}{p}) = (-1)^{((p-1)/2)((q-1)/2)}$ Apparently we can say: $(\frac{p}{q}) = (\frac{q}{p})(-1)^{((p-1)/2)((q-1)/2)}$ and ...
0
votes
0answers
24 views

If $S=\sum (\frac{n}{p})\zeta^n$ then how to prove that $S^2=(\frac{-1}{p})p$? [duplicate]

Here $\zeta$ is a primitive $n$-th root of unity and ($\frac{n}{p}$) denotes the Legendre symbol. Can someone please give a proof of this fact? I tried writing $S^2$ as the product of two sums $S=\sum ...
1
vote
1answer
126 views

Determining prime numbers p which satisfy quadratic residues modulo p

I'm learning about quadratic reciprocity and I'm stuck on an exercise. It states : Determine the congruence characterizing all prime numbers p for the following integers such that they are quadratic ...
1
vote
1answer
33 views

Proof on the Legendre Symbol

I'm working on an exercise involving the Legendre Symbol. It gives me a hint but I'm not sure how to prove it. Let p and q be odd prime numbers with $p = q + 4a$ for some $a \in \mathbb{Z}$. Prove ...
0
votes
2answers
54 views

Find all primes $p > 11$ such that $11$ is a quadratic residue $\pmod p$.

Find all primes $p > 11$ such that $11$ is a quadratic residue $\pmod p$. (The answer should be in terms of congruence conditions mod a certain number.) I believe that we need to find all primes ...
1
vote
1answer
37 views

Equivalent statement to Quadratic reciprocity

One corollary of quadratic reciprocity is that $(\frac{p}q)$ depends only on the equivalence class of $q$ modulo $4p$. Is this enough to derive quadratic reciprocity. While equivalent does not really ...
1
vote
1answer
48 views

Computing Jacobi symbol $\left(\frac{47}{109}\right)$

Compute the Jacobi symbol $\left(\frac{47}{109}\right)$ using multiplicativity and quadratic reciprocity ...
1
vote
1answer
56 views

A conjecture about quadratic residues given $p \equiv 5 \pmod 8$

Original Problem $p$ is a prime that is congruent to $5$ modulo $8$ and $a$ is a quadratic residue modulo $p$. Prove that excactly one of $x_1=a^{\frac{p+3}{8}},x_2=(2a)(4a)^{\frac{p-5}{8}}$ is the ...
0
votes
1answer
35 views

For which primes $p$ does $x^2\equiv3\pmod{p}$ have a solution?

attempt at solution: using Legendre symbol, what I did was notice that the equation has a solution if ($3/p$)=1 IFF ($p/3$)x(-1)^(p-1)/2 = 1 So, can I say that p has to satisfy two properties (4 ...
1
vote
0answers
32 views

Averages of $L(1,\chi)$

Let $(\frac{m}{n})$ denote the usual quadratic Jacobi symbol and $\mu(n)$ be the Moebius function. The series $$ \sum_{\substack{m,n \in \mathbb{N} \\ m,n\equiv 1 \mod{4}}} ...
0
votes
2answers
65 views

Evaluating quadratic residue $(6/p) $

Evaluating quadratic residue $(6/p) $ I want to find for which numbers mod 6 this residue is equal to 1 and for which it's equal to -1. I've tried splitting it into $(3/p)(2/p)$ and expressing it as ...