Tagged Questions

In number theory, the law of quadratic reciprocity is a theorem about modular arithmetic that gives conditions for the solvability of quadratic equations modulo prime numbers. (Ref: http://en.m.wikipedia.org/wiki/Quadratic_reciprocity)

24 views

For which primes $p\not=2$ is $5$ a square mod $p$?

For which primes $p\not=2$ is $5$ a square mod $p$? Using the Legendre symbol, $5$ is a square modulo $p$ if $$\left(\frac{5}{p}\right)=5^{\dfrac{p-1}{2}} \equiv 1 \pmod{p}$$ Now we have ...
20 views

let $q$ be a prime of the form $q=3r+1$ and assume that $p=4q+1$ is also a prime. Show that $3$ is a primitive root of $p$

How to even begin? The proof for if $p$ is an odd prime then $(\frac{2}{p})=(-1)^{\frac{p^{2}-1}{8}}$ seems useful but not sure how to adapt it
26 views

Help solving a question using Quadratic Reciprocity?

How do i solve this equation using Quadratic reciprocity? How many solutions does the quadratic equation $\bar{x}^{2} = \bar{2}$ have in $\mathbb{Z}_{47}$? I have no idea how to go about this i ...
69 views

Prove that a perfect square (also a perfect square backwards) is divisible by 121

Suppose that $n=x^2$ is a perfect square with an even number of base-10 digits. Assume that when n is written backwards, you get another perfect square $y^2$. Prove that 121|n. (Use the mod 11 ...
34 views

If p is a prime with p > 5, then 5 is a quadratic residue modulo p if and only if the last decimal digit of p is 1 or 9.

Use the law of quadratic reciprocity to show that if p is a prime with p > 5, then 5 is a quadratic residue modulo p if and only if the last decimal digit of p is 1 or 9. So far, I got x$^2$ = 5(mod) ...
37 views

Calculate $(\frac{3}{11})$ in the following ways…

Evaluate $(\frac{3}{11})$ Currently going through a study set on a Quadratic Reciprocity, I have to evaluate $(\frac{3}{11})$ in the following three ways: (1) Computing the squares modulo 11 (2) ...
8 views

Finding a prime in range with the largest minimal non quadratic residue

Given k, I'm trying to find the k-bit prime that has the largest minimal non-quadratic residue. I was wondering if there's any construction like that. Perhaps some use of the CRT?
20 views

Let p be an odd prime with $(a,p) = 1$ and $(\frac{a}{p})$ = 1. show that $x^2$ ≡ a (mod p)

Let p be an odd prime with $(a,p) = 1$ and $(\frac{a}{p})$ = 1. show that $x^2$ ≡ a (mod p) has precisely two incongruent solutions mod p. Having a bit of trouble with this question, we are ...
51 views

Is $x^2 ≡ 295$ (mod 2717) solvable?

Is $x^2 ≡ 295$ (mod 2717) solvable? -Having a tough time with this problem, currently covering a section on Quadratic Reciprocity Law of Gauss. After coming back to my professor, his hint was to ...
31 views

For what odd prime p is -3 a quadratic residues? Non-residue?

For what odd prime p is -3 a quadratic residues? Non-residue? Having a bit of trouble with this question, we are currently covering a section on quadratic reciprocity and didn't really see anything ...
60 views

Are there infinitely many pairs of primes, $p$ and $q$, such that $q = 4p + 1$?

How close can one come to proving that there are infinitely many primes, $p$ and $q$, such that $q = 4p + 1$? The idea for this question came from reading the question and answers posed by ...
67 views

Quadratic reciprocity: Tell if $c$ got quadratic square root mod $p$

I am reading the wiki article about Quadratic reciprocity and I don't understand how can I tell if some integer $c$ got quadratic root mod $p$? So far I am using brute search to find $y$ such that ...
36 views

Fermat's little theorem and Euler's criterion

Is it possible to find the solution of this congruence by Fermat's little theorem and how ? $$15125^{2401}\pmod {72}$$ Can somebody tell me how to do it by Euler's criterion?
39 views

I have to find the result of congruences : $$(a)\left(\frac{34}{73}\right)$$ $$(b)\left(\frac{36}{73}\right)$$ $$(c)\left(\frac{1356}{2467}\right)$$ By the way,I found that Theorem of Quadratic ...
20 views

If $p>3$ and $x^2+3y^2=p$, prove $\left(\frac{-3}{p}\right)=1$ and $p\equiv 1\pmod{6}$.

If $p>3$ and $x^2+3y^2=p$, prove $\left(\frac{-3}{p}\right)=1$ and $p\equiv 1\pmod{6}$. $$\left(\frac{-3}{p}\right)=\left(\frac{-1}{p}\right)\left(\frac{3}{p}\right)$$ We know that ...
23 views

I'm trying to determine whether the congruence $x^2+x-1\equiv0\pmod{61}$ has a solution. I know how to do this without the linear term, for instance, $x^2-5\equiv0\pmod{61}$. I can solve it just by ...
119 views

Irreducibility in a polynomial related to quadratic residues

From Romania TST 2004 Day 5 P3, I was introduced to the polynomial $$f(x)=\sum_{i=1}^{p-1} \left( \frac{i}{p} \right)x^{i-1}$$ This polynomial is clearly not irreducible - $x=1$ is a root. Even more ...
42 views

29 views

Verifying quadratic reciprocity for the Jacobi symbol

I am trying to prove: If $m,n$ are odd coprime positive integers, then $$\Big(\frac mn\Big)\Big(\frac nm\Big)=(-1)^{\large\frac{m-1}2\frac{n-1}2},$$ where $\big(\frac mn\big)$ is the Jacobi ...
58 views

What is the probability of having a quadratic residue?

Let $a$ be a random integer and $p$ be a prime. What is the probability of $\left(\frac{a}{p}\right)=1$, as $p$ goes to infinity. And similarly, what about $\left(\frac{a}{p}\right)=-1$ or $0$?
38 views

Given an integer $n>1$, I say that $r$ is a primality radius of $n$ if both $n-r$ and $n+r$ are primes. Goldbach's conjecture asserts that every integer greater than $1$ admits a primality radius. ...
62 views

Describe all odd primes p for which 7 is a quadratic residue

I need to describe all odd primes $p$ for which $7$ is a quadratic residue. Now let $\left(\frac{a}{b}\right)$ be the Legendre Symbol. Then if $7$ is a quadratic residue $p$ we must have: ...
34 views

I know $x^2\equiv-7\pmod7$ has solutions. How can I check if $x^2\equiv-7\pmod{49}$ has solutions? I know $-7\equiv42\pmod{49}$ but $49$ isn't a prime so I can't use Euler's criterion. How shall I do ...
45 views

When is $2$ a quadratic residue mod $p$?

For which prime numbers $p$ is $2$ a quadratic residue modulo $p$. I know that $2$ is a quadratic reside iff $$2^{\frac{p-1}{2}} =1 \; \bmod \;(p)$$ so $$2^{p-1} =1 \; \mod \; (p).$$ But I ...
76 views

Describe the set of odd primes such that $\left(\frac{-5}{p}\right) = 1$ (Legendre Symbol)

Okay, so $\left(\frac{-5}{p}\right) = 1$. I am assuming that I can start this by saying $\left(\frac{-5}{p}\right) = \left(\frac{5}{p}\right) \times \left(\frac{-1}{p}\right)$. There are well ...
61 views

I've been asked to see if $x^2\equiv83$ $(\mathrm {mod} \ 101^{2000})$ has solutions. Now I know $x^2\equiv(\mathrm{mod} \ 101)$ has no solutions since the quadratic reside symbol ...
51 views

Calculating the Legendre symbols $\left(\frac{295}{401}\right)$ and $\left(\frac{713}{1009}\right)$ using quadratic reciprocity

Evaluate the following Legendre symbols using quadratic reciprocity: $\left(\frac{295}{401}\right)$ $\left(\frac{713}{1009}\right)$ I know that can flip the numbers and reduce because both $401$ ...
55 views

$\left(\frac{-3}{p}\right)=\left(\frac{-1}{p}\right)\left(\frac{3}{p}\right)=\left(\frac{-1}{p}\right)\left(\frac{p}{3}\right)^{\frac{p-1}{2}}$ $=\begin{cases}1,\:p\equiv 1\pmod{4}\text{ or ... 1answer 45 views Find all primes$p$such that$\left( \frac{-19}{p} \right) = 1$Find all primes$p$such that -19 is a quadratic residue$\bmod p$. solution: We have that$(\frac{-19}{p})=(\frac{p}{19})$, so that if$-19$is a quadratic residue modulo$p$, then$p$is a ... 1answer 41 views What is$\left[\frac{1}{2}(p-1)\right]! \;(\text{mod } p)$for$p = 4k+1$? Theorem #114 in Hardy and Wright says if$p = 4k+3$then $$\left[\frac{1}{2}(p-1)\right]! \equiv (-1)^\nu \mod p$$ where$\nu = \# \{ \text{non residues mod } p\text{ less than }p/2\}$. Is ... 2answers 28 views Quadratic reciprocity:$\left( \dfrac{-1}{p}\right) = (-1)^{\frac{p-1}{2}}$Prove$\left( \dfrac{-1}{p}\right) = (-1)^{\frac{p-1}{2}}$, where$p$is an odd prime, and the LHS is the legendre symbol. I've got$-1 = x^2 \pmod p \implies (-1)^{\frac{p-1}{2}} = x^{p-1} = 1 = ...
The law of quadratic reciprocity is given as: $(\frac{p}{q})(\frac{q}{p}) = (-1)^{((p-1)/2)((q-1)/2)}$ Apparently we can say: $(\frac{p}{q}) = (\frac{q}{p})(-1)^{((p-1)/2)((q-1)/2)}$ and ...