Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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$.

3
votes
0answers
53 views

Is it necessary for a number of the form $4k^2+1$ to have at least one prime factor of the form $4n+1$?

Is it necessary for a number of the form $4k^2+1$ to have at least one prime factor of the form $4n+1$? I was trying to prove that there are infinitely many primes of the form $4n+1$, but to prove it,...
1
vote
0answers
28 views

Proof: For any prime number $p$, there must be integer $a$, $b$, $c$, $d$ such that $x^4+1 \equiv (x^2+ax+b)(x^2+cx+d)\ (mod\ p)$. [duplicate]

This is a question comes from a book about Number theory, and the question is related to Quadratic residue. I start with $$ x^4+1 \equiv (x^2+ax+b)(x^2+cx+d) \\ \equiv x^4+(a+c)x^3+(b+d+ac)x^2+(ad+...
4
votes
2answers
65 views

Is there always a positive integer $a$ such that both $a^2-4$ and $a^2+4$ are quadratic non-residues $\bmod p$?

I would like to prove (disprove if wrong) the following statement: For all odd prime numbers except for $p=3,5$ or $13$, there exists an integer $a>0$ such that both $a^2-4$ and $a^2+4$ are ...
1
vote
1answer
26 views

A question concerning higher residues (quadratic and so on)

When $x \equiv a \pmod{n}$ one says that $a$ is the residue of $x$ modulo $n$. So one can define: $a$ is a 1-residue modulo $n$ if there is an $x$ with $x \equiv a \pmod{n}$. Clearly, every $a&...
0
votes
0answers
49 views

Relation between residues and primitive roots modulo $p$

I got a very satisfiying answer to my question on the relation between primeness and co-primeness of numbers which can be defined in a somehow symmetric way: $n$ is prime iff $$(\forall xy)\ ...
11
votes
2answers
129 views

If $p$ is prime, then $x^2 +5y^2 = p \iff p\equiv 1,9 $ mod $(20)$.

Let $p\neq 2,5$ be prime. I wish to show that: $x^2 +5y^2 = p \Leftrightarrow p\equiv 1,9 $ mod $(20)$. I proved to $\Rightarrow$ part, means $x^2 +5y^2=p \Rightarrow p\equiv 1,9 $ mod $(20)$. For $\...
0
votes
0answers
37 views

Determine the quadratic residues $QR_{85}$.

Define the set of quadratic residues as $QR_N = \{x^2 \bmod N: x \in \mathbb{Z}_N^*\}$. I'm asked to compute $QR_{85}$ without any further knowledge. I know that there are $\phi(85) = \phi(5) \phi(...
2
votes
0answers
53 views

About the prime divisor of a quadratic function

Encountered in Modell's book Diophantine Equations. In the second chapter, page 3, it says: 'every prime divisor of $p$ of $x^2-a$ for integer $x$ is either a divisor of $a$, or can be represented ...
0
votes
1answer
47 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
1answer
68 views

$x^2 \equiv -2,2 \pmod {122}$

I am trying to solve the following problem: Which of the following congruences has solutions? How many? $$x^2 \equiv 2 \pmod {122}$$ $$x^2 \equiv -2 \pmod {122}$$ For both congruences, $122 = 2\...
4
votes
1answer
112 views

A question about a primitive root mod $p=2^{2^k}+1$, where $p$ is prime.

Let $p=2^{2^k}+1$ be a prime where $k\ge1$. Prove that the set of quadratic non-residues mod $p$ is the same as the set of primitive roots mod $p$. Use this to show that $7$ is a primitive root mod $p$...
0
votes
1answer
72 views

The set of the primitive roots modulo $p$, with $p$ a fermat prime

"Let $p$ be a prime of the form $2^{2^{n}}+1$, with $n \in \mathbb{N} $ (This means $p$ is a Fermat prime) Using Euler's Criterion, prove that the set of primitive roots mod $p$ is equal to the set ...
1
vote
1answer
88 views

Question about a kind of generalized Fermat numbers

The present question is directly inspired by this one. Let $\alpha$ be a unit in the ring of quadratic integers of a real quadratic field, or, in less sophisticated words: $$\alpha=\frac{a\pm\sqrt{...
1
vote
1answer
45 views

$x^2\equiv 5 \pmod{1331p^3}$

Let $p$ be given by $p=2^{89}-1$ and note that it is a Mersenne Prime. The problem is to find the number of incongruent solutions to $$ x^2\equiv 5 \pmod{1331p^3} $$ I began the problem by splitting ...
0
votes
0answers
36 views

Find a congruence condition that determines whether $5$ is a square modulo $p$

Let $p\not\in\{2,5\}$ be prime. How can I find a congruence condition that determines whether $5$ is a square modulo $p$?
0
votes
2answers
37 views

Find the least nonnegative residue of: $42^{173} modulo 13$

I can across this question: Find the least nonnegative residue of: $42^{173} modulo 13$ I have done the following: $42^{10} ≡ 1 mod 13$ $42^{173} = 42^{10 (17) +3}$ $ 42^{173} ≡ 42^{3} mod 13$ $...
0
votes
2answers
36 views

Find the least non residue

Find the least non residue of the following $41 × 42 × · · · 54 modulo 19$ $41 × 42 × · · · 54=54!/40!$ $41 ≡ 3 mod 19$ $54 ≡ 16 mod 19$ That is as far I can get. Any help of how to continue ...
0
votes
3answers
30 views

Find the least non residue… Explanation required

Find the least non residue of the following $7^{4275} \mod 11$. I have the solution for the problem and it is the following: $7^{10} ≡ 1 \mod 11$ $7^{4275} = (7^{10})^{427} \times 7^{5} \mod 11$ ---...
0
votes
1answer
23 views

$(2)-$ cyclotomic cosets modulo a prime

Let $p$ be an odd prime. Assume $2$ is a quadratic residue modulo $p$. Is it true that the $(2)-$ cyclotomic cosets modulo $p$ are ${\{0}\}, {\{Q}\}, {\{N}\}$, where $Q$ are the quadratic residues ...
-1
votes
3answers
45 views

What primes $p$ give solutions to $x^{2} \equiv 7 ($mod $ p)$

I'm trying to understand how to solve this using the Legendre symbol but am having a hard time figuring out exactly what to do. There are many different cases to consider but I do not know how to ...
0
votes
0answers
25 views

Cyclotomic cosets and quadratic residues

Let $p$ be a prime and let $Q$ be the set of quadratic residues and $N$ the set of nonresidues. Assume $2 \in Q$. When I look a the cyclotomic cosets mod $p$, I get ${\{0}\}, {\{Q}\}, {\{N}\}.$ For ...
0
votes
1answer
13 views

Literature on Uniqueness of Quadratic Residues Modulo a Prime

I came across a really interesting blog post on generating a permutation based on quadratic residues of the form $x^2$ $mod$ $p$ (where $p$ is prime). It can be accessed here for further context: ...
0
votes
2answers
75 views

Prove that $2p+1$ is a divisor of $2^p-1$

Suppose that $p$ is a Sophie Germain prime and $p=3 mod 4$. Want to prove that $2p+1$ is a divisor of $2^p-1$. I got a hint that I should prove that $2$ is a square mod $2p+1$ along the way, but I ...
0
votes
1answer
23 views

Solutions of $x^2 \equiv \pm 2 \ (\text{mod} \ p)$ and primitive root modulo $p.$

If $p = 8n+1$ is a prime and $r$ is a primitive root modulo $p,$ then the solutions of $x^2 \equiv \pm 2 \ (\text{mod} \ p)$ are given by $x \equiv \pm(r^{7n} \pm r^n) \ (\text{mod} \ p).$ Again, ...
0
votes
1answer
32 views

Characterization of the solutions to $x^2 \equiv a \ (\text{mod} \ p),$ where $p=8n+5$ is a prime.

If $a$ is a quadratic residue of the prime $p= 8n+5,$ then the solutions of $x^2 \equiv a \ (\text{mod} \ p)$ are $x \equiv \pm a^{n+1}$ or $\pm 2^{2n+1}a^{n+1} \ (\text{mod} \ p)$ I have shown that $...
4
votes
0answers
47 views

The Number of involutory matrices over $\mathbb{Z_p} $

I want to prove the number of 2-by-2 Involutory Matrices ($A^2=I$) over $\mathbb{Z_p}$ using quadratic residue and legendre symbol. I already know that the formula is $p^2$ for characteristic of a ...
0
votes
1answer
63 views

How many elements in the natural system of representative of $5400$ are squares $\mod 5400$?

I was working on the problem: Consider the set $S=\{0,1,...,5399\}$ be the natural system of representatives $\mod5400$. How many elements of $S$ are squares $\mod 5400$. But shouldn't the answer just ...
1
vote
1answer
60 views

Legendre symbol $ p ≡ 5 \mod 8$

I need to prove: If $p$ is a prime number congruent to $5 \mod 8$, and $\left(\frac np\right)= 1$, then either $ [n^{(p+3)/8}] ^2 ≡ n\bmod p$ or $ [n^{(p+3)/8}((p-1)/2)! ]^2 ≡ n\bmod p$ I am ...
3
votes
0answers
40 views

Let $p>11$ be a prime. Then there exists integer $a$ such that $a, a+1$ are quadratic residues modulo $p.$

Let $p>11$ be a prime. Then there exists integer $a$ such that $a, a+1$ are quadratic residues modulo $p.$ May I know if my proof is correct? Please advise, thank you. There are $\dfrac{p-1}{2}$ ...
0
votes
1answer
29 views

Prime factorization of very large integer with quadratic residue and its square roots

We have a very large modulus integer $n$ and we have very large number $y$. We know that $y$ is a quadratic residue modulo $n$. Also we know all $4$ square roots of $y$. What is the best way of ...
0
votes
3answers
50 views

How to prove “Unit digit of a square number”?

How can I prove that the unit digit of a perfect square is always $0,1,4,9,5,6$ and never $2,3,7,8$? It's pretty intuitive but I am having difficulties proving this statement. I had used trial ...
1
vote
1answer
88 views

Showing that $\sum_{x \in \mathbb{F}_p} \left(\frac{x^2-1}{p}\right) = -1$, where $\left(\frac{x}{p}\right)$ is the Legendre symbol

The question is, Show that $$\sum_{x \in \mathbb{F}_p} \left(\frac{x^2-1}{p}\right) = -1$$ where the operation $\left(\frac{x}{p}\right) = \pm 1$ if $x$ is a quadratic residue/non-residue and $0$ ...
2
votes
1answer
65 views

sum of quadratic residues for $p=8k+7$

I have a question concerning the sum of quadratic residues in $[-p',p']$ for $p=8k+7$ where $p'=(p-1)/2$. The answer seems to be $0$ for small cases: $$p=7:1+2-3=0$$ $$p=23: 1+4+9+2+3+6+8-7-10-5-11=0$...
2
votes
2answers
72 views

Basics of Quadratic Sieve algorithm

I'm trying to understand Quadratic Sieve algorithm for integer factorization, I follow the description in the book "Prime Numbers" by Crandall and Pomerance, specifically the Algorithm 6.1.1. (Even ...
0
votes
1answer
28 views

(Soft Question) Why does the Legendre Symbol apply only to odd primes

Why does the Legendre symbol, $(\frac{a}{p})$, apply only to odd primes $p$; and thusly the Jacobi symbol only to odd numbers? Are there any similar identities that hold for $p=2$?
2
votes
2answers
67 views

$-3$ is a quadratic residue iff $p \equiv 1 \pmod 3$ [closed]

So this is the question: Let $p$ be an odd prime, prove that $-3$ is a quadratic residue modulo $p$ iff $p \equiv 1 \pmod 3$. My idea was: $$\left(\frac{-3}{p}\right) = \left(\frac{-1}{p}\right)\...
0
votes
1answer
21 views

Solutions to the equation $3m^2\equiv 1\pmod{p}$ where $p$ is some prime

Here is my question: Solve the equation $3m^2\equiv 1\pmod{p}$, where $p$ is some prime. This seems to be closely related to quadratic residues. For example, if we were to solve $x^2\equiv -1\pmod{...
1
vote
1answer
34 views

Solving a non-linear congruence for $f\in \mathbb{F}_5[x]$

How can we find a solution $f\in \mathbb{F}_5[x]$ for the following non-linear congruence? $ f\equiv 1\mod{x}+1,\ x\cdot f\equiv x+1\mod{x^2}+1,\ (x+1)\cdot f\equiv x+ 1\mod{x^3}+1 $
0
votes
1answer
50 views

the solutions are quadratic nonresidues modulo $p$

Let $q$ be an odd prime number, such that $p=4q+1$ is also an odd prime. I want to show that the congruence $x^2 \equiv -1 \pmod{p}$ has two (incongruenct modulo $p$) solutions, which are quadratic ...
1
vote
1answer
42 views

If $a$ is not square then there is a class $\mod 4a$ such that $a$ is a quadratic non-residue modulo any prime in that class.

I am trying to show that any non-square $a$ is a quadratic non-residue modulo an infinite number of primes, and this is my argument so far: There is a well-defined group homomorphism $\chi : (\mathbb{...
0
votes
0answers
31 views

Finding $p$-primes which a congruential modulo $p$ has a solution.

I need to find the primes for which the congruential $x^2-4x-3=0$ (mod $p$). First I checked for $p=2$ and $x=1$ is a solution. Assuming $p>2$, my approach was that the discriminant $=28$ needs to ...
5
votes
2answers
98 views

Find smallest prime $p$ such that all primes $q < 40$ are quadratic non-residues $\pmod p$

What is the smallest prime $p$ such that every prime $q < 40$ is a quadratic non-residue $\pmod p$? Given that the probability that $q$ is a non-residue mod $\pmod p$ is $1/2$, and there are $12$ ...
0
votes
0answers
47 views

square roots in multiplicative group of integers modulo n

How do I exactly determine all solutions for square roots if they exists and what to do if for one square root exist two solutions? Let's for example take the Group $(\mathbb{Z}/7\mathbb{Z})$ with ...
3
votes
2answers
82 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 ...
1
vote
2answers
34 views

Prove that numbers divisible by $p$ but not by $p^2$ are quadratic non-residues of $p^n$

Prove that numbers divisible by $p$ but not by $p^2$ are quadratic non-residues of $p^n$ This showed up in Disquisitiones Arithmeticae, article 102, but I fail to see why it must be true. My attempt ...
0
votes
1answer
43 views

Distribution of non-negative $y$ in OEIS A205535

While implementing Paul Underwood's algorithm[1] for a small machine with only 16 bit native wordsize I found that $y$ ($y$ in OEIS, $a$ in the paper) cannot exceed 177 without using big integers and ...
4
votes
0answers
150 views

A square modulo every prime is a square. Proof valid?

As Eric Schneider asked, "Am I mistaken, or does the following (actually) elementary proof work?" Theorem. Any integer which is a square modulo every prime is a square. Lemma. For any odd prime $p$, ...
0
votes
2answers
37 views

$n^2 \equiv (p-1) \mod p$ where $p$ is a Pythagorean prime.

let $p$ be a Pythagorean prime, and $n$ some integer. Does there necessarily exist a solution to the concurrency $n^2 \equiv (p-1) \mod p$? I've been studying this problem for the last 6 hours, and to ...
1
vote
2answers
60 views

Independence of shifted squares mod p

Given an odd prime $p$, let $S\subseteq \mathbb F_p$ be the set of quadratic residues modulo $p$. Given $a,b\in \mathbb F_p$ we write $aS+b$ for the set $$aS+b:=\{t\in\mathbb F_p:\ t=ax^2+b \text{ for ...
1
vote
1answer
39 views

finite field quadratic residue “counterpart”

I have a Zp finite field, and there are (p-1)/2 quadratic residues. So leaving 0 aside, there are exactly half quadratic residues. Now, I need to create a 1-1 mapping between quadratic residues to ...