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
53 views

Proving that if prime p>3 divides a^2 + 12, then p is congruent 2(mod 3)

Prove that if prime $p>3$ divides $a^2 + 12$, then $p$ is congruent $2\pmod 3$. I tried splitting (-12/P) to (-1/P) * (3/P) and solving 4 different cases to find when (-12/P) = 1, but I got that p ...
0
votes
1answer
97 views

Quadratic residue test for mod powers of 2

For odd primes, you can test using Euler's criteria if a number is a Quadratic Residue $\bmod p$. I am looking for a test for mod powers of 2 (which are even & hence cannot use Euler's criteria). ...
5
votes
1answer
75 views

What is the most complete binary quadratic form table?

Is there a free, easily accessible quadratic form resource — maybe even just a big web-accessible table — which shows “all known results” [reasonably speaking] about numbers of the form $mx^2+ny^2$ ...
2
votes
0answers
61 views

Question about Legendre Symbol and Division Q12(a) [closed]

Let $q>3$ be an odd prime and let $q=2Q+1$. Prove that: (a) $q\,|\,(3^Q-1) \iff q\equiv ±1 \pmod {12}$ adpated from Number Theory with Applications, James A. Anderson, James M. Bell. Ch 3.9 Q12 (a) ...
0
votes
2answers
34 views

Showing $\sum_{m=1}^{q-1}m^{(q+1)/2}\equiv0\bmod{q}$, where $q$ is an odd prime congruent to $3 \bmod{4}$

I'm reading through Davenport's "Multiplicative Number Theory", and came across this expression on page 53. $$ \sum_{m=1}^{q-1} m^{(q+1)/2} \equiv 0 \mod q, $$ where $q$ is an odd prime ...
2
votes
1answer
61 views

An exercise in “Number Theory” by Shafarevich and Borevich [duplicate]

I have trouble in solving a basic exercise of the book Number Theory by Shafarevich and Borevich. It is exercise 4, chapter 1, page 4 in my edition. It goes as follows: Using the properties of the ...
0
votes
0answers
15 views

Number of Quadratic residues less than $p/3$

Suppose that $p\equiv 1\mod 4$ is a prime. I am interested in getting a formula for the number of quadratic residues less than $p/3$. The interest is because there are $(p-1)/4$ quadratic residues ...
1
vote
3answers
74 views

Perfect squares and cubes in quadratic number fields

Suppose we are given a quadratic number field $\mathbb{Q}(\sqrt{d})$, for some integer $d$ which is not a perfect square. I wish to study when is an element $\alpha \in \mathbb{Q}(\sqrt{d})$ a perfect ...
0
votes
1answer
43 views

Why is $\left( \frac {a}{p} \right)= 1$ equivalent to $p$ satisfying some condition mod $4a$, for odd prime $p$?

Basically title: Why is $\left( \frac {a}{p}\right)$ (the Legendre symbol) $= 1$ equivalent to $p$ satisfying some condition mod $4a$, for odd prime $p$? (For example, $\left( \frac {3}{p}\right)=1 \...
0
votes
2answers
62 views

A doubt in the proof of $\mathbb{Z} + \mathbb{Z}\sqrt m$ is not Euclidean with respect to $\phi_m$

I am reading 'Introductory Algebraic Number Theory' written by Saban Alaca and Kenneth S. Williams. Theorem 2.3.1 says that Let m be a positive squarefree integer. If there exist distinct odd primes ...
3
votes
4answers
282 views

Prove that there are quadratic residues that differ by 6

Let $p \geq 19$ be a prime number. Prove that in the set $\{1,..., p-1\}$ there exist two quadratic residues (QR) that differ by 6. My attempt: If 2 is a QR, then (2,8) is solution. If 3 is QR, then (...
1
vote
1answer
83 views

Divisibility between polynomial expressions [closed]

Given the expression $$ x = \frac{n^2 -bn+c}{(2n+k)-b}$$ For $b$ and $c$ integer coefficients, $k$ is any integer constant, and index $-\infty <n<\infty$, 1. What is the relationship that must ...
0
votes
1answer
73 views

$p \geq$ 7 show $\Big( \frac{n}{p} \Big)=\Big( \frac{n+1}{p} \Big) =1$ for atleast one n in the set $\{ 1,2,\ldots,,9 \}$

Suppose that p is prime $\geq$ 7.Show that $\Big( \frac{n}{p} \Big)=\Big( \frac{n+1}{p} \Big) =1$ for atleast one n in the set $\{ 1,2,3,\ldots,9 \}$. I have read this understood For any prime p>5 ...
0
votes
0answers
48 views

Jacobi Symbol walk through questions

I am reading the book Introduction to Modern Cryptography second edition by Katz et al. The Jacobi Symbol is defined on page 536 and I have included a picture below. I was able to understand most of ...
1
vote
0answers
32 views

Jacobi Quintuple Product Identity

I have to show the Jacobi Quintuple Product Identity $$\prod_{n = 1}^{\infty} (1-q^n)(1- \zeta q^{n-1})(1-\zeta^{-1} q^{n})(1-\zeta^{2} q^{2n-1})(1-\zeta^{-2}q^{2n-1}) = \sum_{n \in \mathbb{Z}} q^{\...
1
vote
1answer
25 views

Jacobisymbols modulo $pq$, both prime

I am trying to find the number of $a$'s for which $$\left( \frac{a}{pq} \right) = 1$$ with $p$ and $q$ both prime, but I am not sure how to approach this problem. I was using the identity with the ...
1
vote
0answers
29 views

If the congruence $ x^2 \equiv n \bmod{P} $ has a solution then $(n \mid p_i) = 1 $ for each prime $ p_i $ that divides $ P $

From section 9.7 "The Jacobi symbol" of Introduction to Analytic Number Theory by Tom M. Apostol Definition If $P$ is a positive odd integer with prime factorization $$ P = \prod_{i=1}^r ...
3
votes
1answer
45 views

Sums of divisors of a Jacobi symbol

$$f(n)= \genfrac(){}{0}{-15}{n}$$ if $n \neq 1$ is odd. What is $\sum_{d \mid n}f(d)$ ? Here is what I tried : Let $n=p_1^{a_1} \cdot \cdot \cdot p_r^{a_r}$, for $p_1,...,p_r$ odd primes. If $p_1,...,...
0
votes
1answer
12 views

Hasse-Minkowski principle and square theorems

This is a question in the same spirit than this one, trying to prove algebraic number theoretic statements from zeta functions. I want to prove the Hasse-Minkowski principle for quadratic forms in two ...
1
vote
0answers
26 views

When is $x$ a square in $\mathbb{F}_p[x]/(Q) $?

Let $p$ be a prime and $Q$ be an irreducible polynomial over $\mathbb{F}_p[x]$. Which are all $p$ and $Q$ such that there exists a polynomial $R(x) \in \mathbb{F}_p[x]$ such that $Q$ divides $x - R^2$?...
0
votes
1answer
91 views

Find all solutions of $x^2 \equiv 9 \pmod{85}$

I am asked to solve this problem, and I know how to solve congruences of degree $2$ modulo a prime $p$, but note that $85=5\cdot 17$ is a product of two primes. On the fly I managed to rewrite the ...
2
votes
1answer
77 views

Prove that $x^4 \equiv a^2 \pmod p$ is solvable for all $a$

Let $p$ be a prime such that $p \equiv 3 \pmod{4}$ Prove that $x^4 \equiv a^2 \pmod p$ is solvable for all $a$. I'm asked to work out this problem and I'm wondering if my approach is correct? My ...
0
votes
1answer
44 views

Why does $a^n \mod p$ always result in a number with Legendre symbol as 1?

I noticed that the following expression $a^n\mod p$ where p is a prime and $n >=1$ and $n <= p$ always results in a number with Legendre Symbol (with p as the prime) as 1. I tested it out with a ...
1
vote
0answers
42 views

Formula for the root of $x^2=-3\mod n$ when $n=p_1^{k_1}\cdots p_l^{k_l}$ and $p_i$ primes equal to $1\mod 3$

Consider the equation $$x^2=-3\mod n,$$ where $n=p_1^{k_1}\cdots p_l^{k_l}$ with $p_i$ primes equal to $1\mod 3$. Notice that any such $n$ can written as $a^2+3b^2$ (by a theorem of Fermat) for some ...
0
votes
1answer
96 views

Solve $x^2 \equiv -1 \pmod{41} $ [duplicate]

Using Legendre's symbol, knowing that $41 \equiv 1 \pmod{4}$ we can solve said equation. Then, I looked at the residue classes and I just counted my way to the solution $x = 9$. Verifying, $9^2 = 81$ ...
2
votes
1answer
52 views

Question about the Legendre's symbol: $\left(\frac{p-1}{5}\right) \overset?= \left(\frac{5}{p}\right)$

I was reading about Legendres symbol (number theory) and encountered the following equality: I don't understand how they got $$\left(\frac 3p \right) = (-1)^{\frac{p-1}{2}\frac{3-1}{2}}\left(\frac{p-...
2
votes
1answer
73 views

The sum of quadratic residues mod $p$ is $0$

I'm trying to solve this problem: If $p$ is congruent to $1$ mod $4$, then the sum of the quadratic residues mod $p$ is $0$. (Where $p$ is an integer prime) But I seem to have proven this holds for ...
3
votes
1answer
71 views

Using Quadratic Residue to show that $2^m-1$ doesn't divide $3^n-1$

Show that if $m$ is congruent to $n$ modulo $2$ and $m>1$ then $2^m-1$ cannot be a divisor of $3^n-1$ What I have tried: I showed that if $p$ is a divisor of $2^m-1$ then if $m$ and $n$ are odd ...
1
vote
1answer
55 views

Using quadratic residue

show that $2b^2+ 3$ cannot be a divisor of $a^2-2$ I have tried working with residue of $2$ modulo $p$ where $p$ is a divisor of $2b^2+3$ but couldn't stablish the result.
2
votes
1answer
47 views

Binomial theorem and a congruence modulo $2^{2m+2}$

I'm interested in the congruence problem $$(1 + 2^m)^{2x} \equiv 1+ 2^{m+1} \pmod{2^{2m+2}}\,,\quad m \geq 2\,.\quad(\dagger)$$ Though I can solve it for various small values of $m$, I still haven't ...
0
votes
0answers
17 views

Numbers represented as a sum of two coprime squares [duplicate]

Given a positive integer $n$, is it possible to represent $n$ as a sum of coprime squares iff $v_2(n) \leqslant 1 $ and no prime $p \equiv -1\pmod{4}$ divides $n$? Clearly any $n$ violating the two ...
0
votes
1answer
35 views

How to prove these pseudo-random number generators don't repeat until running through the entire set?

I just asked this question to find an algorithm for a pseudo-random number generator that generates 100% unique numbers for a bounded set of inputs. There are two answers I've seen. First is this one, ...
1
vote
1answer
46 views

Proof of $n$ being quadratic residue for primes of the form $4n+1$

I'm trying to prove the following statement: If $4n+1$ is a prime $p$, then $n$ is a quadratic residue $\bmod p$. For this, I thought I could evoke the quadratic reciprocity law and deduce: $$\...
0
votes
1answer
99 views

Showing that $p$ is a Fermat prime if and only if every quadratic non-residue mod $p$ is also a primitive root mod $p$ [duplicate]

I want to show that $p$ is a Fermat prime $\iff$ every quadratic non-residue of $p$ is also a primitive root mod $p$ These are some facts that I know: $F_n = 2^{2^n} + 1$ Every prime divisor $p$ of $...
2
votes
2answers
83 views

Find all $f(X)\in\mathbb{Z}[X]$ such that $\left(\frac{f(n)}{p}\right)=\left(\frac{n}{p}\right)$ [Legendre symbol and $p$ is a fixed prime]

Question: Let $f(X)\in\Bbb{Z}[X]$ be a non-constant polynomial such that $$\left(\frac{f(n)}{p}\right)=\left(\frac{n}{p}\right)$$ where $\left(\frac{\cdot}{p}\right)$ is the Legendre symbol and $p$ is ...
0
votes
1answer
39 views

Gaussian sets modulo $p$.

I have the following problem, given the definition: Let $p$ be an odd prime, and let $S$ be a set of $(p-1)/2$ integers. We call $S$ gaussian set modulo $p$ if $S\cup-S=S\cup\{-s\mid s\in S\}$ Is a ...
3
votes
1answer
180 views

$24ml+1=k^2$ has no solution for all $l=1 \dots m$

Investigating solutions of $$24ml+1=k^2$$ for $l=1\dots m$ The question is to find the $m$-s for which the above equation has no solution for all $l=1..m$-s. The first few $m$-s are: $$3, 9, 24, 27, ...
2
votes
1answer
117 views

Solving Equation of form: *num* = $x^3 + ax^2 + bx + c$.

The solution to the following: $$ 45113 = x^3 + ax^2 + bx + c $$ is: $$ 45113 = 31^3 + 15 · 31^2 + 29 · 31 + 8 $$ My question is how does one go about solving this set of equation, I'd like to write a ...
2
votes
1answer
47 views

Proving that if $a$ is not a quadratic residue, then $a^{p'}\equiv -1\pmod p$: Is my proof correct?

On Courant/Robbins' "What is mathematics?", it says that: Due to Fermat's Little Theorem, we have $a^{p-1}\equiv 1 \pmod p$. This suggests that we define $p'=\frac{p-1}{2}$ and factor the ...
1
vote
1answer
33 views

$X^2 + Y^2 \equiv 0 \pmod p$ implies that $-1$ is a square in $\mathbb{Z}/p\mathbb{Z}$

I know that similar questions have been asked several times in the past but I want a precision on a part of the proof. Let $n = x^2 + y^2$ and $p$ be a prime factor of $n$. Let $d = \text{gcd}(x,y)$ ...
0
votes
0answers
23 views

Demonstrating quadratic residues through three different lemmas

I'm trying to prove that 7 is quadratic residue module 29 using Euler's and Gauss's lemmas. The demonstration with Euler's was immediate (since $7^{14} \equiv 1 \pmod {29} $), But I don't know how to ...
0
votes
0answers
52 views

Square of quadratic gauss sum

I know that if $g$ is the quadratic Gauss sum for $r$th root of unity, then $g^2=\pm r$. I know, how to prove it using $g=\sum_{i=0}^{r-1}\left(\frac ir\right)\zeta^i$, but can we prove that using the ...
1
vote
1answer
30 views

Quadratic gauss sum equivalence of definition

Let $r$ be a prime number and $\zeta_r$ be the $r$th rot of unity. I know quadratic gauss sum can be expressed in two ways, $g=\sum_{i=0}^{r-1}\zeta_r^{i^2}$ and $g=\sum_{i=0}^{r-1}(\frac{i}{r})\...
1
vote
1answer
92 views

Quadratic form Gauss sum and quadratic residue

Let $Q(n_1,n_2,\ldots,n_r)$ be a quadratic form of several variables with integral coefficients. Let $q$ be a prime and let $0<a<q$. We are interested in the associated Gauss sum $$S(a,q)=\sum_{...
2
votes
1answer
65 views

Legendre symbols

So for odd prime $p$, I have Legendre symbol $(\frac{-1}{p}) = (-1)^{(p-1)/2}$, and let $n\geq 3$ be an odd positive integer. I have to show that for odd positive integers $n_1$ and $n_2$, we have $\...
2
votes
1answer
67 views

Prove that $x^2\equiv a\pmod {2^m}$ has exactly 4 solutions if $a\equiv 1\pmod8$.

An excercise 11.6.17 of "Number Theory: A Lively Introduction With Proofs Applications and Stories" involves prooving the following theorem: Let $a,m\in \Bbb Z, m \geq 3$. The equation $x^2\...
0
votes
0answers
53 views

Does ⋮ mean “is divisible by” in mathematical notation?

For example, $5(2+3m)⋮5$ if m is an integer. My teacher said yes but I cant find anything about this tiple colon ⋮ online
0
votes
0answers
53 views

$p \geq 7$ is prime, show $p \equiv 1 \; (mod \; 3) \iff (\frac{-3}{p}) = 1$

$p \geq 7$ is prime, show $p \equiv 1 \; (mod \; 3) \iff (\frac{-3}{p}) = 1$ I'm not sure where I can start, at my use I have quadratic reciprocity but that doesn't look like it will work all the time ...
1
vote
0answers
168 views

A new method for finding a solution (when they exist) to $x^2 = a \pmod p$?

For prime $p \ge 2$ define a set $S \subset \Bbb N$ by $\quad S = \{t^2 \mid t \ge 1 \land t^2 \lt p\}$ Let $a$ be an integer satisfying $\quad 1 \le a \lt p$ Conjecture: The equation $x^2 \equiv a \...
1
vote
1answer
108 views

For odd $n$, if $x^2 = a \pmod{n}$ has a solution then at least one solution has a specific representation.

Update: ̶F̶o̶r̶ ̶o̶d̶d̶ ̶$n$,̶ ̶i̶f̶ ̶ $x^2 = a \pmod{n}$ ̶h̶a̶s̶ ̶a̶ ̶s̶o̶l̶u̶t̶i̶o̶n̶ ̶t̶h̶e̶n̶ ̶a̶t̶ ̶l̶e̶a̶s̶t̶ ̶o̶n̶e̶ ̶s̶o̶l̶u̶t̶i̶o̶n̶ ̶h̶a̶s̶ ̶a̶ ̶s̶p̶e̶c̶i̶f̶i̶c̶ ...

1
2 3 4 5
15