Stack Exchange Network

Stack Exchange network consists of 174 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$.

2
votes
2answers
66 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
68 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
35 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
112 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
50 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
134 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
48 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 ...
3
votes
0answers
241 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
74 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
53 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
36 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
32 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
35 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
19 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
47 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
82 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
271 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
88 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
67 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
306 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
38 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
47 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
63 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
47 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
74 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
181 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
164 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
45 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
79 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
257 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
38 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
33 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
33 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
72 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
43 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
126 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
79 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
69 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
49 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})$
1
vote
1answer
23 views

Legendre calculation passing through Jaccobi

We know that Jacobi's symbol does not guaranty that if $(\frac{a}{b}) = 1$ then $a$ is a quadric remander mod $b$. We also know that when calculating Legendre symbol you can use quadratic reciprocity ...
0
votes
0answers
15 views

Modular Reduction in Abstract Polytopes

Anyone of you here who have read the paper of B. Monson and E. Schulte on Modular Reduction in Abstract polytopes? In Proposition 5.1 of the paper, I am confused of the idea of using the Legendre ...
0
votes
1answer
49 views

Sum of Legendre symbol

$$\sum_{y=0}^{p-1} \left(\frac {y^2 + d}{p}\right) = \sum_{y=0}^{p-1} \left(1+\left( \frac {y}{p}\right)\right)\left(\frac {y+d}{p}\right)$$ What is the reason behind this?
-1
votes
1answer
69 views

$\sum_{y=0}^{p-1 } (\frac{y^2 - b^{-1}}{p}) =-1$

Given Legendre symbol: $(\frac{y^2 - b^{-1}}{p})$. Please show a detailed proof of $\sum_{y=0}^{p-1 } (\frac{y^2 - b^{-1}}{p}) =-1$
1
vote
0answers
38 views

Deduce that $\left(\frac{2}{p}\right)=(-1)^{\frac{1}{2}(p-1)-k}$

Let $p$ be an odd prime. Consider the numbers $$2 \cdot 1,2 \cdot 2,\dots,2\cdot \frac{1}{2}(p-1) $$ and let $k$ be the largest integer that satsifies $$2k \le \frac{1}{2}(p-1)$$ Prove that if $l \...
3
votes
2answers
57 views

Number of solution is twice $(x,y)$

Problem: Count the number of $2 \times 2$ matrices $A$ with $A^TA=-I$ in $Z_p$ for $p>2$. Answer: if $p$ is an odd prime, the number of such matrices $A$ is twice the number of solutions $(x,y)$ ...
0
votes
0answers
64 views

Number theory in the quadratic field with golden section unit

I would like to ask a favor. Does anyone of you here have an access to the book 'Number theory in the quadratic field with golden section unit' by Fred Wayne Dodd? I just need to see Theorem 8.5 of ...
1
vote
1answer
51 views

Jacobi Sums and Legendre Sums

I have a question on Jacobi symbols, and the problem goes: Show that is $(a,p)=1$, and $p$ is an odd prime, then prove that: $$\sum_{n=1}^p \left(\frac{n^2+a}{p}\right)= -1$$ I think I have some ...