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)
272
questions
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?
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^...
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 ...
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+...
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$ ...
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^...
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 ...
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.
...
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\{\...
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 ...
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 ...
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$. ...
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}\...
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 ...
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\...
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 ...
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 ...
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?
-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 ...
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. ...
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 ...
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 ...
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 ...
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\...
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$, ...
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_{...
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 ...
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)...
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 ...
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}$. ...
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 ...
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,,
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 ...
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}{...
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)\...
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}^{...
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 ...
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.
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 ...
-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. ...
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 ...
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{...
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 ...
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$ (...
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 ...
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+...
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?
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 ...
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 ...
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 ...