# 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)

46 views

23 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
30 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 ...
83 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 ...
39 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) ...
27 views

### Determine the quadratic character of $293 \bmod 379$.

Determine the quadratic character of 293 mod 379. Did several other problems like this with 3, 5, 60, -1 and 307 all mod 379 but still having a tough time with this problem. I can post up work from ...
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) ...
10 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?
21 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 ...
37 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 ...
80 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 user39898,...
69 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 ...
38 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?
40 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

71 views

### If $n\in\Bbb Z^+$ is not a square, prove exist infinitely many primes $p$ such that $\left(\frac{n}{p}\right)=-1$.

If $n\in\Bbb Z^+$ is not a square, prove exist infinitely many primes $p$ such that $\left(\frac{n}{p}\right)=-1$. Note that if $p\nmid n$ and $n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}$, ...
31 views

### Prove that $\sum^{P}_{k=1} \lfloor\frac {ka}{p}\rfloor = \frac{p^{2} - 1}{8} + \mu(a,p)$ mod$(2)$

I can prove that $\sum^{P}_{k=1} \lfloor\frac {ka}{p}\rfloor = \mu(a,p)$ mod$(2)$ where $p$ is an odd prime, $P = \frac {p-1}{2}$, $a$ is an integer not divisible by $p$, and $\mu(a,p)$ is the ...
56 views

### verify if $8x^2 - 2x - 3 \equiv 0 \pmod{75}$ has solutions or not.

verify if $8x^2 - 2x - 3 \equiv 0 \pmod{75}$ has solutions or not. I tried to write the left term in a form $y^2 \equiv a \pmod{75}$, where $a \in \mathbb{Z}$ so then I can use quadratic repriocity ...
26 views

I am trying to figure out the proof of the quadratic reciprocity law in Serre's book A Course in Arithmetic. I think my question is possible to answer independent of the book though: Let $l$ and $p$ ...
62 views

### Gauss' original proof of quadratic reciprocity

Is the original proof of quadratic reciprocity due to Gauss available anywhere online? I've been looking for quite a while now, but with no results. Most papers seem not to include it because of it ...
37 views

### Technological incompetence [closed]

I am a high school student going into my junior year. Earlier this summer, I went to a math camp at Ohio State University, and one of the assignments was to prove quadratic reciprocity. I was told ...
31 views

I am reading the proof the for odd prime $p$, $$\left ( \frac{-1}{p} \right)_2 = (-1)^{\frac{p-1}{2}} = \begin{cases} 1 \hspace{2mm} \text{for} \hspace{2mm} p \equiv 1 \operatorname{mod} 4 \\ -1 \... 1answer 32 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 ... 1answer 61 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? 2answers 81 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:$$1=\left(\...
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 ...
47 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 don'...
86 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 ...
65 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 $(\frac{83}{101})=-1$...
54 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$ ...
58 views

98 views

126 views

### Determining prime numbers p which satisfy quadratic residues modulo p

I'm learning about quadratic reciprocity and I'm stuck on an exercise. It states : Determine the congruence characterizing all prime numbers p for the following integers such that they are quadratic ...
35 views

### Proof on the Legendre Symbol

I'm working on an exercise involving the Legendre Symbol. It gives me a hint but I'm not sure how to prove it. Let p and q be odd prime numbers with $p = q + 4a$ for some $a \in \mathbb{Z}$. Prove ...
55 views