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

Filter by
Sorted by
Tagged with
0
votes
1answer
47 views

Primes And Quadratic Residues [closed]

Below is the question: Let $p$ be a prime. Prove there exists an integer $1\le x\le9$ such that $x$ and $x+1$ are quadratic residues mod $p$. Please include a proof
0
votes
1answer
53 views

Explain Numerically The Following [duplicate]

This question is one of the unsolved problems in my Encryption and Cipher Systems subject: For prime $p>2$ and $0<a<p\,;$ $ a^{(p-1)/2}(mod \,p)= \begin{cases} 1;\ \ \ \ if \ \ \ \, a\in R_{2}...
2
votes
1answer
46 views

Using quadratic residues and/or reciprocity to prove relative primality?

I have odd positive integers $q$ and $y$, with $3q^2 < y^2 < 4q^2$, such that the following are true: \begin{align} (q^2+9) &\mid (y^2+5)(y^2+29) \\[0.25em] (q^2+2) &\mid (y^2+1)(y^...
2
votes
1answer
74 views

Quadratic residue definition

Why quadratic residue $\pmod n$ must be, by definition, relatively prime with $n$? So, for example $5$ is not quadratic residue modulo $10$? This seems unnatural. Any help?
1
vote
0answers
53 views

Little conjecture in elementary number theory

I was calcultaing quadratic residues. I noticed nice pattern: quadratic residues modulo $p^n$ where $p$ is prime are well-behaved; they always repeat after $\frac{p^n - 1}{2}$-th place (starting with $...
2
votes
0answers
36 views

Distinguishing quadratic residues of a number

Say we have a prime $p$, and its primitive root modulus $g$. Now if we have a number $x \equiv g^{2a}$ mod $p$ for $0 \le a \le p-1$, then its two quadratic residues $r_1 \equiv g^a$ mod $p$ and $r_2 \...
2
votes
1answer
43 views

Finding conditions such that $4b^2 > a^2 > 3b^2$ and $b \mid (a^2-1)$ imply $b=(a+1)/2$

Consider the set of odd positive integers $a$ and $b$ such that $4b^2 > a^2 > 3b^2$ and $b \mid (a^2-1)$. Brute-force computation suggests that $a=2b-1$ is the only solution for “most” such $b$,...
0
votes
0answers
45 views

Calculate Jacobi symbol

Calculate the Jacobi symbol $\left(\frac{n^4+n^2+1}{2n^2+1} \right)$ for every integer $n>0$. Using the properties of the Jacobi symbol, $$\left(\frac{n^4+n^2+1}{2n^2+1} \right)=\left(\frac{2n^2+...
-1
votes
1answer
23 views

Question on solutions for distinct congruence classes b mod n [duplicate]

For how many distinct congruence classes $[b]$ mod $631$ will there be integer solutions $x$ to the congruence $$x^2\equiv b\,(mod\,631)$$
0
votes
1answer
17 views

Wilson's Theorem Application to Quadratic Residues

Im a noob and trying to prove: $(m!)^2\equiv(-1)^{m+1}\textrm{(mod p)}$ using Wilson's Theorem. Although it's on Wikipedia, I want to really understand what is happening. Could someone explain how $$\...
0
votes
1answer
55 views

Need help with Jacobi symbol / quadratic nonresidues proof

I've been doing a few number theory problems online for fun and I've been having a bit of trouble with proving this one successfully: Suppose $p$ and $q$ are distinct odd primes. Prove that there ...
0
votes
0answers
48 views

How to know if a number is quartic residue or nonresidue modulo n?

I'm writing a program to calculate quadratic residue of a number and for prime number it is mentioned that if p mod 8 equals 5 then there two ways to calculate x (check the pic). the part that I don't ...
0
votes
5answers
89 views

Solving $2x^2+x-5 \equiv 0 \pmod{23}$. [closed]

Solve $2x^2+x-5 \equiv 0 \pmod{23}$ My first attempt would be splitting $23$ to its prime divisors and applying Chinese remainder theorem, but since $23$ is a prime number, I wasn't able to do it.
2
votes
1answer
41 views

Given a prime number a of the form 29 (mod 40) or 40k + 29. Show that the prime a cannot divide any integer of the form n^2 + 10.

Not sure how to approach this problem. First idea was proof by contradiction. Assume a divides n^2 + 10 and proceed from there. I couldn't reach a substantial conclusion from this approach.
0
votes
1answer
17 views

Testing for primitive roots using quadratic non residue and Jacobi symbol

Is this always true for all cases?? $a$ is a primitive root $modulo$ $n$ $⇒$ $\left(\dfrac{a}{n}\right) = -1$ Is the converse also always true? $\left(\dfrac{a}{n}\right)$ $= -1$ $⇒$ $a$ is a ...
2
votes
3answers
77 views

Show there exist integers $a$ and $b$ such that $a^2+b^2\equiv -1\mod p$

I'm asked to show there exist integers $a$ and $b$ such that $a^2+b^2\equiv -1\mod p$ for any odd prime $p$. The solution starts by saying that the subsets $\{a^2\}$ and $\{-1-b^2\}$ of $\mathbb Z/p\...
1
vote
0answers
11 views

A quadratic residue equality proof [duplicate]

Let $p$ be an odd prime, $a\in\mathbb{Z}$. Try to prove $$\sum_{y=0}^{p-1}\Big(\frac{y^2+a}{p}\Big)\equiv-1\pmod{p}\tag{1}$$ I find that when $p|a$ it obviously holds, since $$\sum_{y=0}^{p-1}\Big(\...
0
votes
1answer
38 views

Find the number of integer pairs 0 ≤ a, b ≤ 100 such that a^20 ≡ b^50 (mod 101). Need help with understanding solution

Find the number of integer pairs 0 ≤ a, b ≤ 100 such that $a^{20}$ ≡ $b^{50} \pmod {101}$. Here is the solution: "Since is prime, there exists a primitive root g in modulo 101. For some integers x ...
0
votes
1answer
40 views

What is the size of the set $\{ 0^{42}\pmod{101}, 1^{42}\pmod{101}, 2^{42} \pmod{101},…,100^{42}\pmod{101}\}$

What is the size of the set $\{ 0^{42}\pmod{101}, 1^{42}\pmod{101}, 2^{42} \pmod{101},...,100^{42}\pmod{101}\}$? How would you even start the problem? By the way, I got this problem from my number ...
2
votes
1answer
47 views

Find the sum of quadratic residues modulo $101$

Given that $2$ is a primitive root (mod $101$), find the remainder when the sum of all the quadratic residues (mod $101$) is divided by $101$. A quadratic residue $r$ is a residue (mod $101$) such ...
1
vote
2answers
30 views

If $p \equiv 3 \mod 8$ is prime and 3 is non-residue of $p$, then $p\equiv 19 \mod 24$.

I'm reading Stark's paper "a complete determination of the complex quadratic fields of class number one". He argues that if $p \equiv 3 \mod 8$ is prime and 3 is non-residue of $p$, then $p\equiv 19 \...
0
votes
0answers
42 views

Quadratic residue and cubic polynomials

The question is simple: Can $\sum_{x=0}^{p-1} (\frac{ax^3 +bx^2 +cx +d}{p} )$ be expressed as a closed form ? (It's a Legendre Symbol)
1
vote
0answers
18 views

Help regarding Quadratic Sieve

I'm working on a code that recovers/retraces the prime no's from which a 30-digit number was formed. As, this is a factorization problem I have started regarding various algorithms about it. This ...
1
vote
1answer
43 views

Square roots in $\mathbb Z_p$

Using Hensel's lemma, it's standard fair to show that if $p$ is odd, $d\in\mathbb Z$, and $(p,d) = 1$, then $\sqrt{d}\in\mathbb Q_p$ if and only $d$ is a quadratic residue mod $p$. Naturally, there ...
1
vote
0answers
31 views

Quadratic residue of composite numbers [duplicate]

If $a$ is a quadratic residue modulo $m$ and $ab \equiv 1 \;(\bmod\;m)$. Prove that $b$ is also quadratic residue modulo $m$. The above question is from Niven & Zuckerman " Introduction to the ...
0
votes
0answers
27 views

Definition of quadratic residues in $\mathbb{F}_q$, where $q = p^n$. [duplicate]

For $\mathbb{F}_p$, I know that the definiton of quadratic residue (and non-residue) is : $a $ is a quadratic residue if $gcd(a,p) =1$ (i.e $a \neq 0 $ in $\mathbb{F}_p$) and $x^2 \equiv a $ $mod(p)$...
1
vote
1answer
30 views

The product of both quadratic residues and non residues in a residue system modulo prime p

Compute the product of all the quadratic residues $a$ where $(a, p) = 1$ in a residue system modulo $p$ where $p$ is prime. Similarly, compute the product of all the quadratic nonresidues in a residue ...
2
votes
2answers
72 views

For which primes $p$ is $-1$ not the sum of two non-zero quadratic residues?

I am trying go find a characterisation of the primes $p$ for which no two non-zero quadratic residues add to $-1$. Equivalently, we are looking for the values of $p$ for which the equation $x^2 + y^2 ...
0
votes
0answers
24 views

Properties of quadratic residues

I am trying to learn some number theory by myself, and am currently learning about quadratic residues. Could somebody list some properties of $x$ if $x$ is a quadratic residue mod $n$? I think this ...
0
votes
0answers
50 views

How to read the Jacobi symbol aloud?

Suppose you're reading aloud the Jacobi symbol "$J(x, N) = -1$". Which pronunciation you find more natural?
0
votes
0answers
23 views

Show $\chi_{\pi}\left(a(-1)^\frac{p-1}{4}\right)=(-1)^\frac{a^2-1}{8}.$

I'm currently going through of Ireland and Rosen's 'A Classical Introduction to Modern Number Theory' and would like some help on CH9Ex29. I know that $a(-1)^\frac{p-1}{4}$ is primary (i.e it is ...
1
vote
4answers
104 views

Why does $x^2 \equiv 2 \pmod{5}$ have no solution?

Can someone explain why $x^2 \equiv 2 \pmod{5}$ has no solution other than trial and error? So I've shown that modulo 5, we have $0^2 \equiv 0, 1^2 \equiv 1, 2^2 \equiv 4, 3^2 \equiv 4, 4^2 \equiv 1$...
1
vote
1answer
72 views

Triples $(p,q,r)$ of primes satisfying the quadratic residue relation $\left(\frac{p}{q}\right)\cdot\left(\frac{q}{r}\right)=\left(\frac{p}{r}\right)$

I stumbled upon this problem while thinking about quadratic residues: Find all triples $(p,q,r)$ of primes such that $$\genfrac(){}{0}{p}{q}\cdot\genfrac(){}{0}{q}{r} = \genfrac(){}{0}{p}{r}$$ ...
1
vote
0answers
45 views

When or how can basic sieve failures occur, if ever?

I don't know the proper terminology for some of this (feel free to point it out!) so bear with me please. I noticed when I first started playing with $x^2+1$ primes that they can also be treated ...
1
vote
0answers
57 views

Finding all quadratic residues $\pmod{n}$ in sublinear time?

Let $n \in \mathbb{N}$. Let $R_n$ be the set of quadratic residues in $\mathbb{Z}/n\mathbb{Z}$. Suppose we are given access to a factorization for $n$ into prime powers $n = \prod_{i=1}^k p_i^{e_i}$. ...
2
votes
1answer
37 views

Is there any known configuration of primes through $n$ which covers $n^2$?

Is there any known initial arrangement of prime residues (apologies in advance, I'm going to play fast and loose with the nomenclature) through some $n$ such that for every value in $[n+1,n^2]$, some ...
2
votes
3answers
131 views

For which integer values of $n$ does there exist an integer $m$ such that $n^{3} - m^{2} = -23$?

For which integer values of $n$ does there exist an integer $m$ such that $n^{3} - m^{2} = -23$? I'm having a lot of trouble with this one, any help would be appreciated :) So far, I've seen that if ...
0
votes
0answers
49 views

Use Eisenstein's Lemma to prove that a number is a quadratic residue mod p

Let $p > 2$. Use Eisenstein’s Lemma to prove that (a) $2$ is a quadratic residue mod $p$ if and only if $p = 8k ± 1$ for some $k$ ∈ $\mathbb N$ (b) $3$ is a quadratic residue mod $p$ if and only if ...
0
votes
0answers
46 views

Find the values in the diophantine equation

Determine whether there exists a solution for equation $a^4+b^4+c^4+d^4=(8k+7) 4^{t}(abcd+1)$ where $a,b,c,d$ are positive integers, $k, t$ are non-negative integers. It seems hard; but ...
1
vote
2answers
57 views

Wilson's Theorem Lemma

I am faced with the following question in my undergraduate Number Theory textbook: Use the coefficient of x on both sides of (*) to prove that if p $\ge$ 3, then p divides a and $\frac{a}{b}$ = $ 1+ \...
2
votes
1answer
42 views

Randomness of Quadratic Residues

I am an overzealous undergraduate who is attempting to read through parts of Laszlo Lovasz's book "Graph Limits and Networks". However, it is intended for graduate readers and as such I reaching out ...
9
votes
0answers
195 views

How to prove $(\phi-1)(\phi-2)…(\phi-p) = \sqrt{5} + p\left(\frac{1}{2}+A\sqrt{5}\right) \bmod p^2$?

We consider the solution of $x^2=x+1$ and denote them as $\phi=\frac{1}{2}(1-\sqrt{5}),\bar\phi=\frac{1}{2}(1+\sqrt{5})$. Suppose $\phi \not\in \mathbb{F}_p$. In other words, $\sqrt{5} \not \in \...
0
votes
0answers
16 views

Jacobi symbol $\left(\frac{-4}{n}\right)$, where $\gcd(4,n)=1$

According to Jacobi's symbol property, we can always write $\left(\frac{ab}{n}\right)=\left(\frac{a}{n}\right)\cdot \left(\frac{b}{n}\right)$. Then $\left(\frac{-4}{n}\right)$ can always written as $\...
4
votes
1answer
43 views

Jacobi Symbol: $\sum_{n=1}^{p}\left(\sum_{m=1}^{h}\left(\frac{m+n}{p}\right)\right)^2=h(p-h)$

Show that if $p$ is and odd prime and $h$ is an integer, $1\le h \le p$, then $$\displaystyle\sum_{n=1}^{p}\left(\sum_{m=1}^{h}\left(\frac{m+n}{p}\right)\right)^2=h(p-h)$$ where $\left(\frac{m+n}{p}\...
1
vote
0answers
49 views

Jacobi Symbol: $\sum_{n=1}^{n=p}\left(\frac{n^2+a}{p}\right)=-1$

Show that if $(a,p)=1$, $p$ an odd prime then, $\sum_{n=1}^{n=p}\left(\frac{n^2+a}{p}\right)=-1$, where $\left(\frac{n^2+a}{p}\right)$ is the Jacobi symbol. This question has been taken from the book ...
0
votes
1answer
60 views

$\sum_{n=1}^{n=p}\left(\frac{n^2+a}{p}\right)=-1$. [duplicate]

Show that if $(a,p)=1$, $p$ an odd prime then, $\sum_{n=1}^{n=p}\left(\frac{n^2+a}{p}\right)=-1$, where $\left(\frac{n^2+a}{p}\right)$ is the Jacobi symbol.
0
votes
2answers
54 views

Show that $(n^5-n+3)$ is not a perfect square

I need to show that $n^5-n+3$ is not a perfect square. I think I have to use the Legendre symbol and quadratic residues, but I did not see how. Instead I tried the following: For $n=0,1$, we see ...
6
votes
1answer
200 views

Every prime occurs as the least quadratic nonresidue

It is not difficult to check that the least quadratic nonresidue modulo prime $p$ cannot be a composite number, see, for example: Quadratic nonresidues mod p. It is quite natural to ask the opposite ...
0
votes
1answer
55 views

Number of values such that quadratic residue is 1

Let $n$ be an odd integer with $i$ prime factors. how many values of $x (mod\ n)$ are there for which $x^2 ≡ 1 (mod\ n)$? I used Legendre's symbol to find the following: Let $x$ be such that $x^2 ≡ ...

1
2 3 4 5
13