Stack Exchange Network

Stack Exchange network consists of 175 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$.

1
vote
2answers
39 views

Prove that if $a^{(p-1)/2}\equiv 1 \pmod{p}$ then $a$ is a quadratic residue modulo $p$

I know how to prove this the other way, but I don't see how the if and only if statement works in this direction. One thought I had was to try to show that the exponent was even as I know that this is ...
1
vote
0answers
10 views

Quadratic and Cubic Fractional Residues

Is there any method to find out the characterization of all primes $p$ such that $\frac{a}{b}$ is a quadratic residue modulo $p$ such that $a$ and $b$ are primes? Is there any method to do the same ...
1
vote
1answer
21 views

Use primitive root to prove if $a^{\phi(m)/2}\equiv 1\pmod m$ then $a$ is a quadratic residue modulo $m$.

This is trivial in arguments of quadratic residues, but I couldn't solve it using primitive root. The problem seeks to use primitive root to be proved. Problem: Let $m>2$ be an integer having a ...
2
votes
1answer
33 views

Are there infinitely many finite fields of non-two prime order with consecutive quadratic residues?

I'm curious whether there are non-two prime numbers $p$ where such that fields of order $p$ have $\left\{1, 2, \dots \frac{p-1}{2}\right\}$ as their quadratic residues. This paper Real Analysis is a ...
1
vote
0answers
22 views

The sum $\sum_{r=1}^{p-1} r(r|p)$ when $p$ is an odd prime of the form $4k+3$, $k\geq 1$.

In the book Apostol Analytic Number Theory, $(r|p)$ denotes the Legendre Symbol. The exercise tell us to prove when $p\equiv 1\pmod 4$, $$\sum_{r=1}^{p-1}r(r|p)=0.$$ I can solve this quickly, but I ...
1
vote
1answer
18 views

Let $P=\{1,2,\cdots,p-1\}$, $P=S\cup T$, prove that $S$ is quadratic residues and $T$ is quadratic nonresidues.

Let $p$ be an odd prime. Assume that the set $\{1,2,\cdots,p-1\}$ can be expressed as the union of two nonempty subsets $S$ and $T$. $S\neq T$, such that the product (mod $p$) of any two elements in ...
1
vote
0answers
43 views

If $p \equiv 1 \pmod 4$ where $p$ is an odd prime, then $x^2 \equiv -1 \pmod {p^k}$ where $k$ is any integer has $2$ solutions. [closed]

How can I prove that the equation $x^2 \equiv -1 \pmod {p^k} $, where $p$ is an odd prime and $p \equiv 1 \pmod 4$ and $k$ is any integer, has exactly two solutions? Thank you!
1
vote
2answers
83 views

If $p$ is congruent to 1 mod 4 where $p$ is an odd prime, then $x^2$ congruent to -1 mod $p$ has 2 solutions.

If $p = 5$, then the values of $x$ that will satisfy the congruence $$x^2 \equiv -1 \bmod p $$ are $2, 3$ If $p = 13$, then the values of $x$ that will satisfy the above congruence are $5, 8$. And ...
0
votes
1answer
27 views

Question about using sum of quadratic residue to count points on elliptic curve in Schoof's paper

Sorry, I have a very basic question about Schoof's paper, when he is talking about taking the sum of quadratic residues to count points. "This implies that evaluating the sum $$\sum_{x \in F_p} \...
7
votes
0answers
136 views

Modular geometry: The parabolas of quadratic residues modulo $p$

[For using the available space better, I rotated the function graphs by 90 degrees.] For the quadratic function $f_1(x) = x^2$ (with $x \in \mathbb{R}$) there is only one parabola all integer points $...
1
vote
1answer
25 views

Understanding this proof regarding quadratic residues

Let $p$ be an odd prime and let $Q_p$ denote the quadratic residues modulo $p$, $N_p$ the non-residues modulo $p$. Let $X$ be some subset of $p$. Then, $$ q X \equiv X mod (p) \hspace{2mm}\forall q \...
12
votes
1answer
173 views

Visualizing quadratic residues and their structure

[I corrected the pictures and deleted one question due to user i707107's valuable hint concerning cycles.] Visualizing the functions $\mu_{n\%m}(k) = kn\ \%\ m$ (with $a\ \%\ b$ meaning $a$ modulo $b$...
0
votes
0answers
64 views

Who was the first person to prove that only primes of the form $4k+1$ can evenly divide odd integers of the form $n^2+1$?

I am writing a paper and I want to cite the person(s) who proved that only primes of the form $4k+1$ can evenly divide odd integers of the form $n^2+1$. Edit: added "odd" For example, if $n=8$, then ...
0
votes
1answer
28 views

What is the reason for taking $\omega$ to be a primitive $q$-th root unity rather than taking any $q$-th root of unity?

Let $p$ and $q$ be two distinct odd primes. Let $\omega$ be a primitive $q$-th root of unity. Consider the sum $$S = \sum_{x \in \Bbb {F_q}^*} \left ( \frac x q \right ) {\omega}^x.$$ Prove ...
1
vote
1answer
30 views

Show that $S^p = \sum\limits_{x \in \Bbb {F_q}^*} \left ( \frac x q \right ) {\omega}^{xp}.$

Let $a \in \Bbb Z$ and $p,q$ be primes. Define $\left (\frac a p \right )$ as follows $:$ $$\left(\frac{a}{p}\right) = \begin{cases}\;\;\,0&\text{ if }p \text { divides } a\\+1&\text{ if } a \...
1
vote
1answer
62 views

Finding square roots of quadratic residues in prime power field

I know that in fields of cardinality $p$, $a$ is a quadratic residue if and only if $a^{\frac{p-1}{2}}=1$ (Euler's criterion). Therefore $a^{\frac{p+1}{2}}=a$ and if also $p=3\!\!\!\mod\! 4$ we can ...
1
vote
1answer
81 views

Let $p$ an odd prime, $s$ the smallest integer quadratic non residue modulo $p$. Prove that $p > 2s^2-s$ if $-1$ is quadratic residue modulo $p$.

I'm suffering with a number theory question. Let $p$ an odd prime, $s$ the smallest integer quadratic non-residue modulo $p$. Suppose $p > 5$ and $-1$ is a quadratic residue modulo $p$; then $p &...
0
votes
1answer
66 views

Is there integer $x$ such that $79|7x^2+4x-23$

Is there integer $x$ such that $79|7x^2+4x-23$ ? I keep getting that there is $x$ that satisfies this condition, but online calculator keeps saying that there is not. I worked it out using Legendre'...
1
vote
3answers
29 views

Quadratic congruences equivalent statements [duplicate]

Prove that for every prime $p>3$, $L= x^2-x+2 \equiv 0\mod p$ has a solution iff $D=x^2-x+16 \equiv 0\mod p$ has a solution. This is not true, right? If $L \equiv 0$ mod$p$, then $D=L+14 \equiv ...
3
votes
0answers
56 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
31 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
80 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
30 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
53 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
174 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
40 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(...
3
votes
0answers
57 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
53 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
71 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
145 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
84 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
116 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
63 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
53 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
40 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
26 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
50 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
27 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
16 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
83 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
24 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
34 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
51 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
66 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
80 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
32 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
59 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 ...