Questions tagged [legendre-symbol]

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

30 questions
Filter by
Sorted by
Tagged with
892 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 ...
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 ...
2k views

210 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}$, ...
144 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 ...
382 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 ...
671 views

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} \... 3answers 197 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 ... 1answer 438 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'... 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 ... 2answers 150 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}\... 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 ... 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}... 1answer 956 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 ... 0answers 117 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}{... 1answer 79 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 -... 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 \... 2answers 41 views Modular arithmetic with Legendre symbol Let$n\in\mathbb{Z}_{>0}$and let$p\neq3$be a prime divisor of$n^2+n+1$. Show that$p\equiv1\mod3$. I thought of trying to prove that$\left(\frac{p}{3}\right)=1$, since 1 is the only element ... 1answer 468 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),$$ ... 1answer 100 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$$ 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)$... 2answers 347 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} ...
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 ...