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
0answers
31 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}\...
1
vote
0answers
82 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, $=\...
0
votes
1answer
74 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 ...
1
vote
3answers
50 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-...
1
vote
1answer
64 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)...
1
vote
1answer
98 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 ...
0
votes
1answer
39 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 ...
1
vote
1answer
40 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 ...
0
votes
1answer
83 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,...
2
votes
1answer
77 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 ...
1
vote
1answer
69 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 ...
0
votes
1answer
49 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 ...
0
votes
2answers
62 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)$ = $...
0
votes
2answers
61 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 ...
0
votes
1answer
55 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 ...
1
vote
1answer
105 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\...
1
vote
1answer
53 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 ...
4
votes
2answers
81 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 ...
2
votes
1answer
68 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 ...
4
votes
3answers
85 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....
2
votes
2answers
73 views

If $p\equiv 1 \;\text{mod}\; 3$, then show that one can find an integer $k$ satisfying $k^2-k+1=p\cdot M\;$ with $M<p$

If $p\equiv 1 \;\text{mod}\; 3$, then show that one can find an integer $k$ satisfying $k^2-k+1=p\cdot M\;$ with $M<p$ ($p$ is a prime) I don't have any clue on how to work this problem. Also, if ...
3
votes
2answers
306 views

When is $-3$ a quadratic residue mod $p$?

Going over a past exam in my elementary number theory course, I noticed this question that caught my attention. The question asked for the conditions that allowed $-3$ to be a quadratic residue mod $p$...
1
vote
1answer
52 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?
0
votes
1answer
45 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^...
0
votes
0answers
64 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 ...
2
votes
0answers
71 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+...
3
votes
1answer
141 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$ ...
2
votes
1answer
70 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^...
2
votes
1answer
57 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 ...
0
votes
2answers
43 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. ...
0
votes
0answers
50 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 ...
1
vote
0answers
28 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 ...
1
vote
1answer
51 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$. ...
4
votes
1answer
60 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}\...
5
votes
1answer
138 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 ...
1
vote
1answer
73 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\...
4
votes
1answer
115 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 ...
0
votes
0answers
59 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 ...
0
votes
1answer
104 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?
-1
votes
1answer
73 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 ...
0
votes
3answers
65 views

How to show $\,2^n \equiv 8\pmod{24}\,$ for odd $\,n\ge 3$?

Show that if $n\geq3$ is odd, then $2^n-1\equiv7\mod24$. I tried solving this backwardly. We want to prove that $2^3(2^{n-3}-1)=2^n-2^3\equiv0\mod24$. Since $\frac{24}{2^3}=3$, this leaves us to ...
1
vote
1answer
44 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. ...
0
votes
1answer
46 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 ...
2
votes
1answer
45 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
144 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 ...
2
votes
1answer
74 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
28 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
74 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
224 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
65 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)...

1
2 3 4 5