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

How does Legendre symbol formula $(-1)^{{p-1\over 2}{q-1\over 2}}$, actually show the correct value?

I've read about this formula on wikipedia, but attempting to use it just gets me: $$q\equiv 3 \bmod 4\implies p\equiv 1 mod 4 $$ and,$$q\equiv 1 \bmod 4\implies p\equiv 1,3 mod 4$$ However, $$1,4,9,...
-1
votes
1answer
32 views

Algebra of the law of quadratic reciprocity [on hold]

I have seen some examples that use the law of quadratic reciprocity in the form $$\left(\frac{p}{q}\right)=(-1)^{\left(\frac{p-1}{2}\right)\left(\frac{q-1}{2}\right)}\left(\frac{q}{p}\right)$$ I ...
0
votes
1answer
44 views

A contradiction in calculating the legendre symbol

I got a contradiction when I calculated the legendre symbol. I felt like there must be something wrong in my calculation but I can't find them. The following is my calculation steps. Note that $13=4\...
2
votes
1answer
25 views

Prove a property of Legendre symbol

In case someone does not know the definition, I first write down the definition. Def Let $a$ be s.t. $(a,m)=1$. Then we say $a$ is a quadratic residue modulo m if the congruence $x^2\equiv a$ (mod $m$...
0
votes
0answers
20 views

Legendre Transforms

I want to show that the Legendre Transform of a function $g(x) = kf(x-x_0) + m$ for $m$, $k$ constants is equal to $g^*(p) = kf\left(\frac{p}{k}\right)+p \cdot x_0+m$ where $f^*$ is the Legendre ...
1
vote
1answer
39 views

Polynomial evaluates to quadratic residue in $p$ cases

This exercise popped up in a chapter on Legendre symbols. Let $p$ be a prime $3$ $(\textrm{mod } 4)$, and $f(x) \in \mathbb{F}_p[x]$ a polynomial of odd degree. Show that the number of solutions $(...
0
votes
0answers
20 views

Which of these congruences have solutions? [duplicate]

$$x^2 \equiv 134 \text{ mod } 197$$ $$x^2 \equiv 134 \text{ mod } 197^2\times 67$$ $$x^2 \equiv 134 \text{ mod } 197^{30}\times2^{10}$$ $$x^2 \equiv 134 \text{ mod } 197\times 23^2$$ The ...
1
vote
1answer
46 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
31 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
56 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
29 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
27 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.
1
vote
2answers
48 views

Solution to a system of quadratic congruences.

The following is a system of quadratic congruences: $$\left\{\begin{array}{cl}x^{2}\equiv a&\pmod{3}\\x^{2}\equiv b&\pmod{7}\end{array}\right.$$ If $\left(\frac{a}{3}\right)=1=\left(\frac{b}{7}...
0
votes
1answer
71 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
80 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
76 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
39 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
169 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
60 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
335 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
61 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
328 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
91 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
90 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
41 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
53 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
39 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
0answers
33 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
57 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
92 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
599 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
97 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
26 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
115 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
484 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
56 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
69 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
59 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
309 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
383 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
54 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
42 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
87 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
329 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
1answer
38 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
51 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 ...