Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [legendre-symbol]

For questions involving the Legendre symbol, $\genfrac{(}{)}{}{}{a}{p}$ for integer $a$ and prime $p$.

1
vote
1answer
36 views

Legendre Symbol: show that $\left(\frac{-3}p\right)=\left(\frac p3\right)$

I am asked to solve the following question Let $p$ be a prime, $p>3$. By considering the cases $p ≡1\bmod4$ and $p≡-1\bmod4$ separately, show that $\left(\frac{-3}p\right)=\left(\frac p3\right)$....
0
votes
0answers
34 views

The law of quadratic reciprocity 'or' statement

I have just seen written that $(\frac{17}{101})$ = $(\frac{101}{17})$. But doesn't the law of quadratic reciprocity state that $(\frac{p}{q})$ = $(\frac{q}{p})$ if $p\equiv1 mod 4$ OR $q\equiv1mod4$?
1
vote
0answers
22 views

The sum $\sum_{r=1}^{p-1} r(r|p)$ when $p$ is an odd prime of the form $4k+3$, $k\geq 1$.

In the book Apostol Analytic Number Theory, $(r|p)$ denotes the Legendre Symbol. The exercise tell us to prove when $p\equiv 1\pmod 4$, $$\sum_{r=1}^{p-1}r(r|p)=0.$$ I can solve this quickly, but I ...
2
votes
1answer
54 views

Exercise on Gauss sums

Formal count of length-3 progressions, given by: $A(p)$=#{$(r,s,t): \big(\frac{r}{p}\big)=\big(\frac{s}{p}\big)=\big(\frac{t}{p}\big)=1; r \neq s; s-r\equiv t-s$ (mod $p$). Here $p$ is a prime. In ...
1
vote
0answers
27 views

Factoring out Kloosterman Sum

I'm reading Iwaniec's book and he says Kloosterman sum factors into $S(n,n;c)=S(n\bar{q},n\bar{q};r)T(n\bar{r},n\bar{r};q)$ where $n$ is square free and $c=rq$ such that $(q,n)=(q,r)=1$(i.e. $q$ is ...
0
votes
1answer
19 views

Legendre symbols and primitive roots modulo $p$ [duplicate]

Suppose that $\omega$ is a primitive root modulo $p$. What is $(\frac{\omega}{p})$? $p$ is prime.
0
votes
1answer
66 views

Is there integer $x$ such that $79|7x^2+4x-23$

Is there integer $x$ such that $79|7x^2+4x-23$ ? I keep getting that there is $x$ that satisfies this condition, but online calculator keeps saying that there is not. I worked it out using Legendre'...
0
votes
1answer
21 views

Legendre's proof involving linearity independence

Show that any polynomial of degree n is a linear combination of P0(x), P1(x), ..., Pn(x) Actually I have no idea how to start with a proof involving "any". Can someone help??
2
votes
2answers
71 views

Can a number be a quadratic residue modulo all prime that do not divide it

Is there a proof that for any number $a$, there must be at least one prime $p$ such that $(a/p)=-1$, where $(a/p)$ is the Legendre symbol? In other words, for all $a$, is there at least one prime $p$...
2
votes
1answer
71 views

$x^2 \equiv -2,2 \pmod {122}$

I am trying to solve the following problem: Which of the following congruences has solutions? How many? $$x^2 \equiv 2 \pmod {122}$$ $$x^2 \equiv -2 \pmod {122}$$ For both congruences, $122 = 2\...
1
vote
1answer
37 views

Proof that Legendre symbol $\Big(\frac{a}{p}\Big)$ is $a^{\frac{p-1}{2}}$

When $p$ is a prime, we know that Legendre symbol of $a$ is $$\left(\frac{a}{p}\right) = a^{({p-1})/{2}}$$ Suppose $a$ is a square, then $a = x^2$ for some $x$. Therefore, $a^{\frac{p-1}{2}} = x^{p-1}...
4
votes
1answer
145 views

A question about a primitive root mod $p=2^{2^k}+1$, where $p$ is prime.

Let $p=2^{2^k}+1$ be a prime where $k\ge1$. Prove that the set of quadratic non-residues mod $p$ is the same as the set of primitive roots mod $p$. Use this to show that $7$ is a primitive root mod $p$...
1
vote
1answer
55 views

Prove that there are infinitely many prime numbers $p$ such that $\left(\frac{a}{p}\right)=1$ for fixed $a$. [duplicate]

I already proved this is true for all prime numbers and clearly see how this is true for all perfect squares, I'm just having trouble expanding it to any prime factorization. If we let $a$ have prime ...
2
votes
2answers
304 views

What are the Legendre symbols $\left(\frac{10}{31}\right)$ and $\left(\frac{-15}{43}\right)$?

I have the following two Legendre symbols that need calculated: $\left(\frac{10}{31}\right)$ $=$ $-\left(\frac{31}{10}\right)$ $=$ $-\left(\frac{1}{10}\right)$ $=$ $-(-1)$ $=$ $-1$ $\left(\frac{-15}{...
1
vote
1answer
50 views

Find all primes $p$ : $x^2 \equiv 13 \pmod p$ has solutions

I'm analyzing this little problem: Find all primes $p$ : $x^2 \equiv 13 \pmod p$ has solutions Here my effort since now: If the congruence $x^2 \equiv 13 \pmod p$ has solutions, must be the ...
2
votes
0answers
311 views

Determine the Legendre symbol of $\left(\frac{14}{p}\right)$

I have been asked to determine the Legendre symbol $\left(\frac{14}{p}\right)$ for $p \geq 11$ and have made good progress, however, I am stuck at the very last hurdle. So far, I have found that \...
5
votes
1answer
89 views

If $p=a^2+b^2$ prove these consequences about $\big(\!\frac{a}{p}\!\big)$

Suppose odd prime $p=a^2+b^2$, and $a$ is odd and $b$ is even. Prove that if $b\equiv2\pmod4$, then $\left(\dfrac bp\right)=-1$ and if $b\equiv0\pmod4$, then $\left(\dfrac bp\right)=1$. What I have ...
3
votes
1answer
72 views

Proof that $5$ is a quadratic residue $(\mod p)$ with $p$ odd prime iif $p \equiv \pm 1 \mod 10$

Here I present the following proof in order to receive corrections or any kind of suggestion to improve my handling/knowledge of modular arithmetic: Prove that $5$ is a quadratic residue $(\mod p)$ ...
0
votes
1answer
37 views

Find p primes odds for Legendre symbol $(-3|p)=+1$ or $(-3|p)=-1$

First time calculating this and I apologize if I result a little bit confused; so I want to find p primes odds for Legendre symbol $(-3|p)=+1$ or $(-3|p)=-1$. I know from Legendre's original ...
0
votes
0answers
49 views

Sum of Legendre symbol $\left(\frac{n^2-a}{p}\right)$ (More explanation)

In fact, there are several same questions, but I still post it here: If $(a,p)=1$, $p$ an odd prime, then $\sum_{n=1}^{p}\left(\frac{n^2+a}{p}\right)=-1$. In those same posts, I tried to read the ...
-1
votes
1answer
37 views

If $p \equiv 3 \ (\text{mod} \ 4)$ is a prime, show $(\frac{p-1}{2})! \equiv (-1)^{t} \ (\text{mod} \ p)$ [duplicate]

If $p \equiv 3 \ (\text{mod} \ 4)$ is a prime, show $(\frac{p-1}{2})! \equiv (-1)^{t} \ (\text{mod} \ p),$ where $t$ is number of positive integers less than $\frac{p}{2}$ that are nonquadratic ...
0
votes
1answer
29 views

Advice needed to understand a theorem on Legendre symbol

Let $p$ be an odd prime. Then $\Big(\frac{2}{p}\Big)=(-1)^{\frac{p^2-1}{8}}.$ I read that this is equivalent to the following: Let $p$ be an odd prime. Then $X^2+1\equiv 0 \ (\text{mod} \ p)$ has a ...
4
votes
0answers
51 views

The Number of involutory matrices over $\mathbb{Z_p} $

I want to prove the number of 2-by-2 Involutory Matrices ($A^2=I$) over $\mathbb{Z_p}$ using quadratic residue and legendre symbol. I already know that the formula is $p^2$ for characteristic of a ...
4
votes
1answer
90 views

Let $p,q$ be odd primes such that $p-q=4a.$ Prove that $\Bigg(\dfrac{a}{p}\Bigg)=\Bigg(\dfrac{a}{q}\Bigg).$

Let $p,q$ be odd primes such that $p-q=4a.$ Prove that $\Bigg(\dfrac{a}{p}\Bigg)=\Bigg(\dfrac{a}{q}\Bigg).$ Could anyone advise on how to prove the equality? Hints will suffice, thank you.
0
votes
1answer
468 views

Evaluate the Legendre symbol $(\frac{14}{p})$ for $p > 2$.

Let $p > 2$. I try to compute the Legendre symbol $\left(\frac{14}{p}\right)$, but I have some difficulties. Here is my attempt so far: $$\left(\frac{14}{p}\right) = \left(\frac{2}{p}\right)\left(\...
1
vote
1answer
94 views

Showing that $\sum_{x \in \mathbb{F}_p} \left(\frac{x^2-1}{p}\right) = -1$, where $\left(\frac{x}{p}\right)$ is the Legendre symbol

The question is, Show that $$\sum_{x \in \mathbb{F}_p} \left(\frac{x^2-1}{p}\right) = -1$$ where the operation $\left(\frac{x}{p}\right) = \pm 1$ if $x$ is a quadratic residue/non-residue and $0$ ...
1
vote
0answers
25 views

How to guarantee non existence of order 4 elements in class group of a maximal order

If we know the prime factorisation of the fundamental negative discriminant $\Delta_K$, say $n$ prime factors, then we are guaranteed that $2^{n-1}\mid h_K$, the class number of $C(\mathcal{O}_K)$ ...
2
votes
2answers
72 views

$-3$ is a quadratic residue iff $p \equiv 1 \pmod 3$ [closed]

So this is the question: Let $p$ be an odd prime, prove that $-3$ is a quadratic residue modulo $p$ iff $p \equiv 1 \pmod 3$. My idea was: $$\left(\frac{-3}{p}\right) = \left(\frac{-1}{p}\right)\...
3
votes
2answers
419 views

How can $\left(\frac pq\right)\left(\frac qp\right)=(-1)^{\frac{p-1}{2}\frac{q-1}{2}}$

While looking through some of the formulae I came across this formula.$$\left(\dfrac pq\right)\left(\dfrac qp\right)=(-1)^{\frac{p-1}{2}\frac{q-1}{2}}$$ What I know is $\left( \dfrac pq\right)\left( ...
-2
votes
1answer
45 views

Quadratic Reciprocity problem.. help! [closed]

If $p$ is an odd prime, evaluate $\left(\frac{1\times2}{p}\right)+\left(\frac{2\times3}{p}\right)+\cdots+\left(\frac{(p-2)\times(p-1)}{p}\right)$ I don't know how I use properties of Legendre symbol. ...
1
vote
1answer
48 views

Determine $\left ( \frac{5}{p} \right )=1$ in a different way

Let $p$ prime with $p\equiv 1\pmod 5$. Let $c$ be an element of order $5$ in $(\mathbb{Z}/p\mathbb{Z})^\times$. I suppose this element exists, since the set $(\mathbb{Z}/p\mathbb{Z})^\times$ is cyclic....
4
votes
1answer
68 views

Every prime divisor ($p \neq 5$) of $n^2+n-1$ is of the form $10k+9$ [duplicate]

Now, what I have done so far is the following: Let $p$ be a prime such that $p | n^2+n-1$, then $n^2+n-1 \equiv 0 \pmod p$ This congruence has a solution if and only if $x^2 \equiv \Delta \pmod p$ ...
2
votes
1answer
51 views

$N$ square-free $\Rightarrow \exists a \in (\mathbb Z / N\mathbb Z)^{\times}, (\frac{a}{N}) = -1$

I want to show that if $N$ is a square free odd integer then there is some number coprime to $N$ such that the Jacobi Symbol $(\frac{a}{N}) = -1 $ Honestly I don't even know how to start showing this....
1
vote
2answers
76 views

Determine $p$ such that $x^2 \equiv a \pmod{p}$ using Legendre symbols(for specific values of $a$)

Determine $p$ such that $x^2 \equiv a \pmod{p}$ has a solution.(where $p$ is a prime) How would you approach this for "bigger" numbers, if you would want to solve this using Legendre symbols and ...
2
votes
2answers
230 views

Legendre symbol of $(-3/p)$.

Question. Show $$\Big(\frac{-3}{p}\Big)=\begin{cases}+1 & p\equiv 1\bmod 3,\\ -1 & p\equiv 2\bmod 3. \end{cases}$$ Attempt. So, using the established results of $$\Big(\frac{3}{p} \Big) = \...
2
votes
1answer
274 views

Legendre symbol of $(-2/p)$.

Question. Show $(-2/p)$ equals $1$ when $p\equiv 1,3\bmod 8$ and $-1$ when $p\equiv 5,7\bmod 8$. So using the multiplicativity of the symbol; we have $$\Big(\frac{-1}{p}\Big)\Big(\frac{2}{p}\Big),$$ ...
0
votes
1answer
49 views

Legendre symbol question without Euler's Criterion

I would like to solve the following Legendre symbol problem without the use of Euler's Criterion. We have the following: $$\left(\dfrac{10}{41}\right)$$ We can do it the long way and write out a ...
0
votes
1answer
41 views

Legendre symbol related-problem

Suppose that I am given an odd prime $p$. In addition, suppose that $$\left(\dfrac{75}{p}\right) = -1, \left(\dfrac{93639}{p}\right) = 1.$$ I am solving for $\left(\dfrac{4179}{p}\right).$ I have ...
3
votes
2answers
81 views

Suppose $p$ is $3\bmod 4$. Show $a$ and $-a$ cannot both be primitive roots $\bmod p$.

Suppose $p$ is $3\bmod 4$. Show $a$ and $-a$ cannot both be primitive roots $\bmod p$. I think the idea behind my proof is right but not sure it's written out that clearly, would appreciate another ...
1
vote
0answers
288 views

Let $p$ be an odd prime. Suppose $a$ and $b$ are both primitive roots mod $p$. Show that $ab$ is not a primitive root mod $p$

Let $p$ be an odd prime. Suppose $a$ and $b$ are both primitive roots mod $p$. Show that $ab$ is not a primitive root mod $p$. Would appreciate some proof-checking here. First, we show that a ...
0
votes
0answers
46 views

Dirichlet character associated to modular forms

Let $Q$ be a positive definite integral symmetric $2m \times 2m$ matrix with even diagonals (which determines a positive definite quadratic form). Assume that the level of $Q$ is strictly bigger than ...
0
votes
1answer
37 views

Elementary Number Theory: Legendre Symbol

Compute $(\frac{307}{379})$. So what I did is as follows: $(\frac{3}{379})= (-1)^{189\times153} (\frac{379}{307})= -1(\frac{72}{307})$. Since $72$ is composite I spilt the legendre symbol into it's ...
0
votes
1answer
40 views

Computing the Legendre Symbol

Compute $(\frac{3}{379})$. So what I did is as follows: $(\frac{3}{379})= (\frac{379}{3})=1$ because using Euler's Criterion $\displaystyle 1^\frac{3-1}{2}\equiv 1$. Hence $3$ is a quadratic ...
0
votes
1answer
88 views

How many solutions does a quadratic congruence have?

Given $x^2 \equiv 182\ mod\ 727$, how many solutions $mod\ 727$ does it have? Note $727$ is prime and $182 = 2\cdot7\cdot13$. So I know this is soluble computing $\left(\frac{182}{727}\right)$, but ...
1
vote
1answer
50 views

Calculating the Legendre symbol

Not sure what's going wrong with the calculation here, trying to calculate the Legendre Symbol $\left(\frac{138}{461}\right)$. My process follows as $\left(\frac{138}{461}\right) = \left(\frac{2}{...
4
votes
0answers
136 views

Analogue of Fermat’s Little Theorem

The question is “Establish an analogue of Fermat’s Little Theorem for the ring $\mathbb{Z} [\sqrt{-2}]$.” I know how to do this for the cases where $\mathbb{Z} [\sqrt{3}]$ and $\mathbb{Z} [\sqrt{5}]$...
1
vote
2answers
83 views

How to prove equality of sum of Legendre symbols

I have to prove that the next equality holds: $$\sum_{k=0}^{p-1} \left( \frac{k(k+a)}{p} \right)=\sum_{k=0}^{p-1} \left( \frac{k(k+1)}{p} \right)$$ with $a \in \mathbb{Z}$ and $a$ not divisible by $p$ ...
0
votes
1answer
74 views

Eisenstein's Lemma

Hi I've read the proof here. https://proofwiki.org/wiki/Eisenstein%27s_Lemma On the line about division it says $$k a = p \times \left \lfloor {\dfrac {k a} p} \right \rfloor + r$$ where $r\in S′$....
0
votes
0answers
34 views

Value of $L(1,\chi)$ when $\chi$ is defined via ramification of primes

Let we have $K= \mathbb{Q}(\sqrt d)$ . For a rational prime $p$, we have the following cases if we consider its ramification in $O_K$: $p$ is ramified if $p| \Delta$. $p$ splits if $(\cfrac{d}{p}) =...
-1
votes
2answers
50 views

Proof on Legendre symbol

Given Legendre symbol $(\frac {y}{p})$. Prove that $(\frac {y}{p})=(\frac{y^{-1}}{p})$ Help me prove this also. $\sum_{y=0}^{p-1} (\frac {y}{p}) = \sum_{y=0}^{p-1} (\frac {y+d}{p})$