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
55 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
68 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
24 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
44 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
57 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
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
40 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
41 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
80 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
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
71 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
40 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{...
2
votes
2answers
114 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
47 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
45 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 \...
1
vote
1answer
110 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
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
54 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$...
0
votes
0answers
26 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
vote
1answer
47 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
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
35 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
35 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.
1
vote
2answers
57 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}...
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??
2
votes
2answers
97 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\...
1
vote
1answer
42 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
180 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
67 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
350 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
65 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
353 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 ...
3
votes
1answer
103 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
45 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
59 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
44 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
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 ...
4
votes
0answers
68 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
99 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
672 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(\...