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
4
votes
2answers
62 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
56 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
78 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
63 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
125 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
50 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
42 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
45 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
65 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+...
2
votes
1answer
102 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
59 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
46 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
37 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
23 views

Show $\chi_{\pi}\left(a(-1)^\frac{p-1}{4}\right)=(-1)^\frac{a^2-1}{8}.$

I'm currently going through of Ireland and Rosen's 'A Classical Introduction to Modern Number Theory' and would like some help on CH9Ex29. I know that $a(-1)^\frac{p-1}{4}$ is primary (i.e it is ...
0
votes
0answers
37 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
21 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
46 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
44 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}\...
4
votes
1answer
93 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
69 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
105 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
51 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
73 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
67 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
52 views

Exponentiation with odd number in modular arithmetic

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
42 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
45 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
38 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
91 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
51 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
18 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
64 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
216 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
50 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
1answer
196 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
0answers
269 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
108 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
78 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
85 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
370 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
74 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
68 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
132 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
139 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
2answers
468 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
112 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
88 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
86 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
48 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
46 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
2 3 4 5