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

762 questions
Filter by
Sorted by
Tagged with
1 vote
32 views

### Number of Residues of $x^n \pmod{p}$

I wanted to prove that when $n<\frac{p-1}{2}$ for prime $p$, then $x^n$ takes on more than or less than, but not equal to $3$ residues modulo $p$, for $x$ over the integers. Obviously when $p\mid x$...
63 views

### Curious about the meaning of the term '&c' in Legendre's paper [closed]

In Legendre's paper "De Nouvelles Méthodes pour la Détermination des Orbites des Comètes", the term $\&c$ is used. I'm not familiar with that terminology, but it seems to me that it ...
• 130
43 views

### How can one go about determining which primes $p>3$ satisfy the Jacobi symbol $(\frac{-3}{p})=1$? [closed]

I know how to do this for a positive 3, but the -3 is throwing me off a little. I’m not exactly sure how to proceed with determining the primes to satisfy that Jacobi symbol. Thanks for any help 61 views

### What's the link from $2^u-1$ to the multiplicative order?

I am reading this paper, but I will write everyting I need for my question here. So, long story short, we have a proth-number $n$, i.e. $n = h\cdot 2^k+1$ for odd $h<2^k$. We are looking for ...
• 140
28 views

### First Element $D$ such that $\left(\frac{D}{n}\right) \neq 1$ for given $n$.

I am reading this paper, but for my question, you don't have to. Let $n$ be a Proth-number, i.e. $n = h\cdot 2^k+1$ for $k\geq 2$ and an odd $h$ and $h<2^k.$ Now I am looking for elements $D$ such ...
• 140
1 vote
52 views

### Infinitely many primes $q$ such that $p$ is a quadratic residue modulo $q$

For primes $p,q\equiv 1\pmod 4$, I want to know if there are infinitely many $q$ such that $p$ is a quadratic residue modulo $q$? This question is important to me for understanding whether the ...
• 942
60 views

• 140
1 vote
31 views

• 2,182
21 views

### Legendre symbol and formula for 2 quadratic residue modulo p

$$\left(\frac{2}{p}\right) = (-1)^{(p^2-1)/8}$$ I am trying to understand the proof of the above result from the book of Rosen. The same proof is also given in the following link. But how the exponent ...
• 646
1 vote
113 views

### A primitive root modulo p is a primitive root modulo $p^2$ if and only if $g^{p-1} \not\equiv 1 \mod{p^2}$

$p$ is an odd prime. I'm starting with number theory and I'm completly stuck with this question. In general, I don't really know how to approach the proves. Then I'm also supposed to prove that either ...
• 87
29 views

### If $p$ is a prime where $p=4k+3$ and $a$ is a quadratic residue modulo $p$, then exactly one if its roots is a QR modulo $p$?

I recall encountering a theorem which stated something like: if $p$ is a prime of the form $p=4k+3$ and $a$ is a quadratic residue (QR) modulo $p$, then exactly one if its roots is a QR modulo $p$. I ...
• 1,555
18 views

• 148
70 views

### solve diophantine equation $a+b+2ab=n$

I need to find the samllest positive integer value of a for which $(n - a) / (1 + 2 a)$ is an integer. where n is a given natural number . In other words solve diophantine equation for postive $a$, $b$... 25 views

### Because it is enough to calculate these values to find the quadratic residue $x^2 ≡ a (mod 13)$ [duplicate]

Let $m$ be a positive integer and $a$ any integer such that $(a, m) = 1$. Then $a$ is a quadratic residue of $m$ if the congruence $x^2 ≡ a (mod m)$ is solvable; otherwise, it is a quadratic ...
• 2,733
37 views

### What is the number of quadratic residues in $Z_{11^4}$? [closed]

I am stuck on this question. We know there exists (p-1)/2 number of quadratic residues in $Z_{p}$, how about in $Z_{p^a}$? Can we approach it by Hensel's Theorem? For example, What is the number of ...
• 21
120 views

### Is there any way to predict the largest number of consecutive quadratic or cubic residues modulo prime $p$?

We all know that $a$ is a quadratic residue modulo $p$ if and only if $a^{(p-1)/2} \equiv 1 \pmod p$, also $a$ is a cubic residue modulo $p$ if and only if $a^{(p-1)/3} \equiv 1 \pmod p$. Now, for a ...
214 views

### number of solutions to $x^2 + xy + y^2 = 0\mod p$

Let $p$ be an odd prime congruent to $2$ modulo $3$ and $c$ an integer between $1$ and $p-1$. Let $\chi(x)$ denote $\left(\dfrac{x}{p}\right)$ (the Legendre symbol modulo $p$ for $x$). How many ...
• 1,127
99 views

### Proving $b^n-1$ is not a perfect square for any $b, n \geq 2$

I am currently attempting to prove that $b^n - 1$ is not a perfect square for any integers $b$ and $n$ greater than 1. I've gotten most of the way using a straightforward argument using quadratic ...
• 333
81 views

### Quadratic residue and Chinese Remainder Theorem [duplicate]

I have been casually reading a set of notes (page 30 in reader) on number theory, but I am not certain on one of the steps in the reasoning. Here is a quote: What can we say about $w^2 ≡ −3\mod 4n$? ...
• 1,412
99 views

### Sum of squares and quadratic residues

I found the following statement: "If sum of three numbers which are squares is divisible by $9$, then difference of two of these three numbers is divisible by $9$." This can be proved by ...
• 341
190 views

For a positive integer $n$, let $a(n)$ the smallest number $k>0$ such that $-n$ is not a quadratic residue modulo $k$. Using CRT, we can prove that all values of $a(n)$ are prime powers, and every ... 59 views

### Explicit description of primes for which $2$ is a quartic residue?

According to this SE question (and the internet more generally), $2$ is a quartic residue modulo a prime $p\equiv 1\pmod{4}$ if and only if $p$ may be written in the form $a^2 + 64b^2$ for integers $a$...
• 3,647
1 vote
72 views

### Evaluate a kronecker symbol sum: $\sum\limits_{n=1}^\infty \frac {\big(\frac n x\big)}n$ and $\sum\limits_{n=1}^\infty \frac {\big(\frac xn\big)}n$

The Kronecker Symbol $\left(\frac nm\right)$ has a range of $\{-1,0,1\}$ and $\sum\limits_{n=1}^\infty\frac{(-1)^n}n=-\ln(2)$, so we combine to find the following with the using software. Also note ...
• 7,804
27 views

### Equal Legendre symbols.

Any hints for proving that if $p$ and $q$ are odd primes such that $p=4a+q$ for some integer $a$ then $\left(\frac{a}{p}\right) = \left(\frac{a}{q}\right)$? I have tried using quadratic reciprocity ...
621 views

### Can we generalize the quadratic formula to modular arithmetic?

Does the quadratic formula $\displaystyle x = \frac{-b \pm \sqrt{b^2-4ac}}{2a}$ hold modulo $n$ for $ax^2 + bx + c \equiv 0 \pmod n$? Computing the square root would require factoring $n$ and using ...
• 267
1 vote