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
1
vote
0answers
23 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
45 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
51 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
40 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
53 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
27 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
40 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
17 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
49 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
50 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
88 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
37 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
70 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( \...
8
votes
1answer
110 views

Name of group of order $p-\bigl(\frac ap\bigr)$ constructed from field $\Bbb Z_p$?

Let $p$ be an odd prime, and $a$ be an element of field $\Bbb Z_p$. Define $l$ as the Legendre symbol $\displaystyle\biggl(\frac ap\biggr)$. When $l=+1$, define $b$ as a particular solution of $b^2=...
1
vote
1answer
51 views

Two different outcomes (-1 and 1) for Legendre symbol?

I'm trying to solve the Legendre symbol $\left(\frac{97}{131}\right)$. With my calculation I end up with 1. ...
3
votes
1answer
85 views

Show that $x^4 \equiv -4$ (mod $p$) is solvable iff $p \equiv 1$ (mod $4$)

Given an odd prime $p$, I want to prove that $x^4 \equiv -4$ (mod $p$) is solvable if and only if $p \equiv 1$ (mod $4$). More specifically, I want to prove this using a hint, which says to first ...
0
votes
2answers
89 views

Legendre symbol sum $\sum\limits_{x=4}^{p-1} \left(\frac{x(1-p-x)}{p}\right)$

I am studying the sums of Legendre symbol and I have a question about it. Let $p$ is a prime number, $p >7$, $p\equiv 7 \pmod 8$. Find $$\sum_{x=4}^{p-1} \left(\frac{x(1-p-x)}{p}\right).$$ I had ...
1
vote
0answers
84 views

Primality testing when $n\equiv3\pmod{4}$ and $gcd(totient(n), (n-1)/2) = 1$

Euler proved that if $n$ is prime, $a^{\frac{n-1}{2}}\equiv \genfrac{(}{)}{}{}{a}{n}\pmod{n}$, which for primes is $1$ if $a$ is a quadratic residue mod $n$, $-1$ if $a$ is a non-quadratic residue mod ...
0
votes
2answers
80 views

a) and b) Suppose a = primitive root mod p for an odd prime p. Show that $\left(\frac{a}{p}\right)$ = -1

I understand how to evaluate Legendre symbols when given discrete numbers. For example the Legendre symbol for the following: $\left(\frac{3}{105953}\right)=\left(\frac{105953}{3}\right)=\left(\frac{2}...
1
vote
1answer
30 views

Computing Legendre symbol of a (p = prime number raised to prime number) mod p?

Example: What is the Legendre Symbol $ (\frac{3^{24671}}{105953}) $? Since ($\frac{3}{105953}$) $= -1$ and the exponent p = prime = $24671$ is odd, would this mean the answer would be -1? Please ...
0
votes
0answers
30 views

Summations of Legendre Symbols with an odd prime p [duplicate]

Let $p$ be an odd prime. For any integer $k$, define $S(k,p) = \sum^{p}_{x=1}(\frac{x(x+k)}{p})$. (i) Show that S(0,$p$) = $p$-1 (ii) Show that if p does not divide k then $S(k,p) = S(1,p)$ (iii) ...
0
votes
0answers
56 views

Legendre symbol and variable denominator

Suppose $z\in\mathbb{Z}$ and let $p$ be a prime, such that $p>>z$. Can I say something what happens to Legendre symbol $(\frac{z}{p})$ if I vary $p$? One obvious answer comes when $x^2=z$ for $...
1
vote
1answer
46 views

A number theory problem: show $N_{x^2−n}(p^k) = 2$ for all $k = 1,2,3,…$

One of my number theory exercises this week asks the following: Let $n$ be an odd natural number and assume that the Legendre symbol $\left(\frac np\right)$ equals $1$ for some prime $p>2$. ...
1
vote
2answers
38 views

Prove that $\sum_{a\in\mathbb{Z}/p\mathbb{Z}} (a/p)a^i$ is $0$ if $i\neq (p-1)/2$ and $p-1$ if $i= (p-1)/2$.

Let $0\leq i\leq p-1$. I want to prove that $$\sum_{a\in\mathbb{Z}/p\mathbb{Z}} \left(\frac{a}{p}\right) a^i$$ is $0$ is $i\neq (p-1)/2$ and $p-1$ if $i= (p-1)/2$. I know that this holds for $i=0$ ...
4
votes
1answer
43 views

Jacobi Symbol: $\sum_{n=1}^{p}\left(\sum_{m=1}^{h}\left(\frac{m+n}{p}\right)\right)^2=h(p-h)$

Show that if $p$ is and odd prime and $h$ is an integer, $1\le h \le p$, then $$\displaystyle\sum_{n=1}^{p}\left(\sum_{m=1}^{h}\left(\frac{m+n}{p}\right)\right)^2=h(p-h)$$ where $\left(\frac{m+n}{p}\...
1
vote
1answer
29 views

Calculating Legendre symbol : $\left(\frac{3}{2^{2^n}+1}\right)$ , n being positive.

I want to find the Legendre symbol : $\left(\frac{3}{2^{2^n}+1}\right)$ for any positive n. Also I want to find the Legendre symbol for: $\left(\frac{5}{2^{2^n}+1}\right)$, when $n>1$ Solution: ...
1
vote
0answers
20 views

lattice structure of a subset of $\Bbb Z^2$

Let $d$ be a squarefree integer. Suppose prime p can be written as $p = a^2 − db^2$ for some integers $a$ and $b$. Determine the (lattice structure) of $A=\{(x, y)\in\Bbb Z^2 : p | x^2 − dy^2\}$ , ...
1
vote
1answer
27 views

Legendre symbol for a prime of the form $m^2-dn^2$

Let $p$ be a prime of the form $p=a^2-db^2$ with $d$ square-free and $a,b \in \Bbb Z$ Prove that $(\frac{d}{p})=1$. We have $(\frac{d}{p})(\frac{b^2}{p})=(\frac{a^2}{p})$ Hence $(\frac{d}{p})\ge 0$ ...
0
votes
2answers
54 views

Show that $(n^5-n+3)$ is not a perfect square

I need to show that $n^5-n+3$ is not a perfect square. I think I have to use the Legendre symbol and quadratic residues, but I did not see how. Instead I tried the following: For $n=0,1$, we see ...
0
votes
1answer
55 views

Number of values such that quadratic residue is 1

Let $n$ be an odd integer with $i$ prime factors. how many values of $x (mod\ n)$ are there for which $x^2 ≡ 1 (mod\ n)$? I used Legendre's symbol to find the following: Let $x$ be such that $x^2 ≡ ...
1
vote
1answer
45 views

Existence of an integer $i$ such that $i$ and $i+1$ are both squares mod $p$

Let $p$ be a prime $\ne 2,5$ Prove $\exists i\le 9$ such that $(\frac{i}{p})=(\frac{i+1}{p})=1$ where $(.)$ is the Legendre symbol. I tried to use the Euler formula $(\frac{a}{p})\equiv a^{\frac{p-1}...
0
votes
0answers
30 views

Consequences of Jacobi and Legendre Symbols

For $a\in\mathbb{Z}$ that is not a perfect square such that $a\equiv0\text{ or }1\left(\mod4\right)$, define $$\left(\frac{a}{2}\right):=\begin{cases} 1 & \text{if }a\equiv1\left(\mod8\right)\\ -1 ...
2
votes
2answers
49 views

$(\frac{a}{p})=(\frac{b}{p})$ iff $\exists c: b\equiv\ c^2a\pmod p$ and $(c,p)=1$.

Let $p$ be a prime. With $()$ standing for Legendre symbol, prove $(\frac{a}{p})=(\frac{b}{p})$ iff $\exists c: b\equiv\ c^2a\pmod p$ and $(c,p)=1$. Working out the 3 possible cases $\Leftarrow)$ is ...
4
votes
1answer
88 views

A prime number is not a quadratic residue modulo some prime without quadratic reciprocity

In Cox's book "Primes of form $x^2 + ny^2$", I stumbled upon a lemma $ \newcommand{\Z}{\mathbb{Z}} $ Lemma 1.14: If $D \equiv 0,1 \pmod{4}$ is a nonzero integer, then there is a unique homomorphism ...
1
vote
1answer
68 views

quadratic residue such as “$(n|p)= -1$”(quadratic reciprocity)

(Note: (n|p)=1 is legendre-symbol.) So need to find primes where $(n|p)=1$ So we have 1- $1\pmod 4$ where we use quadratic residue of $n$ along with $\pmod n$ to find solutions. 2- Then we have $3\...
0
votes
1answer
65 views

How to determine $(\tfrac{-5}{p})$ $\mod 20$?

There was a question in a past exam paper that asked Find criteria $\mod(20)$ for determining the Legendre symbol $(\tfrac{-5}{p})$ where $p\geq 7$. I am very confused by what this means as I ...
1
vote
1answer
86 views

Is there a quick way of using Gauss's lemma for large $p$?

Gauss's lemma in number theory states that if we have a number $a$ which is coprime to a prime $p$ then if we consider the set $S=\{a,2a,3a,.....((p-1)/2)a\}$ then say that if the number of elements ...
1
vote
1answer
26 views

Can at least one primitive root $w$ of $N$ be expressed as $a^2-b$, where $(b|N)=-1$

I am stuck on a thought experiment: can any (or for that matter, at least one) primitive root $w$ of $N$, $N$ prime, be expressed as $w=a^2-b$, where $(b|N)=-1$, and $a,b\in\mathbb{N}$. We know that ...
0
votes
1answer
71 views

Assume that p and q are odd primes and $p \equiv q \pmod {28}$. Show that $(\frac{7}{p}) = (\frac{7}{q})$.

Assume that p and q are odd primes and $p \equiv q \pmod {28}$. Show that $(\frac{7}{p}) = (\frac{7}{q})$. Could anyone give me a hint for the solution please?
-1
votes
1answer
67 views

Why if the Legendre symbol satisfy $\left(\frac{a}p\right)=\left(\frac{p}a\right)$ then $\left(\frac{a}p\right) = 1$?

Sorry for my stupid question: This is in completion to this question Let $p$ be a prime of the form $p = a^2 + b^2$ with $a,b \in \mathbb{Z}$ and $a$ an odd prime. Prove that $(a/p) =1$ Why if the ...
0
votes
3answers
48 views

Exponentiation with odd number in modular arithmetic

Show that if $n\geq3$ is odd, then $2^n-1\equiv7\mod24$. I tried solving this backwardly. We want to prove that $2^3(2^{n-3}-1)=2^n-2^3\equiv0\mod24$. Since $\frac{24}{2^3}=3$, this leaves us to ...
1
vote
1answer
41 views

Question on modular arithmetic with prime numbers

Let $p\neq3$ be a prime conguent to $3\pmod4$ and let $q$ be a prime divisor of $(12p)^{2019}+1$ satisfying $q\equiv p^2+1\pmod{3p}$. Determine $q\pmod 4$. I tried solving the problem as follows. ...
0
votes
1answer
45 views

Proving that $n$ is not a prime [duplicate]

Let $n=3^{100}+2$ and assume that $X^2-53$ does not have zeroes in $\mathbb{Z}/ n\mathbb{Z}$. Show that $n$ is not a prime. I tried solving this problem by assuming that $n$ is a prime (in order to ...
3
votes
2answers
53 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
130 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 ...
0
votes
1answer
29 views

Is the Legendre symbol (9/8) the same as Legendre symbol $3^2/2$? [closed]

Is the Legendre symbol (9/8) the same as Legendre symbol $3^2/2$? if so, by what property?
0
votes
3answers
236 views

How can I prove that $ (3/p) = -1$ if $ p \equiv \pm 5 \pmod {12}$

I know how to prove that $ (3/p) = 1$ if $ p \equiv \pm 1 \pmod {12}$ but I need to prove that $ (3/p) = -1$ if $ p \equiv \pm 5 \pmod {12}$, which the book write it as it is without explaining why ...
0
votes
2answers
49 views

A proof of a property of the Legendre symbol.

My book mentioned the following property of Legendre symbol: $$\left(\frac{a^2}{p}\right) =1, $$ And it said in the proof That the integer a trivially satisfies the congruence $x^2 \equiv a^2 \pmod{...
1
vote
2answers
389 views

How to prove that the Legendre symbol is multiplicative?

The proof is given here in the answer Proving $(\frac{n}{p})$, a Legendre symbol, is multiplicative But I do not understand it, Also the definition in the book for Legendre symbol says that if $p|a$ ...
0
votes
0answers
59 views

How to classify the factorization of polynomials over finite fields?

I want to study the factorization of a specific polynomial with coefficients over finite fields. Let $f\in \mathbb{Z}$ a polynomial, I define the polynomial class as follows: suppose $(\bar{f})\in \...

1
2 3 4 5 6