Questions tagged [legendre-symbol]

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

Filter by
Sorted by
Tagged with
4
votes
1answer
889 views

Legendre symbol: Showing that $\sum_{m=0}^{p-1} \left(\frac{am+b}{p}\right)=0$

I have a question about Legendre symbol. Let $a$, $b$ be integers. Let $p$ be a prime not dividing $a$. Show that the Legendre symbol verifies: $$\sum_{m=0}^{p-1} \left(\frac{am+b}{p}\right)=0.$$ I ...
10
votes
2answers
3k views

Legendre symbol, second supplementary law

$$\left(\frac{2}{p}\right) = (-1)^{(p^2-1)/8}$$ how did they get the exponent. May be from Gauss lemma, but how. Suppose we have a = 2 and p = 11. Then n = 3 (6,8,10), but not $$15 = (11^2-1)/8$$ n ...
3
votes
1answer
2k views

sum of the product of consecutive legendre symbols is -1

How do I prove the formula $\newcommand{\jaco}[2]{\left(\frac{#1}{#2}\right)}\sum\limits_{a=1}^{p-2} \jaco{a(a+1)}p = -1$ where a varies from 1 to p-2 and p is a prime I got as far as $\jaco{p-a}p = \...
2
votes
1answer
178 views

Prove that $\sum_{X=0}^{p-1} \left(\frac{X^{2}+A}{p}\right)=-1$

Let $\left(\frac{a}{p}\right)$ denote the Legendre symbol and $p \geq 5$ a prime number and $a,b,c$ integers. Prove that $$\sum_{X=0}^{p-1} \left(\dfrac{X^{2}+A}{p}\right)=-1$$ where $p\nmid A=4ac-b^...
5
votes
2answers
1k views

How can I prove these summations for the legendre symbol

How can I prove for the Legendre symbol that: $$\sum_{a=1}^{p-1}{\left(\frac{a(a+1)}{p}\right)}= -1 = \sum_{b=1}^{p-1}{\left(\frac{(1+b)}{p}\right)}$$
3
votes
1answer
302 views

A problem with the Legendre/Jacobi symbols: $\sum_{n=1}^{p}\left(\frac{an+b}{p}\right)=0$ [duplicate]

This problem is taken from Niven's textbook, 3.6.16. Prove that if $(a,p)=1$ and $p$ is an odd prime, then $\sum_{n=1}^{p}\left(\frac{an+b}{p}\right)=0$, where $\left(\frac{x}{y}\right)$ is the ...
1
vote
1answer
102 views

$r! \equiv (−1)^k \pmod p$

Suppose that p ≡ 3 (mod 4) and $r = \frac {p-1}2$ Show that $r! \equiv (−1)^k \pmod p$ where k is the number of non-quadratic residues modulo p which are smaller than $\frac p2$ I know from ...
4
votes
1answer
1k views

Computing the Legendre symbol $\bigl(\frac{3}{p}\bigr)$ using Gauss' Lemma

I would like to compute the Legendre symbol $\bigl(\frac{3}{p}\bigr)$, where $p > 3$ is a prime using Gauss' Lemma. What I got so far is that $p$ can belong the following residue classes $\mod ...
2
votes
1answer
209 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}$, ...
6
votes
2answers
139 views

Find the primes $p$ such that the equation: $x^{2} + 6x + 15 = 0$ has a solution modulo $p$

I need to solve this question: Find the primes $p$ such that the equation: $x^{2} + 6x + 15 = 0 $ has a solution modulo $ p $. My approach was: I checked for $p = 2$ and there is no solution. Now ...
2
votes
1answer
671 views

Sum of Legendre symbols: $\sum _{n=1}^p \left(\frac{an+b}{p}\right)=0$ [duplicate]

If $(a,p)=1$ and $p$ is an odd prime, prove the Legendre symbol sum $$\sum _{n=1}^ p \left(\frac{an+b}{p}\right)=0.$$ Where $b$ is any integer. I know the fact that $\sum_{a=1}^p \left( \frac{a}{p} \...
5
votes
3answers
191 views

Prove the congruence $ \sum_{r=1}^{p-1}{(r|p) * r } \equiv 0 \pmod p.$

Prove that if $p$ is prime and $p\equiv 1 \pmod4$, then $$ \sum_{r=1}^{p-1}{(r|p) * r } \equiv 0 \pmod p.$$ ( $(r|p)$ is a Legendre Symbol ) I know that $\sum_{1 \le r \le p}{(\frac{r}{p})} = 0$, but ...
4
votes
1answer
435 views

How to solve $1+\frac12-\frac13+\frac14-\frac15-\frac16+\frac18+\ldots+\left(\frac n7\right)\frac1n+\ldots$?

$$1+\frac12-\frac13+\frac14-\frac15-\frac16+\frac18+\ldots+\left(\frac n7\right)\frac1n+\ldots$$ where $\left(\frac n7\right)$ is Legendre symbol. I think its about algebraic number theory, but I can'...
3
votes
1answer
127 views

A generalization of a divisibility relation for Fibonacci numbers

Given $a,b\in\mathbb Z^+$, and let $F_{a,b}:\mathbb N\to\mathbb N$ be a function such that $F_{a,b}(0)=0$, $F_{a,b}(1)=1$ and $F_{a,b}(n+1)=a\cdot F_{a,b}(n)+b\cdot F_{a,b}(n-1)$. $F_{1,1}$ correspond ...
1
vote
2answers
148 views

Legendre symbol $(-21/p)$

I am a bit confused with the question: For what prime $p$, $\left(\frac{-21}{p}\right) = 1$? I did something like that: $$\left(\frac{-21}{p}\right) = \left(\frac{-1}{p}\right)\left(\frac{3}{p}\...
1
vote
1answer
1k views

Legendre symbol $(-3/p)$ where $p = 1 \mod 3$

Suppose $p = 1 \bmod 3$, prove the following statements: prove that $x^2 + x + 1 = 0 \mod p$ has a solution Prove that $\left(\frac{-3}{p}\right) = 1$ if $p = 1\mod 3$ Determine the discriminant of $...
3
votes
2answers
300 views

A combinatorial proof of Euler's Criterion? $(\tfrac{a}{p})\equiv a^{\frac{p-1}{2}} \text{ mod p}$

Euler's criterion states that $ (\tfrac{a}{p}) \equiv a^{\frac{p-1}{2}} (\text{ mod }p \,) $, where $(\tfrac{a}{p})$ is the Legendre symbol. Here is one algebraic proof, since $\mathbb{Z}/p\mathbb{Z}...
3
votes
1answer
955 views

Proof involving Legendre Symbol: $\left(\frac{3}{p}\right) = 1$ iff $p \equiv \pm 1 \pmod{12}$

I’m having a really difficult time with the following proof involving the Legendre symbol: Show that $\left(\dfrac{3}{p}\right) = 1$ iff $p \equiv \pm 1 \pmod{12}$ The normal tricks don’t seem to ...
1
vote
1answer
75 views

Divisor sum or möbius inversion of the Jacobi Symbol?

We're doing number theory and we've separately covered the topics of Quadratic Reciprocity and Multiplicative Functions. I just noticed that if one of the parameters in the Jacobi symbol is constant -...
1
vote
0answers
116 views

Discrete logarithm problem, existence and parity

Let $p>2$ be a prime number such that $p-1=2^st, s>0,t$ odd. Let $a,d\in \mathbb … {Z}^* /p \mathbb{Z}$ with $\left(\frac{a}{p}\right)=1$ and $\left(\frac{d}{p}\right)=-1$, where $\left(\frac{a}{...
6
votes
2answers
377 views

Prove that $-3$ is a quadratic residue mod an odd prime $>3$ if and only if $p$ is of the form of $6n+1$

How would I prove that $-3$ is a quadratic residue mod an odd prime larger than $3$ if and only if $p$ is of the form of $6n+1$? The last thing we covered in class last night was Euler criterion ...
3
votes
1answer
443 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),$$ ...
3
votes
0answers
149 views

Proof Involving Legendre Symbol and Quadratic Residue Multiplication

I am struggling with this proof. I really cannot think of where to start: Let $p$ be an odd prime, prove that: $$\left(\frac{1 \cdot 2}{p}\right) + \left(\frac{2 \cdot 3}{p}\right) + \left(\frac{3 \...
2
votes
1answer
99 views

Legendre symbol, what is it?

I am reading wiki article about Legendre symbol and I don't understand the power meaning. Can you please explain the next expression. $$\left(\frac ap\right)\equiv a^{\frac{p-1}{2}}\pmod p$$
1
vote
0answers
27 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)$ ...
1
vote
2answers
346 views

Legendre Symbol $\left ( \frac{7}{p} \right ) = \left ( \frac{7}{q} \right )$

I am asked to prove, that if $p\equiv q\mod 28$ then Legendre Symbol $\left ( \frac{7}{p} \right ) = \left ( \frac{7}{q} \right )$ So far I have this $7\equiv -1\mod 4$ thus $\left ( \frac{7}{p} ...
0
votes
2answers
3k views

Fast legendre symbol calculation

Let's say that I would like to calculate all legendre symbols from $1$ to $p-1$ $\pmod{p}$, is there a way to calculate them in an incremental way?. For example, an incremental table of legendre ...
0
votes
1answer
39 views

Congruences and Legendre

I am trying to solve a Legendre symbol problem and have got it down to the following: When $p \equiv 1\mod4$ and a prime such that $p \neq 2,7$, $\left(\frac{7}{p}\right) = \left(\frac{p}{7}\right) ...
0
votes
1answer
654 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(\...