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
22 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 ...
0
votes
1answer
22 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
100 views

How does Legendre symbol formula $(-1)^{{p-1\over 2}{q-1\over 2}}$, actually show the correct value?

I've read about this formula on wikipedia, but attempting to use it just gets me: $$q\equiv 3 \bmod 4\implies p\equiv 1 \mod 4 $$ and$$q\equiv 1 \bmod 4\implies p\equiv 1,3 \mod 4.$$ However, $$1,4,...
1
vote
1answer
23 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
35 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
55 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 ...
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 ...
0
votes
3answers
34 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
39 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
44 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
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 ...
2
votes
2answers
111 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
1answer
27 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
70 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
39 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{...
0
votes
0answers
45 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 \...
0
votes
1answer
43 views

How to factor a polynomial over finite fields?

We want to study the factorization of a specific polynomial with coefficients over finite fields. Let $f\in \mathbb{Z}$ a polynomial, we define the polynomial class as follows: suppose $(\bar{f})$ $\...
1
vote
0answers
32 views

Existence of a non - square solution to a modular equation

Let $p_1, \dots, p_l \in \mathbb{Z}$ be pairwise disjoint odd primes. By the Chinese remainder follows there exists $x \in \mathbb{Z}$ satisfying \begin{align*} x & = 1 \text{ mod } 4 \cdot p_2 \...
0
votes
0answers
22 views

Legendre Transforms

I want to show that the Legendre Transform of a function $g(x) = kf(x-x_0) + m$ for $m$, $k$ constants is equal to $g^*(p) = kf\left(\frac{p}{k}\right)+p \cdot x_0+m$ where $f^*$ is the Legendre ...
-1
votes
1answer
38 views

Algebra of the law of quadratic reciprocity [closed]

I have seen some examples that use the law of quadratic reciprocity in the form $$\left(\frac{p}{q}\right)=(-1)^{\left(\frac{p-1}{2}\right)\left(\frac{q-1}{2}\right)}\left(\frac{q}{p}\right)$$ I ...
1
vote
1answer
52 views

A contradiction in calculating the legendre symbol

I got a contradiction when I calculated the legendre symbol. I felt like there must be something wrong in my calculation but I can't find them. The following is my calculation steps. Note that $13=4\...
2
votes
1answer
32 views

Prove a property of Legendre symbol

In case someone does not know the definition, I first write down the definition. Def Let $a$ be s.t. $(a,m)=1$. Then we say $a$ is a quadratic residue modulo m if the congruence $x^2\equiv a$ (mod $m$...
1
vote
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 $...
1
vote
1answer
46 views

Polynomial evaluates to quadratic residue in $p$ cases

This exercise popped up in a chapter on Legendre symbols. Let $p$ be a prime $3$ $(\textrm{mod } 4)$, and $f(x) \in \mathbb{F}_p[x]$ a polynomial of odd degree. Show that the number of solutions $(...
0
votes
0answers
20 views

Which of these congruences have solutions? [duplicate]

$$x^2 \equiv 134 \text{ mod } 197$$ $$x^2 \equiv 134 \text{ mod } 197^2\times 67$$ $$x^2 \equiv 134 \text{ mod } 197^{30}\times2^{10}$$ $$x^2 \equiv 134 \text{ mod } 197\times 23^2$$ The ...
1
vote
2answers
51 views

Solution to a system of quadratic congruences.

The following is a system of quadratic congruences: $$\left\{\begin{array}{cl}x^{2}\equiv a&\pmod{3}\\x^{2}\equiv b&\pmod{7}\end{array}\right.$$ If $\left(\frac{a}{3}\right)=1=\left(\frac{b}{7}...
1
vote
1answer
49 views

Legendre Symbol: show that $\left(\frac{-3}p\right)=\left(\frac p3\right)$

I am asked to solve the following question Let $p$ be a prime, $p>3$. By considering the cases $p ≡1\bmod4$ and $p≡-1\bmod4$ separately, show that $\left(\frac{-3}p\right)=\left(\frac p3\right)$....
0
votes
0answers
34 views

The law of quadratic reciprocity 'or' statement

I have just seen written that $(\frac{17}{101})$ = $(\frac{101}{17})$. But doesn't the law of quadratic reciprocity state that $(\frac{p}{q})$ = $(\frac{q}{p})$ if $p\equiv1 mod 4$ OR $q\equiv1mod4$?
1
vote
0answers
31 views

The sum $\sum_{r=1}^{p-1} r(r|p)$ when $p$ is an odd prime of the form $4k+3$, $k\geq 1$.

In the book Apostol Analytic Number Theory, $(r|p)$ denotes the Legendre Symbol. The exercise tell us to prove when $p\equiv 1\pmod 4$, $$\sum_{r=1}^{p-1}r(r|p)=0.$$ I can solve this quickly, but I ...
2
votes
1answer
56 views

Exercise on Gauss sums

Formal count of length-3 progressions, given by: $A(p)$=#{$(r,s,t): \big(\frac{r}{p}\big)=\big(\frac{s}{p}\big)=\big(\frac{t}{p}\big)=1; r \neq s; s-r\equiv t-s$ (mod $p$). Here $p$ is a prime. In ...
1
vote
0answers
31 views

Factoring out Kloosterman Sum

I'm reading Iwaniec's book and he says Kloosterman sum factors into $S(n,n;c)=S(n\bar{q},n\bar{q};r)T(n\bar{r},n\bar{r};q)$ where $n$ is square free and $c=rq$ such that $(q,n)=(q,r)=1$(i.e. $q$ is ...
0
votes
1answer
34 views

Legendre symbols and primitive roots modulo $p$ [duplicate]

Suppose that $\omega$ is a primitive root modulo $p$. What is $(\frac{\omega}{p})$? $p$ is prime.
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 ...
3
votes
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 ...
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}{...
0
votes
0answers
33 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 ...
0
votes
1answer
76 views

Is there integer $x$ such that $79|7x^2+4x-23$

Is there integer $x$ such that $79|7x^2+4x-23$ ? I keep getting that there is $x$ that satisfies this condition, but online calculator keeps saying that there is not. I worked it out using Legendre'...
0
votes
1answer
22 views

Legendre's proof involving linearity independence

Show that any polynomial of degree n is a linear combination of P0(x), P1(x), ..., Pn(x) Actually I have no idea how to start with a proof involving "any". Can someone help??
3
votes
1answer
98 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)$ ...
2
votes
2answers
95 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
79 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\...
2
votes
2answers
147 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)\...
2
votes
1answer
99 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$$
1
vote
1answer
41 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
177 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
65 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
343 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
64 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 ...
2
votes
0answers
343 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
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 ...