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

2
votes
1answer
31 views

Solution to equation modulo p

Under the assumptions that $$p\cong 1 \mod 5$$ and $$g = 2(c+c^{-1})+1$$ where $c$ has order $5$ modulo $p$. I need to show that $g^2 \cong 5 \mod p$. I have that $$g^2=4(c^4+c^3+c^2+c)+9$$ I know ...
1
vote
1answer
20 views

Arbitary number of primes pairwise quadratic residues

For each $n \in \mathbb{N}$ show that there exists primes $p_1,p_2,\dots ,p_n$ so that $p_i$ is a quadratic residue modulo $p_j$ for each $i \neq j$. I was given a hint that you can find these primes ...
-1
votes
1answer
34 views

Algebra of the law of quadratic reciprocity [closed]

I have seen some examples that use the law of quadratic reciprocity in the form $$\left(\frac{p}{q}\right)=(-1)^{\left(\frac{p-1}{2}\right)\left(\frac{q-1}{2}\right)}\left(\frac{q}{p}\right)$$ I ...
1
vote
4answers
33 views

The number of quadratic residues modulo p in the set ${1,2,…,p-1}$ [duplicate]

Is it always true that the number of quadratic residues modulo p of the set ${1,2,...,p-1}$ is $\frac{p-1}{2}$ implying the rest are quadratic non-residues? if so why is this so?
1
vote
0answers
13 views

How to use Logarithm in the Sieving step of Quadratic Sieve technique

I am working on a program to factor large semi-prime numbers. I am using the simple Quadratic Sieve technique. My program works well but lot slower because during the sieving process (when I was ...
2
votes
0answers
50 views

Least Non-Square Quadratic Residue

There's a lot of work on the least quadratic non-residues for a given modulus p (usually prime), with research on bounds and distributions providing some interesting results. The justification for ...
1
vote
1answer
40 views

Polynomial evaluates to quadratic residue in $p$ cases

This exercise popped up in a chapter on Legendre symbols. Let $p$ be a prime $3$ $(\textrm{mod } 4)$, and $f(x) \in \mathbb{F}_p[x]$ a polynomial of odd degree. Show that the number of solutions $(...
4
votes
1answer
39 views

Shifting quadratic residues modulo n

I'm trying to solve a rather specific problem involving quadratic residues. Let $p,q$ be primes $(q > 2)$, such that $p = 2q + 1$, i.e. p is a safe prime. $\mathbb{Z}^{*}_{p}$ is a multiplicative ...
0
votes
1answer
33 views

Chinese remainder theorem and quadratic congruences

By Chinese remainder theorem there is a solution to $x \equiv a_{1} \pmod{ p_{1}}, \ ..., \ x \equiv a_{k} \pmod{ p_{k}}$ if $p_{1}, \ ..., \ p_{k}$ are pairwise coprime and $a_{1}, \ ..., \ a_{k}$ ...
13
votes
1answer
267 views

Proving or disproving $12\mid x$ given $x^2+2\mid y^2-2$

Let $x$, $y$ be positive integers such that $x^2+2\mid y^2-2$. Prove or disprove that $12\mid x$. This conclusion comes when I was dealing with another problem, and I feel it is right because when $x=...
2
votes
1answer
59 views

Congruence and quadratic residues

Let $p_1$, $p_2$, $p_3$ be distinct primes satisfying $p_1 \equiv p_2 \equiv p_3 \equiv 5 \pmod 8$, such that $p_i$ is a quadratic residue modulo $p_j$ for any $i\neq j$. Prove that, for any prime $p$,...
1
vote
1answer
16 views

Show that $a$ generates the group of units $(\Bbb{Z}/F_n\Bbb{Z})^\times$

Let $F_n=2^{2^n}+1$ be a Fermat prime and let $a\in\Bbb{Z}$ such that $F_n\not| a$ and $a$ is not a quadratic residue modulo $F_n$. I want to show that the class $a+(F_n)$ generates the group of ...
1
vote
1answer
34 views

Quadratic residue

Show that there are infinitely many pairwise coprime integers $d$ for which there is at least one integer $c$ so that $a^2 + b^2 \equiv c \pmod d$ has no integer solutions. I see that c must be from ...
0
votes
1answer
38 views

calculate the order of the subgroup of n-th residues mod n^2

Suppose $n=pq$ where $p,q$ are prime. A number $z$ is said to be a $n$th-residue modulo $n^2$ if there exists $y\in \mathbb{Z}_{n^2}^*$ such that $z = y^n \bmod n^2$. It's claimed by this paper that ...
7
votes
2answers
85 views

Finding quadratic residues without Legendre symbols

I ran into two very similar problems concerning quadratic residues, and I'm having a bit of trouble working through them. These problems are supposed to rely exclusively on the theory of cyclic groups,...
5
votes
2answers
77 views

Prove this equation has no integer solutions: $x^p_{1}+x^p_{2}+\cdots+x^p_{n}+1=(x_{1}+x_{2}+\cdots+x_{n})^2$

Let $ p\equiv2\pmod 3$ be a prime number. Prove that the equation $x^p_{1}+x^p_{2}+\cdots+x^p_{n}+1=(x_{1}+x_{2}+\cdots+x_{n})^2$ has no integer solutions. This problem is from the (Problems from the ...
9
votes
1answer
141 views

Congruence about Fibonacci numbers

Let $$ F_{n} = \frac{1}{\sqrt{5}} \left[ \left( \frac{1+\sqrt{5}}{2}\right)^{n} - \left( \frac{1-\sqrt{5}}{2} \right)^{n} \right] $$ be a Fibonacci number. If $p\neq 2, 5$ is a prime, then I want ...
1
vote
2answers
45 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
17 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
31 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
37 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
31 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
22 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
52 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
121 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
30 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
141 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
29 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
180 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
66 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
30 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
78 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
2answers
48 views

Solution to a system of quadratic congruences.

The following is a system of quadratic congruences: $$\left\{\begin{array}{cl}x^{2}\equiv a&\pmod{3}\\x^{2}\equiv b&\pmod{7}\end{array}\right.$$ If $\left(\frac{a}{3}\right)=1=\left(\frac{b}{7}...
1
vote
1answer
108 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
73 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
31 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
57 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
86 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
32 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
59 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
215 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
46 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
58 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
56 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
76 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
169 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
118 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
123 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{...