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

532 questions
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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!
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 ...
27 views

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

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 ...
30 views

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 ...
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$ ---...
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 ...
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 ...
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 ...
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: ...
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 ...
### 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, ...