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
0
votes
1answer
37 views

Why is $\left( \frac {a}{p} \right)= 1$ equivalent to $p$ satisfying some condition mod $4a$, for odd prime $p$?

Basically title: Why is $\left( \frac {a}{p}\right)$ (the Legendre symbol) $= 1$ equivalent to $p$ satisfying some condition mod $4a$, for odd prime $p$? (For example, $\left( \frac {3}{p}\right)=1 \...
0
votes
2answers
63 views

Show that $p\equiv 3\pmod 4$ being prime implies $x^2+y^2\equiv n\pmod p$ has $p+1$ solutions [closed]

Let $p$ be an odd prime with $p\equiv 3\pmod 4$. Show that for $n\ne 0$, $x^2+y^2\equiv n\pmod p$ has $p+1$ solutions. I tried using some laws of quadratic reciprocity but got absolutely nowhere:(
3
votes
4answers
273 views

Prove that there are quadratic residues that differ by 6

Let $p \geq 19$ be a prime number. Prove that in the set $\{1,..., p-1\}$ there exist two quadratic residues (QR) that differ by 6. My attempt: If 2 is a QR, then (2,8) is solution. If 3 is QR, then (...
0
votes
0answers
22 views

There exists an integer $x$ s.t $x^2\equiv -3 \,\text{mod}\, p$ iff $p=3k+1$, $k\in\mathbb{Z}$ [duplicate]

I need to prove the theorem above and I'm stuck. What I tried: Assume $p=3k+1$ with integer $k$ This means $p \equiv 1 \,\text{mod}\, \Rightarrow \left(\frac{1}{3} \right) = \left(\frac{p}{3} \right)$ ...
0
votes
0answers
42 views

Legendre symbol in the Fibonacci primality test

The Legendre symbol $\left(\dfrac{5}{p}\right)$ is used in the Fibonacci primality test. I understand its significance, but why did 5 show up and not some other prime? Is it because $p$ is written in ...
3
votes
0answers
68 views

definite integral solution for $\int^{\pi}_{\alpha} P_{n}(\cos\theta)\:P_{m}(\cos\theta)\sin\theta\:d\theta$

I'm trying to verify the result of $\int^{\pi}_{\alpha} P_{n}(\cos\theta) P_{m}(\cos\theta)\sin\theta\:d\theta$ in a publication which gives: $$\tfrac{\sin \alpha}{m(m+1) - n(n+1)}\biggl( P_{m}(\cos\...
0
votes
1answer
70 views

$p \geq$ 7 show $\Big( \frac{n}{p} \Big)=\Big( \frac{n+1}{p} \Big) =1$ for atleast one n in the set $\{ 1,2,\ldots,,9 \}$

Suppose that p is prime $\geq$ 7.Show that $\Big( \frac{n}{p} \Big)=\Big( \frac{n+1}{p} \Big) =1$ for atleast one n in the set $\{ 1,2,3,\ldots,9 \}$. I have read this understood For any prime p>5 ...
1
vote
1answer
63 views

For a fixed $a$, can we say $\left[\frac{a}{p}\right]_q=-1$ for infinitely many $p$?

Here $\left[\frac{a}{p}\right]_q$ refers to the $q$-th power rational reciprocity symbol, with $q,p$ prime. That is $\left[\frac{a}{p}\right]_q=1$ if $q\nmid p-1$ or $a^{\frac{p-1}{q}}=1\bmod p$ $\...
0
votes
0answers
46 views

Jacobi Symbol walk through questions

I am reading the book Introduction to Modern Cryptography second edition by Katz et al. The Jacobi Symbol is defined on page 536 and I have included a picture below. I was able to understand most of ...
0
votes
1answer
40 views

Show that $2a \equiv -(-1)^m {2m \choose m} \pmod{p}$ where $m={p-1 \over 4}$

This is Problem $26$ from chapter $8$ of "A Classical Introduction to Modern Number Theory" by Ireland-Rosen : Let $p$ be a prime, $p \equiv 1 \pmod{4}$, $\chi$ a multiplicative character ...
0
votes
0answers
20 views

Class number of positive definite binary quadratic forms formula

I've been doing some computational research into the class number $h(d)$ which for my purposes is defined as the number of positive definite binary quadratic forms $(a,b,c)$ which are reduced, ...
1
vote
1answer
24 views

Jacobisymbols modulo $pq$, both prime

I am trying to find the number of $a$'s for which $$\left( \frac{a}{pq} \right) = 1$$ with $p$ and $q$ both prime, but I am not sure how to approach this problem. I was using the identity with the ...
-1
votes
1answer
35 views

Why does $p \nmid m$ imply $\left(\frac{-4m^2} p\right) = \left(\frac{-1 } p\right)$?

$\newcommand{\Leg}[2]{\left(\frac{#1}{#2}\right)} $ Note: In this question $ a \mid b $ denotes a divides b and $\Leg a b$ denotes Legendre's symbol. Theorem 9.12 in Introduction to Analytic Number ...
1
vote
0answers
27 views

If the congruence $ x^2 \equiv n \bmod{P} $ has a solution then $(n \mid p_i) = 1 $ for each prime $ p_i $ that divides $ P $

From section 9.7 "The Jacobi symbol" of Introduction to Analytic Number Theory by Tom M. Apostol Definition If $P$ is a positive odd integer with prime factorization $$ P = \prod_{i=1}^r ...
3
votes
1answer
43 views

Sums of divisors of a Jacobi symbol

$$f(n)= \genfrac(){}{0}{-15}{n}$$ if $n \neq 1$ is odd. What is $\sum_{d \mid n}f(d)$ ? Here is what I tried : Let $n=p_1^{a_1} \cdot \cdot \cdot p_r^{a_r}$, for $p_1,...,p_r$ odd primes. If $p_1,...,...
0
votes
1answer
38 views

Why does $a^n \mod p$ always result in a number with Legendre symbol as 1?

I noticed that the following expression $a^n\mod p$ where p is a prime and $n >=1$ and $n <= p$ always results in a number with Legendre Symbol (with p as the prime) as 1. I tested it out with a ...
1
vote
1answer
46 views

Sum of Legendre Symbols for evey number less than $p$

If $p$ is an odd prime, show that $\sum_{j=1}^{p-1}({\frac{j}{p}})=0$ with $(\frac{j}{p})$ the Legendre Symbol. I'm not sure if it's enough to say that, because of the Euler's Criteria, there are ...
1
vote
1answer
41 views

Squares in a finite field $\mathbb{F}_p$

I need to find all prime $p$ s.t $n+3$ is the inverse of $n-3$ in $\mathbb{F}_p$. So obviously this means $(n+3)(n-3)=1\mod p$, meaning $n^2=10\mod p$. So the question is - for which $p$ does the ...
2
votes
1answer
52 views

Question about the Legendre's symbol: $\left(\frac{p-1}{5}\right) \overset?= \left(\frac{5}{p}\right)$

I was reading about Legendres symbol (number theory) and encountered the following equality: I don't understand how they got $$\left(\frac 3p \right) = (-1)^{\frac{p-1}{2}\frac{3-1}{2}}\left(\frac{p-...
0
votes
0answers
42 views

Bounded sum of Legendre Symbol

I learned about Paley graphs and got stuck with the following problem. (Seemingly not directly related to it) For a odd prime $p$ and $A, B \subseteq \mathbb{Z}/p\mathbb{Z}$, prove that $$ \left| \...
1
vote
1answer
45 views

Proof of $n$ being quadratic residue for primes of the form $4n+1$

I'm trying to prove the following statement: If $4n+1$ is a prime $p$, then $n$ is a quadratic residue $\bmod p$. For this, I thought I could evoke the quadratic reciprocity law and deduce: $$\...
0
votes
1answer
34 views

Relationship between Dirichlet character and Legrendre symbol [closed]

I'm wondering whether you always can express a non trivial Dirichlet character by a Legendre symbol. And in case so, how would one explicitly do that? Or how does one connect the two things?
1
vote
1answer
53 views

Sum of Legendre symbols for divisors of a quadratic non-residue modulo an odd prime.

Let $\big(\frac{n}{p}\big)=-1$ (Legendre's symbol) for an odd prime p. Then show that $$\sum_{d,\ \ d\mid n}\Big(\frac{d}{p}\Big)=0.$$ I know that if $d$ is a divisor of $n$, then $-d$ is also its ...
1
vote
1answer
63 views

Find all the prime numbers $p$ which have a solution to $x^2\equiv14\bmod p$.

Find all the prime numbers $p$ which have a solution to $x^2\equiv14\bmod p$. I found that for $p=2,5,7$ there is a solution and for $p=3$ there's no solution. I tried using Legendre symbol because ...
0
votes
1answer
72 views

Proving first supplement of the quadratic reciprocity law [duplicate]

I'm trying to prove the first supplement of the quadratic reciprocity law in its particular form: $$-\bar{1} \text{is a square in} \mathbb{Z}/p\mathbb{Z} \iff p \equiv 1 \pmod 4$$ For the forward part,...
3
votes
1answer
68 views

Square in a finite field [duplicate]

I need to prove: $a$ is a square in $\mathbb{Z}$ iff $a\mod p$ is a square in $\mathbb{F_p}$ for every $p$ prime. First side ($\rightarrow$) is trivial and is derived directly from multiplicativity of ...
0
votes
0answers
48 views

$\Big [ \frac{p-1}{p}\Big ]_n$

this is equivalent to solving $x^n\equiv-1\pmod p$ where $p$ is a prime number. if $n=2$, the solution is iff $p\equiv 3 \pmod 4$.(if $p=2$ then all numbers are residues.) I'm unsure about the rest of ...
2
votes
1answer
63 views

Legendre symbols

So for odd prime $p$, I have Legendre symbol $(\frac{-1}{p}) = (-1)^{(p-1)/2}$, and let $n\geq 3$ be an odd positive integer. I have to show that for odd positive integers $n_1$ and $n_2$, we have $\...
1
vote
0answers
53 views

A sum of some Legendre symbols is $\equiv 0 \mod p$

Let $p \gt 5$ be a prime number. Then $$ \sum_{a = 1}^{\frac{p - 1}{2}} \left( \frac{a}{p} \right) a ^2 \equiv 0 \mod p ?$$ (Where $\left( \frac{a}{p} \right)$ is the Legendre symbol mod. p.) I could ...
1
vote
0answers
38 views

Product of Jacobi Symbols over Reduced Residue System

Problem For any odd composite number $m$ with at least $2$ distinct prime factors, prove that $\displaystyle \prod_{\substack{1\leq i\leq m \\ \text{gcd}(i,m)=1}}\left(\frac{i}{m}\right) = 1$, where $\...
1
vote
1answer
40 views

For odd prime $p$, show there exist nonzero residues $x$ and $y$ mod $p$ s.t. $ax^2+by^2 \equiv 0$ mod $p$ iff $(\frac{-ab}{p}) = 1$

The question is exactly what I put in the title. But I will restate it below anyway: For odd prime $p$, show there exist nonzero residues $x$ and $y$ mod $p$ such that $ax^2+by^2 \equiv 0$ mod $p$ iff ...
1
vote
0answers
44 views

Show that the following function is a homomorphism.

This is part (2) of the question that I asked here. Inspired by the answer in this question, I want to see if I am on the right track with this question. I was given this exercise, based on a theorem ...
0
votes
0answers
90 views

Legendre symbol for (2/p)

I'm reading a proof that $$ (2/p) = (-1)^{\frac{p^2 -1}8} $$ for odd primes $p$. I follow the proof upto and including this line: Which follows from the fact $$p \equiv \pm 1 \pmod 8 \implies \frac{p^...
2
votes
1answer
66 views

Show for any odd prime $p\geq 5,$ $(-3/p)=1$ or $ -1$ [duplicate]

Show for any odd prime $$p\geq 5,$$ $$\left ( \frac{-3}{p} \right ) =\begin{cases} 1 & \text{ if } p\equiv 1,-5\pmod{12} \\ -1& \text{ if } p\equiv -1,5\pmod{12} \end{cases}$$ So far I have ...
2
votes
0answers
75 views

For any odd prime $p≥5$, $(-3/p) = 1$ if $p ≡ 1,-5\pmod{12}$ and $(-3/p) = -1$ if $p ≡ -1,5 \pmod{12}$ [duplicate]

For any odd prime $p≥5$, $(-3/p) = 1$ if $p ≡ 1,-5\pmod{12}$ and $(-3/p) = -1$ if $p ≡ -1,5 \pmod{12}$. My solution so far: if $p ≡ 1\pmod{4}$ then $(-3/p) = 1$ exactly when $p ≡ ±1\pmod{12}$ when $p ≡...
1
vote
1answer
176 views

For which prime powers are there solutions to $x^{2} + y^{2} = 0 \pmod {p^a}$ with $(x,p) = (y,p) = 1$?

I have a problem about Jacobi and Legendre Symbols and don't know how to approach it properly since I am new to this subject. For this problem I tried to show that $\left(\dfrac{-1}{p^a}\right) = 1$ ...
2
votes
0answers
71 views

Finding solutions to $x^2\equiv a$ mod $8k+1$, $8k+1$ prime

For $N=4k+3$ prime, a solution can easily be found as $x=a^{k+1}$. This is because: $x^2=a^{2k+2}=a^{2k+1}\cdot a=a^{\frac{N-1}{2}}\cdot a\equiv a\mod N$. A similar construction can be done for $N=8k+...
1
vote
0answers
28 views

Quadratic Integer Ring mod p - Field?

In order to understand a proof of a book I try to get I need to deal with Quadratic Integer Rings. As far as I got till now if I look at $\mathbb{Q}(\sqrt(d))$, $O_{\sqrt(d)}$ and $p \equiv \eta_p \...
0
votes
0answers
61 views

Calculate Jacobi symbol

Calculate the Jacobi symbol $\left(\frac{n^4+n^2+1}{2n^2+1} \right)$ for every integer $n>0$. Using the properties of the Jacobi symbol, $$\left(\frac{n^4+n^2+1}{2n^2+1} \right)=\left(\frac{2n^2+...
0
votes
1answer
56 views

Prove $\bigg(\frac{1(1-m)}{p}\bigg) + \bigg(\frac{2(2-m)}{p}\bigg) + \dots + \bigg(\frac{(p-1)(p-1-m)}{p}\bigg) = -1$. [closed]

How would I go about proving this? Note that I'm not allowed to use quadratic reciprocity since my textbook hasn't covered it.
-1
votes
1answer
88 views

Calculate Legendre symbol

When i calculate the legendre symbol for (101/1739), i end up with (2/27)*(5/27) in the middle of the calculation. I understand how to calculate (5/27), but how do i calculate (2/27). This would have ...
2
votes
4answers
88 views

If $(p^2-1)/8$ is an odd number and $p$ is prime odd number what is $p\pmod8$?

So we know $p^2-1$ is divisible by 8, so $p^2 =1\pmod 8$ but this isn't nothing new because this is true for every odd number p. But how to use the fact that $(p^2-1)/8$ is an odd number ? I started ...
0
votes
1answer
37 views

Analogue of Fermat’s Theorem

The question is “Establish an analogue of Fermat’s Little Theorem for the ring $\mathbb{Z} [\sqrt{3}]$. I know you begin by letting $\alpha \in \mathbb{Z} [\sqrt{3}]$ so there exists integers $a$ and $...
0
votes
0answers
45 views

Investigate the size of $\sum_{x=0}^{p-1}e^{2\pi ix^2/p}$

I attempted to look at the size of this sum, and the hint was to use Legendre symbols to split this sum into 2 sums. But from what I have seen so far, all I manage to do is simplify the sum rather ...
0
votes
1answer
33 views

Testing for primitive roots using quadratic non residue and Jacobi symbol

Is this always true for all cases?? $a$ is a primitive root $modulo$ $n$ $⇒$ $\left(\dfrac{a}{n}\right) = -1$ Is the converse also always true? $\left(\dfrac{a}{n}\right)$ $= -1$ $⇒$ $a$ is a ...
2
votes
0answers
55 views

How to evaluate Legendre symbols more quickly

I'm trying to determine for which primes $p$ we have $\displaystyle\binom{6}{p}=1$, where $\displaystyle\binom{6}{p}$ is the the Legendre symbol. I know how to do this, but my question what is the ...
1
vote
1answer
92 views

Proving Diophantine Equation has no solution using Legendre Symbol

Given that $\left(\frac{10}{23}\right)=-1$. How would I go about showing that $9x^2-46(y^3+3y+1)=10$ has no integer solutions? I believe it has something to do with Quadratic Reciprocity. For ...
2
votes
2answers
274 views

Sum of Legendre symbols is 0?

I have a question regarding this sum: \begin{equation} \sum_{k=1}^{p-1}k\left(\frac{k}{p}\right) \end{equation} where $(k/p)$ is the Legendre symbol mod $p$, for $p>3$. I shall prove that \begin{...
1
vote
1answer
46 views

Cardinality of $ S = \{ x \in \mathbb{Z}_p^* | \phi(1-x^2) = 1 \}$

For prime $p$, let, $ S = \{ x \in \mathbb{Z}_p^* | \phi(1-x^2) = 1 \}$, where $p=4k+1$ and $\phi$ is Legendre symbol. I have to prove that $|S| = 2(k-1)$. I know that there are $(p-1)/2$ residues ...
0
votes
0answers
75 views

Does $x^4 \equiv -17 \pmod{83}$ has root or not?

I need to answer a question "Does $x^4 \equiv -17 \pmod{83}$ has root or not?" Here is my answer. We first prove that $X^2 \equiv -17 \pmod{83}$ has no root by using Legendre symbol. Indeed, $\left( \...

1
2 3 4 5
7