Skip to main content

Questions tagged [quadratic-residues]

An integer $a$ is a quadratic residue modulo $p$ if $a \equiv x^2 \pmod p$ for some integer $x$. If $a$ is not a quadratic residue modulo $p$, it is said to be a quadratic nonresidue modulo $p$.

Filter by
Sorted by
Tagged with
-3 votes
0 answers
47 views

How to prove $x^2 \equiv 567\pmod {625}$ has no solutions (i.e. 567 is not a quadratic residue)? [closed]

For small numbers like $x^2 \equiv 2 \pmod 7$ I could try to calculate every case. But what do I do if there are big numbers?
Radupp's user avatar
  • 1
-1 votes
0 answers
23 views

What condition on $r$ we need to have so that "If $a$ is a quadratic residue modulo p and $ab ≡ r \mod p$, then $b$ is quadratic residue modulo p" [duplicate]

when $r=1$, it's easy to prove the statement this way: $a \equiv b^{-1} \mod p \\ x^2 \equiv a \mod p\\ (xb)^2 = x^2b^2 \equiv ab^2 \equiv b^{-1}b^2 \equiv b \mod p$ Now, does it work when r is not $1$...
Abdulrahman Albeladi's user avatar
-2 votes
0 answers
28 views

Solving congruence for p [duplicate]

Any idea of how to solve the following congruence? $$5^{\frac{p-1}{2}} \equiv 1 \text{ (mod p)}$$ In fact, the whole question is to decide for which p does the Legendre symbol $$(\frac{5 \text{ mod p}}...
Marc's user avatar
  • 57
0 votes
1 answer
41 views

Determine the odd primes $p$ for which $−28$ is a quadratic residue $\bmod p$.

Determine the odd primes $p$ for which $−28$ is a quadratic residue $\bmod p$. (I've done something though I'm unsure if I'm working towards the correct answer. I have no solution for this.) When $...
Alex's user avatar
  • 3
2 votes
2 answers
171 views

There exists $a$ s.t the 2 equations both have integer solutions.

For each prime $p>5$, prove that there always exists an integer $a$ s.t the two following equations $$x^2+py+a=0\quad\text{and}\quad x^2+py+a+2=0$$ both have integer solutions. Here are my ...
Alex Nguyen's user avatar
  • 1,201
0 votes
0 answers
21 views

Show $\sum_{k=0}^{p-1} \left(\frac{k^2+1}{p}\right) = \sum_{t=0}^{p-1} \left(1 + \left(\frac{t}{p}\right)\right)\left(\frac{t+1}{p}\right)$ [duplicate]

Let $p$ be an odd prime. I wish to show that $$\sum_{k=0}^{p-1} \left(\frac{k^2+1}{p}\right) = \sum_{t=0}^{p-1} \left(1 + \left(\frac{t}{p}\right)\right)\left(\frac{t+1}{p}\right),$$ where the ...
V. Elizabeth's user avatar
0 votes
1 answer
70 views

Number of Solutions to $y^2 \equiv x^2 + 1 \pmod{p}$

Suppose $p$ is an odd prime. I wish to show that the number of solutions to $y^2 \equiv x^2 + 1 \pmod{p}$ is $$p + \sum_{k=0}^{p-1}\left(\frac{k^2 +1}{p}\right).$$ I know that, for any $a$, $y^2 \...
V. Elizabeth's user avatar
0 votes
0 answers
48 views

How to find all $p$ congruences such that $(\frac{-5}{p})$ are quadratic residues

I am self-studying number theory and came across the question asked by another user in this post here. Specifically part (b). My initial solution is to use the fact that the Legendre Symbol is ...
Gottfried Leibniz's user avatar
0 votes
0 answers
29 views

Do we need relative prime in the definition of a quadratic residue? [duplicate]

From my lectures I know that $a$ is a quadratic residue mod $m$ if there is a $b$ such that $b^2\equiv a \pmod m$. But in several book I now read that $a$ and $m$ have to be coprime. That would mean ...
Lereu's user avatar
  • 434
2 votes
2 answers
117 views

Prove that if $p \equiv 7 \pmod{8}$, the solutions to the congruence $x^2-34x+1 \equiv 0 \pmod{p}$ are both quadratic residues modulo p.

Consider the quadratic congruence \begin{equation} x^2-34x+1 \equiv 0 \pmod{p}, \end{equation} where $p \equiv 7 \pmod{8}$. There are two solutions, since we can write it as \begin{equation} (x-17)^2 \...
J. Miarecki's user avatar
1 vote
0 answers
31 views

Congruences of partitions and Legendre symbol.

Let $(\frac{a}{p})$ denote the Legendre symbol, and let $\psi(q)=\sum_{n\geq 0} q^{n(n+1)/2}$. We define Ramanujan's general theta function $f(a,b)$ for $\mid ab \mid <1$ as $$ f(a,b)=\sum_{n=-\...
Adam's user avatar
  • 21
0 votes
0 answers
9 views

Notation for modular in proof that $n$ is a perfect square iff jacobisymbol $J(a,n)\neq -1$ for all $a$

I want to proof the following: Let $\left(\frac{a}{n}\right)$ denote the Jacobisymbol of $a$ and $n$. Then I want to show that $n$ is a square $\Leftrightarrow \left(\frac{a}{n}\right) \neq -1 \forall ...
Lereu's user avatar
  • 434
-1 votes
2 answers
97 views

prove for Jacobi symbols $\sum_{k=0}^{500}(\frac{k}{1001}) = 0$ [closed]

Could somebody help me prove that $\sum_{k=0}^{500}\left(\dfrac{k}{1001}\right) = 0$? I think that there might be a bijection with $\sum_{k=0}^{500}\left(\dfrac{k}{501}\right)$ but I don't know how to ...
uuio's user avatar
  • 19
0 votes
0 answers
40 views

Strategies for Proving a Summation Formula Involving Quadratic Residues Modulo Prime Numbers

I've recently been delving into summation formulas involving quadratic residues modulo prime numbers and am seeking strategies or insights for a formal proof. Thus far, my efforts have focused on ...
TibetanFox's user avatar
1 vote
0 answers
38 views

When is $(m+1)/2$ a quadratic residue mod $m$?

The motivation here comes from this MSE question involving a set of divisibility constraints. In particular, it requires finding $n,p,q$ such that $p \mid 2n^2-1$ and $q \mid 2n^2-1$. Since $2n^2-1$ ...
Eric Snyder's user avatar
  • 3,016
1 vote
1 answer
88 views

$-1$ as quadratic residue in $p$-adic rings

It is well known that $-1$ is a quadratic residue in all the fields $\mathbb F_p$ for primes of $4N+1$ type. I want to know if $-1$ is always a perfect square in the rings of $p$ to the $n$-th powers, ...
Yuan Liu's user avatar
0 votes
2 answers
91 views

quartic residue symbol

Let $p$ be a prime $p \equiv 1 \bmod 4$. An $x\in\mathbb{Z}/p\mathbb{Z}$ is a quartic residue if there exists a $y$ such that $x = y^4 \bmod p$. Like for quadratic residues, there is a symbol which ...
a196884's user avatar
  • 283
0 votes
0 answers
29 views

Smallest element §a§ such that Jacobisymbol $(a, n) = -1$.

I want to get an upper bound for the smallest $a$ and a natural number $n$ such that the Jacobisymbol is $$ \big(\frac{a}{n}\big) = -1. $$ I know the following: Let $p>3$ be prime and let $a_p$ be ...
Lereu's user avatar
  • 434
1 vote
0 answers
27 views

Proof that Legendre symbol is multiplicative [duplicate]

I want to proof that the Legendre symbol is multiplicative. Therefore I use the Criterion by Euler whih claims, that for an integer $a$ and an odd prime $p$ it holds $$ \big( \frac{a}{q} \big) \equiv ...
Lereu's user avatar
  • 434
0 votes
2 answers
49 views

How to show a quadratic polynomial with complex roots has solutions mod $p$?

When the discriminant is $-k$ or ${-1\over k}$: As long as $-1$ and $k$ are both squares $\bmod p$ (trivial) or are both not squares, there are solutions mod $p$. How can this be explained/proven? e.g....
Older Amateur's user avatar
0 votes
1 answer
146 views

Is there any solution to $x^2 \equiv 53 \mod97$

Is there any solution to $x^2 \equiv 53 \mod97$ ( or in other words: is 53 quadratic residue of 97 ). It is possible to place any of $0,1,...,96$ in the congruence and check if any of them is a ...
Kevinlove's user avatar
  • 171
2 votes
1 answer
74 views

A Diophantine equation centered around the divisor counting function and squares

For each positive integer $n$, let $τ(n)$ be the prime counting function. Prove that for all positive integers $a$ and $b$ satisfy the following equation that $a+b$ is even: $a + τ (a) = b^2 + 2$. So ...
A Neutrino Boy's user avatar
0 votes
0 answers
106 views

Principal square root of quadratic residue mod $n$, where $n$ is a Blum integer

Let $n = pq$ be a Blum integer, where $p$ and $q$ are prime numbers, and $y$ belongs to the Quadratic Residues modulo $n$ ($y \in QR(n)$). How could I prove that the primitive square root $x$ of $y$ ...
Panagiotis Stefanis's user avatar
0 votes
1 answer
89 views

The least quadratic non-residue

For my thesis I need a good bound for the least quadratic non-residue modulo an odd prime $p$, which I can cite as proven. So I researched a lot and found several papers and bound. As far as I read in ...
Lereu's user avatar
  • 434
4 votes
2 answers
99 views

Experimentally found weird number theory pattern $p^\frac{d-3}{2}\cdot \left(p^\frac{d-1}2 \pm \{-1 \text{ or } p-1 \}\right) \mod d$ equals $0,1$

In the course of studying a problem involving counting points on hyperspheres and hyperplanes in dimension $d$ mod $p$, I came across the following interesting pattern Conjecture/Question: for (odd?) ...
D.R.'s user avatar
  • 8,805
0 votes
0 answers
51 views

Quadratic Residue for even numbers?

From our lecture, I noted down this statement: Let $a$ be an integer and $m$ an odd natural number with the prime decomposition $$ m = p_1^{\alpha_1}\cdot p_2^{\alpha_2} \cdots p_n^{\alpha_n}. $$ If $...
Lereu's user avatar
  • 434
0 votes
0 answers
7 views

How to recognize anisotropic quaternary rational quadratic forms?

For a rational quadratic form $Q$ in dimension $n$ I want to recognize when it is anisotropic or not. For $n=1$ or $2$ this is trivial, for $n> 4$ this cannot happen by Meyer's theorem. For $n=3$ ...
Mathieu Dutour Sikiric's user avatar
-2 votes
1 answer
38 views

Find a criterion for the odd primes p for which the congruence $x^2 + x + 3 \equiv 0 \pmod p$ has at least one solution.

Find a criterion for the odd primes p for which the congruence $x^2 + x + 3 \equiv 0 \pmod p$ has at least one solution. Explain how you know your answer is correct. A hint is given that the ...
StillLife's user avatar
2 votes
1 answer
38 views

Prove that there exists $1\leq a < p^{1/(2\sqrt{e})} (\log p)^2$ that is a quadratic non-residue modulo p

Logarithms are base 2. Use the inequality $|\sum_{a=1}^m \genfrac(){1pt}{2}{a}{p}|\leq \sqrt{p}\log p$, where $\genfrac(){1pt}{2}{a}{p} := a^{(p-1)/2}\mod p$ and p is a prime number, to prove that ...
Alfred's user avatar
  • 869
0 votes
0 answers
58 views

Residual theorem for ellipse perimeter integral

Trying to use residual theorem for integrating ellipse perimeter. Can I use the residual theorem for the ellipse perimeter? The calculation process I've followed so far If it cannot use the residual ...
Jerry Yang's user avatar
0 votes
0 answers
58 views

Prove that if $n$ is odd and $p \mid n$, then $\sum_{m=1,\, \gcd(m,n)=1}^{\varphi(n)} (\frac{m}{p})=0$

I have to prove this statement for my class, but I have run into an issue. When I choose $n=15$, for example, and if I choose $p=3$, I get \begin{align} \sum_{\substack{1 \leq m \leq 8 \\[1pt] \gcd(m,...
idontknow123's user avatar
2 votes
1 answer
152 views

how to find p-th primitive root of unity in GF(2^m)

The definition of quadratic residue codes involves finding a primitive p-th root of unity in some finite extension field of $GF(2)$. 2 is a quadratic residue of prime $p$. By brute force search I ...
unknown's user avatar
  • 1,010
0 votes
0 answers
34 views

The distribution of which numbers have square roots in $\mathbb Z_p$ and how many

Let $p$ be a prime number, and consider the set $V \subset Z_p$ of $x$ modulo $p$ for which there exist an $m$ where $m^2 \equiv x \pmod p$. Specifically, consider a count version of that, where each ...
Snared's user avatar
  • 895
3 votes
1 answer
72 views

$\sum _{r=1}^{p-1}r^{2k}\left(\frac{r}{p}\right)=\sum_{i=1}^{2k-1} c_i(p)\sum _{r=1}^{p-1}r^{2k-i}\left(\frac{r}{p}\right)$

[Analytic Number Theory - Florian Luca and Jean Marie De Koninck, chapter 14, question 14.2] A series of questions asks to prove the following:- Prove $$\sum _{r=1}^{p-1}r\left(\frac{r}{p}\right)=0$$...
Sayan Dutta's user avatar
  • 9,094
0 votes
2 answers
62 views

A question about Legendre symbols

I am reading a book with corrected exercises, and I bumped into the following sentence: $$\left( \frac{2^m + 1}{3} \right)=\left( \frac{2}{3} \right)=-1$$ where we assumed that $2^m+1$ is prime. I ...
TheStudent's user avatar
  • 1,245
0 votes
0 answers
88 views

Where did Euler publish his formular for the Legendre Symbol?

I am working on a thesis and I am using Euler's criterion. I am interested in it's origin, so the first publication of it by Euler. I found some references, though I did not find the original work of ...
Lereu's user avatar
  • 434
3 votes
0 answers
248 views

Is the quadratic residue the only restriction?

I still search without success for a prime factor of the huge number $$2\uparrow \uparrow 4+3\uparrow \uparrow 4$$ Another way to write this is $$3^{3^{3^3}}+2^{2^{2^2}}=3^{3^{27}}+65536=3^{...
Peter's user avatar
  • 84.7k
3 votes
0 answers
40 views

Sequences in finite fields producing quadratic residues

Let $q$ be a prime $q\equiv 3 \pmod 4$, and consider the finite field $F_{q^2}$. We take the sequence starting with some $x_0$ and with $x_{i+1} =\sqrt{\frac{x_i+x_i^{-1}}{2}}$ for $i\geq 0$. We ...
Vicente Muñoz's user avatar
2 votes
1 answer
136 views

Cardinality of set of quadratic residue of mod n.

I was studying quadratic residue mod $n$, $n=p_1p_2\dots,p_k$ where $p_i$ are distinct primes such that $p_i\equiv 3\pmod4$ recently. Let $Q=\{x^2\equiv q\pmod n | gcd(q,n)=1\}$ be the set of ...
isnet's user avatar
  • 65
0 votes
0 answers
60 views

Stuck in a quadratic reciprocity problem

I've recently started studying elementary number theory. Now I'm going through the topic of quadratic reciprocity. I'm having trouble trying to show that $n$ and $k$ are even numbers whenever $60k+7$ ...
dwhydtea's user avatar
2 votes
2 answers
132 views

Legendre symbols always match?

When I test these Legendre symbols on the primes that are $p\equiv 1\bmod 12$, they always seem to equal each other: $$\left( \frac{-6+2\sqrt{-3}}{p}\right)=\left(\frac{3+2\sqrt{3}}{p}\right)$$ Is ...
user404920's user avatar
2 votes
1 answer
93 views

How to find the square root of an element in an abelian group of even order?

Suppose $a\in\mathbb{G}$ is an arbitrary element in an abelian group $\mathbb{G}$ of order $|\mathbb{G}|$. The group $\mathbb{G}$ need not be a multiplicative modulo group and/or a cyclic group. Is ...
Souvik's user avatar
  • 33
1 vote
1 answer
102 views

Quadratic residues that are also squares themselves

I have a question about number bases and square numbers. When considering quadratic residues in a given modulus (without eliminating residues that are not relatively prime to the modulus), it is ...
Robert J. McGehee's user avatar
1 vote
0 answers
54 views

Help with summing characters

Let $p \equiv 1(n)$. Let $\chi$ denote a character from $\mathbb{F}_p \rightarrow \mathbb{C}-\{0\}$. Then, in Ireland and Rosen's A Classical Introduction to Number Theory, while trying to find the ...
Yang Awotwi's user avatar
0 votes
0 answers
45 views

Given $y$, is $-\left(\dfrac{x - y}{2}\right)^2$ is a quadratic residue $\pmod x$?

I am trying to find a formula for some circle packings when the following arose. I am wondering if there is a nice way to find which $y$ yield $-\left(\dfrac{x - y}{2}\right)^2$ a quadratic residue $\...
Clyde Kertzer's user avatar
1 vote
1 answer
97 views

How to prove that primes congruent to $\pm1$ mod $5$ are of the form $5 a^2 - b^2$

I'm working through Reid's Undergraduate Commutative Algebra to prepare myself for Algebraic Geometry next semester, and one of the exercises (0.19) walks you through studying the ring $\mathbb Z[\...
themathandlanguagetutor's user avatar
0 votes
2 answers
133 views

Find the number of integer solutions of $22x^2-34xy+6y^2=2024$

I was given this and I could really use some hints. I know that there are no integer solutions to the equation and that I have to factor the left side to get the form $(ax+by)^2$ by multiplying/...
fluffy's user avatar
  • 51
2 votes
2 answers
72 views

Show that $z^2$ is a fourth power mod $q$ if and only if $\left(\frac{z}{q}\right) = 1$, given that $q \equiv 1 \pmod{4}$.

Show that $z^2$ is a fourth power mod $q$ if and only if $\left(\frac{z}{q}\right) = 1$, given that $q \equiv 1 \pmod{4}$. Here $\left(\frac{z}{q}\right)$ is the Legendre symbol whose value of 1 ...
TSpoon's user avatar
  • 339
1 vote
0 answers
82 views

Legendre symbol on $p$-adic integers $\mathbb{Z}_p$

I have seen that you can define the usual modular arithmetic on the $p$-adic integers: For $a,b\in\mathbb{Z}_p$ and a prime $p$, $$a\equiv b\pmod{p}\iff (a-b)/p\in \mathbb{Z}_p.$$ My question is, can ...
the inner beauty's user avatar
-2 votes
1 answer
144 views

(103/1009) Evaluate The Legendre Symbol

I am relatively new to Legendre symbols. For the following problem, I feel that what I have is correct thus far: (103/1009) -> (1009/103) -> (82/103) -> (2/103)(41/103) 103 is congruent to 3 (...
نظامی گنجوی's user avatar

1
2 3 4 5
17