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
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 ...
7
votes
2answers
94 views

If $p=a^2+4b^2$ for some $a,b \in \mathbb{Z}$, then $a$ is quadratic residu modulo $p$?

If $p=a^2+4b^2$ for some $a,b \in \mathbb{Z}$ and $p$ prime, then $a$ is quadratic residu modulo $p$? Approach: I thought it was true. (I could't find a counterexample). So I tried to prove it. I ...
7
votes
1answer
508 views

Does the Legendre Symbol/quadratic reciprocity generalize to higher degrees?

The Legendre symbol is a tool for measuring whether or not $$ x^2 \equiv a \text{ } (p) $$ has a solution in $\mathbb{F}_p$ for some fixed integer $a$. Does the Legendre symbol generalize to higher ...
7
votes
0answers
125 views

Connection between sgn character and the Legendre symbol

Today, while I was lecturing on the Legendre symbol, I realized that the phenomenon: "the product of two non-squares is a square" isn't so foreign. For example, for $\mathbb R^\times$, the squares are ...
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 ...
6
votes
2answers
311 views

How to prove this sum related to Legendre symbol

I can see why it is true by writing out some examples, but I'm not sure how one could prove that, with $\left({\cdot\over p}\right)$ as the mod $p$ Legendre symbol $$\sum_{x=1}^{p-1} \left(\frac{x(x-...
6
votes
1answer
331 views

Non-positivity of partial sums of certain Legendre symbols

Let $T(c, k, p) := \sum_{i = 0}^{k} \left( \frac{i^2 + c}{p} \right) $, where $p$ is a prime number. It is known, that $T(c, p - 1, p) = -1$ for $p \nmid c$. Now, I would like the sequence $T(c, 0, p),...
6
votes
1answer
105 views

$\tau( n!(n+1) ) = 2\times\tau(n!)$. Then what is $n!\;\text{mod} \; (n+1)?$

If the number of factor of $(n+1)!$ is double than the number of factor of $n!$, then find the reminder if $n!$ is divided by $(n+1)$? I'm not sure if the question mean factor = divisor. However in ...
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 ...
6
votes
0answers
496 views

Application of Legendre, Jacobi and Kronecker Symbols

Legendre, Jacobi and Kronecker Symbols are powerful multiplicative functions in ...
5
votes
3answers
190 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 ...
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)}$$
5
votes
1answer
72 views

Showing Legendre's Properties

I've solved parts (a) and (b), but i don't know how to use this to solve (c) (a) let $\ell>1$ an odd integer. Show $\displaystyle (\ell-1)!=2^{\frac{\ell-1}{2}}\left(\frac{\ell-1}{2}\right)!\left(...
5
votes
3answers
123 views

Number Theory: Find $m\equiv 1\pmod4$ so that $x^2\equiv -1\pmod{m}$ has no solution.

I have this problem that I'm a bit stuck on: Find $m\equiv 1\pmod4$ so that $x^2\equiv -1\pmod{m}$ has no solution in $\mathbb{Z}$. So far, I know that $m$ can't be prime because $(\frac{-1}{p})=1$, ...
5
votes
1answer
92 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 ...
5
votes
1answer
119 views

Jacobi symbol properties

I know that $p_i$ is an odd prime, $(\frac{a}{p_i}\equiv a^{\frac{p_i-1}{2}} \pmod p$). But I don't know how to solve this problem...
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'...
4
votes
1answer
248 views

How to prove this formula for the Legendre symbol for a finite field

Let $\mathbb{F}_q$ be a finite field with $q$ odd, let $x\in\mathbb{F}_q$ and define the Legendre symbol for $\mathbb{F}_q$ as \begin{equation} \left(\frac{x}{\mathbb{F}_q} \right) = \begin{cases} \...
4
votes
1answer
96 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.
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 ...
4
votes
1answer
888 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 ...
4
votes
1answer
176 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$...
4
votes
1answer
188 views

Prove that if p is an odd prime, the number of residues x modulo p for which both x and x+1 are quadratic residucs

Prove that if p is an odd prime, then the number of residues x modulo p for which both x and x+1 are quadratic residucs is $\frac{p-(-1)^\frac{p-1}{2}}{4}-1$ I know that 0 is neither a quadratic ...
4
votes
1answer
333 views

Jacobi's Symbol

I read online that even when Jacobi's Symbol is 1, it doesn't necessary means that it's legendre Symbol is 1: $$\left(\frac 2 {15}\right) = \left(\frac 2 3\right)\left(\frac 2 5\right) =-1*-1 = 1$$ ...
4
votes
1answer
116 views

For which primes is $-2$ a quadratic residue?

For which primes is $-2$ a quadratic residue? We are trying to find primes that have solution for $x^2 \equiv -2 \mod p.$ Using the Lagrange symbol I know that $2$ is a quadratic residue when $p \...
4
votes
1answer
212 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 ...
4
votes
2answers
695 views

Proving summations involving the Legendre symbol

In the following, let $(\frac{a}{p})$ denote the Legendre symbol. Then Show that $$\sum _{a=1}^{p-2} \left(\frac{a(a+1)}{p}\right)=-1$$ for an odd prime $p$. I was thinking of factoring out $a^2$, ...
4
votes
0answers
66 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
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$ ...
4
votes
0answers
175 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}]$...
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 = \...
3
votes
2answers
517 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( ...
3
votes
2answers
40 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 ...
3
votes
2answers
79 views

establish that every prime number p of the form $ 8k + 1$ or $8k +3$ can be written as $ p = a^2 + 2b^2$ for some choice of integers a and b.

The question is: Establish that every prime number p of the form $ 8k + 1$ or $8k +3$ can be written as $ p = a^2 + 2b^2$ for some choice of integers a and b. And the Hint says: Mimic the proof 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
437 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
2answers
866 views

Prove that Legendre Symbol $\left(\frac{(p-1)!}p\right) \equiv p\pmod4$

Let $p$ be an odd prime. Prove that Legendre Symbol $\left(\frac{(p-1)!}p\right)=1$ if $p\equiv1\pmod4$, $-1$ if $p\equiv3\pmod4$. Not sure where to begin but here are my initial thoughts. Clearly, ...
3
votes
3answers
633 views

Describing the primes $p$ for which the Legendre symbol $(\frac{-6}{p})=1$

I would love your help with describing the primes $p$ for which the Legendre symbol $(\frac{-6}{p})=1$. From the properties of the Legendre symbol I know that $(\frac{-6}{p})=(\frac{-1}{p})(\frac{2}{...
3
votes
2answers
101 views

To show that $\sum_{a=1}^{p-2}(a(a+1)/p)=-1$

Let $p$ be an odd prime and for any integer $a$ , relatively prime to $p$ , let $(a/p)$ denote the Legendre symbol . Then how to show that $\sum_{a=1}^{p-2}(a(a+1)/p)=-1$ ? I know that $\sum_{a=1}^{...
3
votes
2answers
306 views

How to prove this summation involving Legendre symbol: $\sum\limits_{k=1}^{p-1}k\left(\frac{k}{p}\right)=0 $

If $p\equiv 1 \pmod{4}$ is a prime number, prove that $$\sum_{k=1}^{p-1}k\biggl(\dfrac{k}{p}\biggr)=0 $$ Any suggestion how to prove it I will appreciate.
3
votes
1answer
56 views

Trying to prove $p \equiv 3 \pmod 4 \iff \sum\limits_{x\in\mathbb{F}_p} \left(\frac{x^3-x}{p} \right)=0$

Let $p>2$ be a prime number. I would like to show that $$p \equiv 3 \pmod 4 \iff \sum_{x\in\mathbb{F}_p} \left(\dfrac{x^3-x}{p} \right)=0$$ where $\left(\dfrac{\cdot}{p} \right)$ denotes the ...
3
votes
2answers
238 views

Fibonacci Numbers and Legendre symbol

How to prove congruence below ? $$F_{p-\left( \frac{5}{p}\right)} \equiv 0 \pmod p$$ Where $\displaystyle \left( \frac{}{}\right)$ is legendre symbol, and $\displaystyle p$ is a prime number.
3
votes
3answers
104 views

When $p=3 \pmod 4$, show that $a^{(p+1)/4} \pmod p$ is a square root of $a$

Let $a$ and $p$ be integers such that $p$ is prime, and $a$ is a square modulo $p$. When $p\equiv3\pmod4$, show that $a^{(p+1)/4}\pmod p$ is a square root of $a$. Why does this technique not work when ...
3
votes
1answer
362 views

Legendre symbol $(-11/p)$

When $p$ is not $11$ and $p$ is an odd prime, compute the Legendre symbol $\left(\dfrac{-11}{p}\right)$. What I have done is that $\left(\dfrac{-11}{p}\right) = \left(\dfrac{-1}{p}\right)\left(\dfrac{...
3
votes
1answer
89 views

Prove that $\left(\frac{-1}{p}\right)\left(\frac{3}{p}\right)=\left(\frac{p}{3}\right)$

Why does $\left(\frac{-1}{p}\right)\left(\frac{3}{p}\right)$ equal $\left(\frac{p}{3}\right)$?
3
votes
1answer
81 views

Infinite graph with Legendre symbol .

Consider a (kind of) infinite oriented graph as follows : 1.The vertexes represent the prime numbers $p>2$ . 2.We draw an oriented edge from $p$ to $q$ if $\left(\frac{p}{q} \right )=1$ (this is ...
3
votes
2answers
1k 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(\...
3
votes
1answer
954 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 ...
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 ...
3
votes
1answer
97 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)$ ...