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
0 votes
1 answer
18 views

Quadratic residues with prime number

Let Define: $$Q1=\{i^2\ mod\ p | 0\leq i<p\}$$ $$Q2=\{(-1)^i\cdot i^2\ mod\ p | 0\leq i<p\}$$ Let notice that for $p=47$ it can be shown that $|Q1|=24$ and $|Q2|=47$ but for other primary for ...
user avatar
3 votes
1 answer
63 views

Number of Solutions of the Hyperbola Equations over Finite Fields

I have a problem with proving the number of points of the hyperbola equation $H_u: x^2 - y^2 = u$ (for every u > 0 in finite field $F_p$) in the finite fields. I have to prove that the number of ...
user avatar
  • 31
-1 votes
1 answer
36 views

Problem regarding quadratic recidues that I cannot solve [duplicate]

The problem is as follows: Let $p$ be a prime and assume that $p=1$ mod 5. Let $c\in\left(\mathbb{Z}/p\mathbb{Z}\right)^{\times}$ be an element of order 5 and let $g=2(c+c^{-1})+1$ Show that $g^2=5$ ...
user avatar
  • 15
2 votes
1 answer
59 views

For every prime p there is a sum of squares congruent to -1 mod p [duplicate]

For every prime $p$, there exists $a,b \in \mathbb{Z}$ such that $p\mid a^2+b^2+1$ For context, this question shows up as a statement on a hint to showing that every positive integer is a sum of 4 ...
user avatar
0 votes
0 answers
32 views

Find any or all Lipschitz quaternions corresponding to a given quaternion norm

In this answer, in response to the question "How to find $2+7𝑖$ from $53$?", user @Cocopuffs provided a reference to a Jacobsthal sum, which enables obtaining a Gaussian integer, based on a ...
user avatar
  • 19
1 vote
1 answer
37 views

Sum of the Multiplicative Legendre's symbol

Let $p$ a be odd prime show that $\displaystyle\sum_{a=1}^{p-2}\left(\frac{a(a+1)}{p}\right)=-1$. Nota Bene : The $(\frac{a}{p})$ is $\textbf{Legendre Symbol}$
user avatar
1 vote
1 answer
25 views

Can the jacobi symbol be used for the statement "n is represented by some quadratic form of discriminant d iff 4n is a square mod d"

We've been using the above statement repeatedly in a number theory course, but to find all primes that are represented by a quadratic binary form of discriminant d, we've been using $$(\frac{d}{4p}) = ...
user avatar
  • 33
2 votes
1 answer
109 views

Is $\left(\frac{a^2}{5}\right)=1$ for all $a$ not divisible by 5?

$\left(\frac{a^2}{5}\right)$ is the legendre symbol. I used wolfram alpha to see if, $$\left(\frac{a^2}{5}\right)=1$$ and this is true for integers from 1 to 10 and it is except 5 and 10, which are ...
user avatar
0 votes
1 answer
59 views

Prove that there exists exactly 1 solution to $x^2 \equiv a \pmod{2}$ where $a \in \mathbb{Z}$.

Prove that there exists exactly 1 solution to $x^2 \equiv a \pmod{2}$ where $a \in \mathbb{Z}$. I've been looking around for this problem, but I haven't found it here so I asked. What the title says. ...
user avatar
0 votes
0 answers
24 views

Legendre symbol and quadratic residues [duplicate]

Suppose $p\in\mathbb{N}$ is an odd prime. I wish to show that in any reduced system of residues modulo $p$, we have that the number of quadratic residues is the same as the number of quadratic ...
user avatar
0 votes
0 answers
40 views

Order of an integer $a$ relation with the Legendre symbol $(a/p) = -1 \pmod p$

I am self studying number theory from David M. Burton's book Elementary Number Theory. Example $9.7$ explains about $3$ as a primitive root of primes $F_n = 2^{2^n}+1$ these are of the form $p= 12k+5$...
user avatar
  • 160
4 votes
1 answer
45 views

Suppose an integer x is a square modulo every prime, show that x is a square integer

I was looking at Is every non-square integer a primitive root modulo some odd prime? (the answer by Hagen von Eitzen) but its a bit too concise so im having a hard time understanding it. Could someone ...
user avatar
  • 161
-4 votes
1 answer
37 views

Quadratic residues and non-residues of p=4k+3 are complementary [closed]

Given a prime p=4k+3 and an integer X, is it the case that if X is a quadratic residue of p, then -X (i.e. p-X) is NOT a quadratic residue of p? How to prove this? (Kudos for a simple proof!)
user avatar
3 votes
1 answer
83 views

Prove that 3 is not a quadratic residue of $2^n-1$ when n is odd.

The problem is to show that 3 not a quadratic residue mod $2^n-1$ when n is odd and $n>\geq 3$. As for now I can see that $2^n-1$ is $1$ mod $3$ which means that $2^n-1$ has an even number of prime ...
user avatar
0 votes
1 answer
19 views

Gauss sum over Legendre symbols combining residue and non-residue parts

I’m reading Davenport’s Multiplicative Number Theory and I’m currently in the second chapter, the subject of which is calculating the following sum: $$ G= \sum_{n=1}^{q-1} \Bigr(\frac{n}{q}\Bigr )e_q(...
user avatar
  • 1,770
0 votes
1 answer
39 views

Is there an algorithm for determining if $a$ is a quadratic residue mod $n$, where factorization of $n$ is given? [duplicate]

Let's say I'm given numbers $a$ and $n$, where $n$ is already factored into prime powers: $$n = p_1^{\alpha_1}p_2^{\alpha_2}p_3^{\alpha_3}... $$ Is there a fast algorithm to determine if $x^2 \equiv a ...
user avatar
1 vote
0 answers
36 views

Counting the number of $x \in [a,b] \subset \Bbb{Z}$ such that $x^2 = k^2 \pmod d, \ \ d\mid n\#$?

Define $$ \phi(a,b,d,k)= \sum_{c\mid d \\ (c,2k)=1} \left( \lfloor\dfrac{b - x}{d}\rfloor + \lfloor\dfrac{x - a}{d}\rfloor\right).\tag{1} $$ We know that $\phi$ measures $\#\{x \in [a,b]: x^2 = k^2 \...
user avatar
1 vote
1 answer
43 views

square root of $a$ mod n when $a$ and n are not relatively prime

When finding whether there exists a solution for $x^2 \equiv a \pmod n $, one way is to calculate it with the Jacobi symbol. However, Jacobi symbol requires that $(a,n) = 1$. So I wonder when $(a,n) \...
user avatar
3 votes
1 answer
134 views

Logarithmic average of the Legendre symbol

My question is simple: can we show that the sum $$ \sum_{k=1}^{p-1} \frac{\left( \frac{k}{p} \right)}{k} $$ is positive for all primes $ p $ where $ (k/p) $ denotes the Legendre symbol modulo $ p $, i....
user avatar
  • 17.1k
2 votes
0 answers
29 views

Formula to calculate Jacobi Symbols using polynomials

Given $\left(\dfrac{a}{n} \right)$ for some odd $n$ coprime to $a$, is it possible to construct a polynomial $P(n)$ such that $\left(\dfrac{a}{n} \right) = (-1)^{P(n)}$ Such polynomials exist for $a=-...
user avatar
  • 181
0 votes
1 answer
65 views

How did we discover that this quadratic residue oriented PRNG generates unique numbers in a sequence?

Question (tl;dr) How do we know that even for extremely large numbers like even far past $32^{15}$ (any bigint, or any number really), that as you increment the sequence from $0$ to $n$, $n$ being the ...
user avatar
  • 3,166
0 votes
1 answer
63 views

How to find the amount of solutions of polynomial congruence?

The given congruence is $ x^4-5x-6 ≡ 0 $ mod $(100^{100})$. Find the amount of it’s solutions. I’ve factorised it: $ (x+1)(x-2)(x^2+x+3) ≡ 0$ mod $(100^{100})$. From here I get solutions for the first ...
user avatar
  • 83
1 vote
0 answers
26 views

Particular case of the law of quadratic reciprocity

Let $\mathbb{F}_q$ be a finite field of characteristic $p \neq 2,5$ . What I've shown so far : $x \in\mathbb{F}_q^* $ is a root of $\Phi_5 = X^4 + X^3 +X^2+X+1$ if and only if $x$ is of order 5 in $\...
user avatar
0 votes
0 answers
44 views

Solve RSA problems with e=2 and n is product of three primes

Summarize problem: Given: n=p*q*r with p,q,r are primes number and $p\equiv3(\text{ mod }4)$,$q\equiv3(\text{ mod }4)$,$r\...
user avatar
  • 405
2 votes
1 answer
67 views

Incongruent Solutions of a Quadratic congruence

I have been reading up on finding incongruent solutions of quadratic congruences and have stumbled upon an answer to a question asked here. The answer I am confused about is the following: "if ...
user avatar
0 votes
0 answers
73 views

How to find squares mod $m$, i.e $x$ in $x^2 \equiv a \mod m$, without factoring $m$?

I have very large integers $m$, where ( $\log_2(m)> 630$), and I need to find square roots modulo m. I am aware of several theorems that allow me to find the roots $\mod m$ when m is a power of a ...
user avatar
2 votes
0 answers
190 views

Number of quadratic congruences modulo $n$ having exactly $k$ solutions

Given integers $n$ and $k$, find the number of quadratic congruences of the form $$ ax^2 + bx + c \equiv 0 \pmod{n} $$ having exactly $k$ solutions in $\mathbb{Z}_n$, where $a, b, c \in \mathbb{Z}_n$....
user avatar
  • 277
0 votes
1 answer
72 views

Determine the number of distinct solutions of $(x^2-1)(x^2+1)\equiv 0 \pmod {4\cdot31^3}$ [closed]

I want to determine the number of distinct solutions of $(x^2-1)(x^2+1)\equiv 0 \pmod{4\times 31^3}$,if I call LHS as $f(x)$,then $f(x)\equiv 0 \pmod{4}$ and $f(x)\equiv 0 \pmod{31^3}$.Now I do not ...
user avatar
4 votes
2 answers
73 views

Is it possible to a root of a Gaussian integer be a Hurwitz quaternion?

I'm trying to solve the equation $$ E(x)=\frac{(1+ix)^{1/2}-(1-ix)^{1/2}}{(1+ix)^{1/2}+(1-ix)^{1/2}} \mod p, $$ where $p$ is a prime and $1+ix$ is a Gaussian integer over $p$. For some values of $x$, ...
user avatar
1 vote
2 answers
76 views

How to find the solution of $x^2\equiv 25\pmod{32}$?

I am trying to find square root of $57$ modulo $32\times 49$. For that I need to find the solutions of $x^2\equiv 57\pmod{32}$ and $x^2\equiv 57\pmod{49}$ which are $x^2\equiv 25\pmod{32}$ and $x^2\...
user avatar
2 votes
1 answer
48 views

Why isn't Quadratic Congruences trivially solvable in polynomial time?

The Quadratic Congruences problem asks if for constants $a$, $b$, and $c$, does there exist $x$ such that $x<c$ and $x^2 \equiv a\mod b$? This problem is known to be NP-complete. However I can't ...
user avatar
0 votes
0 answers
19 views

Consecutive quadratic residues. [duplicate]

I am stuck with the following question given to us in an assignment: Let $p>5$ be prime.Let $S=\{1,2,...,p-1\}$ Show that at least one of $2,5,10$ is a quadratic residue mod $p$. Hence show that ...
user avatar
-1 votes
1 answer
52 views

Finding the quadratic residue $Q_{160}$

Let $Q_n$ denote the quadratic residues in $U_n=\mathbb Z_n^\times$.Our instructor gave us a characterisation of $Q_n$ as follows: $1.$ If $\gcd(m,n)=1$.then $a\in Q_{mn}\iff a\in Q_m $ and $a\in Q_n$....
user avatar
1 vote
0 answers
59 views

Proof of Theorem 9.10 Equation (8) in Apostol's Introduction to Analytic Number Theory

In the book Introduction to Analytic Number Theory by Apostol, the Theorem 9.10 (two properties of the Jacobi symbol) states that: If $P$ is an odd positive integer we have \begin{equation} \tag{7} (-...
user avatar
  • 511
1 vote
0 answers
83 views

If $p$ is a Sophie Germain prime, that is $q = 2p+1$ is also prime and $a\not\equiv \pm1$(mod $p$) then $a^2 \not\equiv 1$(mod $q$).

I am trying to understand the proof that If $p$ is a Sophie Germain prime, that is $q = 2p+1$ is also prime and $a\not\equiv 0,\pm1$(mod $p$) $$\text{If }\biggl(\frac{a}{q}\biggr)=-1 \text{ then }a \...
user avatar
3 votes
0 answers
58 views

Number of square roots of $a$ modulo $n$.

An element $a\in U_n$ is said to be a quadratic residue modulo $n$ if $a=b^2$ for some $b\in U_n$. Now we know that the set of all quadratic residues form a group $Q_n$. Now, we define an epimorphism ...
user avatar
1 vote
0 answers
31 views

Correctness of $\sigma_s(n) (1-\frac{1}{n^s}) = 0 \pmod{k}$ (divisor sum congruence)

I've played around with some identities and came up with: $\sigma_s(n)(1-\frac{1}{n^s}) = 0 \pmod{k}$ (for $n$ and $k$ positive integers, and $s$ an integer) With the conditions that 1) $n$ is ...
user avatar
  • 341
2 votes
1 answer
55 views

Is factoring primes $pq$ eqivalent to discovering $p+q$, thus binding $q$ and the search for $(p+q)$ when $(q/p) < 4$?

Background Some crypto algorithms rely principally on the difficulty of factoring two prime numbers $p$ and $q$. For the purpose of this discussion, assume $p<q$. (The top of this article is ...
user avatar
  • 135
2 votes
0 answers
63 views

Generalization of Quadratic Residues to other rings?

In my number theory class, we're learning about Quadratic Residues (QRs) vs. Nonquadratic Residues (NRs, also sometimes called quadratic nonresidues) in $\mathbb F_p$. It works out that multiplying ...
user avatar
0 votes
0 answers
13 views

Efficiently finding small non-trivial "quadratic residues" for large smooth numbers

Eg. Is there an efficient way to find the smallest non-square "quadratic residue" (in quotes because I don't know if I'm allowed to use that term for composite numbers) modulo 300! (that's ...
user avatar
  • 800
1 vote
2 answers
74 views

Counting solutions to $x^2+y^2 \equiv d \pmod{p}$ for a prime $p \equiv 3 \pmod 4$

For any given $p \equiv 3 \pmod{4}$ and $d=1, 2, \dots, p-1$, we would like to show that there are always exactly $p+1$ solutions to $x^2 + y^2 \equiv d \pmod{p}$. This conjecture comes from some ...
user avatar
1 vote
1 answer
49 views

Notation for Legendre symbol over polynomial rings

Hopefully this is a simple question to answer. I am wondering if there is any standard notation for something equivalent to the Legendre symbol, but over polynomial rings. That is, if we have a prime $...
user avatar
1 vote
0 answers
31 views

Only Legendre symbol gives constant magnitude discrete Fourier transform

It is well-known that if we take the Fourier transform $\hat{g}$ of a (translated) Legendre symbol $g(x) = \pm(x+a|p)$, then $|\hat{g}(r)| = \sqrt p$ for all $r\neq 0$. I heard that the converse is ...
user avatar
0 votes
0 answers
69 views

Find the sum of all primes less than $75$ that can be factors of $n^2-3$ such that $n≥2$

Find the sum of all prime numbers less than $75$ that can be factors of $n^2-3$ such that $n≥2$. On trying small values of $n$, I found that $2,3,11,13,7,19,67,43,31$ can be prime factors of $n^2-3$ ...
user avatar
1 vote
2 answers
85 views

Is $62$ a quadratic residue module $187$?

My idea was to put $$187 = 11 \times 17$$ and then I have the system of congruences: $$x^2 \equiv 62 \equiv 7\pmod{11} \space \text{and} \space x^2 \equiv 62 \equiv 11\pmod{17}.$$ Using the Legendre ...
user avatar
0 votes
0 answers
44 views

Jacobi symbol (40 | n) is equal to 1 for which positive integer n ?where n is relatively prime to 40 .

For which positive integer $n$ relatively prime to $40$ does the Jacobi symbol $\left(\frac{40}{n}\right)$ equal $1$? I am try several times but I am unable to find it. Here $40 = 5\cdot2^{3}$ so we ...
user avatar
0 votes
0 answers
14 views

Why do some authors define the Legendre symbol also for the case if $p|a$?

I found the definition of the Legendre-Symbol as an homomorphism $$ \left( \frac{\cdot}{p} \right) : (\mathbb{Z} / m \mathbb{Z})^{\cdot} \rightarrow (\mathbb{Z} / m \mathbb{Z})^{\cdot} / (\mathbb{Z} / ...
user avatar
  • 145
0 votes
1 answer
29 views

$a^2 \equiv kb^2 \pmod p$ implies solution to $x^2 \equiv k \pmod p$

Suppose $p$ a prime and $a$ and $b$ are not divisible by $p$. I’d like to show that $a^2 \equiv kb^2 \pmod p$ implies that there exists a solution to $x^2 \equiv k \pmod p$ but I don’t know what ...
user avatar
0 votes
1 answer
70 views

Proving that if prime p>3 divides a^2 + 12, then p is congruent 2(mod 3)

Prove that if prime $p>3$ divides $a^2 + 12$, then $p$ is congruent $2\pmod 3$. I tried splitting (-12/P) to (-1/P) * (3/P) and solving 4 different cases to find when (-12/P) = 1, but I got that p ...
user avatar
  • 79
0 votes
1 answer
124 views

Quadratic residue test for mod powers of 2

For odd primes, you can test using Euler's criteria if a number is a Quadratic Residue $\bmod p$. I am looking for a test for mod powers of 2 (which are even & hence cannot use Euler's criteria). ...
user avatar
  • 359

1
2 3 4 5
22