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
1 vote
1 answer
53 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?
stripe9420's user avatar
0 votes
1 answer
97 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^...
jibber032394's user avatar
1 vote
1 answer
231 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 ...
Tejas Rao's user avatar
  • 1,890
2 votes
0 answers
73 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+...
Tejas Rao's user avatar
  • 1,890
4 votes
1 answer
197 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$ ...
Yes it's me's user avatar
  • 1,854
2 votes
1 answer
74 views

Using quadratic residues and/or reciprocity to prove relative primality?

I have odd positive integers $q$ and $y$, with $3q^2 < y^2 < 4q^2$, such that the following are true: \begin{align} (q^2+9) &\mid (y^2+5)(y^2+29) \\[0.25em] (q^2+2) &\mid (y^2+1)(y^...
Kieren MacMillan's user avatar
2 votes
1 answer
80 views

Trial Division and Quadratic Reciprocity

I am reading The Joy of Factoring by Samuel Wagstaff and I am having trouble understanding a paragraph from this book. It says the following One can use quadratic residues to speed Trial Division ...
ElPerroBermudez's user avatar
0 votes
2 answers
66 views

Reciprocal of Quadratic Equation

How can we prove there are infinitely many solutions to $\frac{1}{x^{2}-2x+3}=y$ by only staying at Further maths at High School level? Will the graph ever go below the x-axis or will stay on it. ...
Haroon Arfan's user avatar
12 votes
2 answers
3k views

What is the intuition behind the law of quadratic reciprocity?

Law of quadratic reciprocity states as follows: Law of quadratic reciprocity — Let $p$ and $q$ be distinct odd prime numbers, and define the Legendre symbol as: $$ \left(\frac {q}{p}\right)=\left\{\...
Bach's user avatar
  • 5,730
0 votes
0 answers
86 views

Reference Request: Cubic and Biquadratic Reciprocity Law

I want to read about the Cubic and Biquadratic Reciprocity Laws after learning the Quadratic Reciprocity Law. I already know about Franz Lemmermeyer's book "Reciprocity Laws", but I think this is a ...
3nondatur's user avatar
  • 4,182
2 votes
0 answers
99 views

Applications of higher order reciprocity laws

I'm currently studying quartic & cubic residues and their reciprocity laws, and would like to know of any real world applications to finding the values of their respective residue symbols. I ...
MNic's user avatar
  • 31
1 vote
1 answer
56 views

A number theory problem: show $N_{x^2−n}(p^k) = 2$ for all $k = 1,2,3,...$

One of my number theory exercises this week asks the following: Let $n$ be an odd natural number and assume that the Legendre symbol $\left(\frac np\right)$ equals $1$ for some prime $p>2$. ...
nik's user avatar
  • 65
4 votes
1 answer
259 views

Jacobi Symbol: $\sum_{n=1}^{p}\left(\sum_{m=1}^{h}\left(\frac{m+n}{p}\right)\right)^2=h(p-h)$

Show that if $p$ is and odd prime and $h$ is an integer, $1\le h \le p$, then $$\displaystyle\sum_{n=1}^{p}\left(\sum_{m=1}^{h}\left(\frac{m+n}{p}\right)\right)^2=h(p-h)$$ where $\left(\frac{m+n}{p}\...
user avatar
5 votes
1 answer
274 views

A prime number is not a quadratic residue modulo some prime without quadratic reciprocity

In Cox's book "Primes of form $x^2 + ny^2$", I stumbled upon a lemma $ \newcommand{\Z}{\mathbb{Z}} $ Lemma 1.14: If $D \equiv 0,1 \pmod{4}$ is a nonzero integer, then there is a unique homomorphism ...
Kolja's user avatar
  • 2,750
1 vote
1 answer
96 views

quadratic residue such as "$(n|p)= -1$"(quadratic reciprocity)

(Note: (n|p)=1 is legendre-symbol.) So need to find primes where $(n|p)=1$ So we have 1- $1\pmod 4$ where we use quadratic residue of $n$ along with $\pmod n$ to find solutions. 2- Then we have $3\...
tt z's user avatar
  • 129
4 votes
1 answer
123 views

How to evaluate $\prod_{n=1}^{p-1} \sin(\frac{2n^2\pi}{p})$

According to Quadratic Gauss sum I want to know what is the exact value of this product?,since I put this product on Wolfram Alpha and I got the result in this form $$\frac{a+b\sqrt{ p}}{c}$$ for some ...
Unik Sillavich's user avatar
0 votes
0 answers
73 views

"Inverting" the Artin map in terms of characters

I will start by saying that I know very little about Class Field Theory, so I am hoping for someone to shed some light on this. If $K$ is a finite abelian extension of $\mathbb{Q}$, then one can ...
kaedit's user avatar
  • 651
0 votes
1 answer
129 views

Assume that p and q are odd primes and $p \equiv q \pmod {28}$. Show that $(\frac{7}{p}) = (\frac{7}{q})$.

Assume that p and q are odd primes and $p \equiv q \pmod {28}$. Show that $(\frac{7}{p}) = (\frac{7}{q})$. Could anyone give me a hint for the solution please?
Intuition's user avatar
  • 3,367
-1 votes
1 answer
90 views

Why if the Legendre symbol satisfy $\left(\frac{a}p\right)=\left(\frac{p}a\right)$ then $\left(\frac{a}p\right) = 1$?

Sorry for my stupid question: This is in completion to this question Let $p$ be a prime of the form $p = a^2 + b^2$ with $a,b \in \mathbb{Z}$ and $a$ an odd prime. Prove that $(a/p) =1$ Why if the ...
Intuition's user avatar
  • 3,367
1 vote
1 answer
49 views

Question on modular arithmetic with prime numbers

Let $p\neq3$ be a prime conguent to $3\pmod4$ and let $q$ be a prime divisor of $(12p)^{2019}+1$ satisfying $q\equiv p^2+1\pmod{3p}$. Determine $q\pmod 4$. I tried solving the problem as follows. ...
bitsbit's user avatar
  • 429
0 votes
1 answer
49 views

Proving that $n$ is not a prime [duplicate]

Let $n=3^{100}+2$ and assume that $X^2-53$ does not have zeroes in $\mathbb{Z}/ n\mathbb{Z}$. Show that $n$ is not a prime. I tried solving this problem by assuming that $n$ is a prime (in order to ...
bitsbit's user avatar
  • 429
2 votes
1 answer
68 views

Solution to equation modulo p [duplicate]

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 ...
limeeattack's user avatar
2 votes
1 answer
316 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 ...
Tychonoff3000's user avatar
4 votes
1 answer
194 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\...
rmdmc89's user avatar
  • 9,939
2 votes
0 answers
64 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$, ...
J. Linne's user avatar
  • 3,007
3 votes
1 answer
119 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_{...
user avatar
3 votes
1 answer
243 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 ...
Mee98's user avatar
  • 1,133
2 votes
1 answer
80 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)...
Mjoseph's user avatar
  • 989
8 votes
1 answer
283 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 ...
Anubhab's user avatar
  • 2,008
12 votes
0 answers
351 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}$. ...
Seewoo Lee's user avatar
  • 15.1k
5 votes
1 answer
130 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 ...
john takeuchi's user avatar
0 votes
1 answer
199 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,,
Maged Saeed's user avatar
  • 1,140
2 votes
2 answers
363 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 ...
Mjoseph's user avatar
  • 989
2 votes
2 answers
398 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}{...
Hidaw's user avatar
  • 971
2 votes
1 answer
207 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)\...
cactus314's user avatar
  • 24.4k
2 votes
1 answer
96 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}^{...
J. Linne's user avatar
  • 3,007
2 votes
1 answer
384 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 ...
Algebear's user avatar
  • 1,674
1 vote
1 answer
289 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.
J. Linne's user avatar
  • 3,007
4 votes
2 answers
2k 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 ...
J. Linne's user avatar
  • 3,007
-2 votes
1 answer
146 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. ...
박윤수's user avatar
4 votes
1 answer
179 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 ...
the man's user avatar
  • 2,394
1 vote
3 answers
181 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{...
Matthijs Bjornlund's user avatar
0 votes
0 answers
60 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 ...
Sohail Abdul Karim's user avatar
0 votes
0 answers
55 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$ (...
Rose's user avatar
  • 289
2 votes
1 answer
680 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 ...
mathcourse's user avatar
1 vote
1 answer
53 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+...
S34717's user avatar
  • 11
1 vote
1 answer
53 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?
user7802048's user avatar
  • 1,265
1 vote
1 answer
180 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 ...
Ansel Fu's user avatar
0 votes
1 answer
706 views

If $p$ and $q$ are primes of the form $4k+3$, and $x^2 \equiv p \pmod q$ has no solutions, show $x^2 \equiv q \pmod p$ has two incongruent solutions

Prove or disprove: If $p$ and $q$ are primes of the form $4k+3$, and $x^2 \equiv p \pmod q$ has no solutions, show $x^2 \equiv q \pmod p$ has two incongruent solutions I think it is a true ...
dr.rise's user avatar
  • 619
15 votes
2 answers
2k 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 ...
David Reed's user avatar
  • 3,255