Questions tagged [legendre-symbol]

For questions involving the Legendre symbol, $\genfrac{(}{)}{}{}{a}{p}$ for integer $a$ and prime $p$.

48 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
7
votes
0answers
128 views

Connection between sgn character and the Legendre symbol

Today, while I was lecturing on the Legendre symbol, I realized that the phenomenon: "the product of two non-squares is a square" isn't so foreign. For example, for $\mathbb R^\times$, the squares are ...
6
votes
0answers
505 views

Application of Legendre, Jacobi and Kronecker Symbols

Legendre, Jacobi and Kronecker Symbols are powerful multiplicative functions in ...
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
0answers
176 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}]$...
3
votes
0answers
137 views

Why the expansion of functions of 2 variables in legendre polynomials does not take into account all products Pi (x) Pj (y)?

My question arises from this reading link (In this article, in equation 6 on page 3, also expands a function of 2 variables in this way Parametric estimate of intensity inhomogeneities applied to MRI),...
3
votes
0answers
149 views

Proof Involving Legendre Symbol and Quadratic Residue Multiplication

I am struggling with this proof. I really cannot think of where to start: Let $p$ be an odd prime, prove that: $$\left(\frac{1 \cdot 2}{p}\right) + \left(\frac{2 \cdot 3}{p}\right) + \left(\frac{3 \...
3
votes
0answers
376 views

Legendre symbol identity: $\sum_{a=1}^{p-1}a \cdot (\frac{a}{p} )$ and $\sum_{a=1}^{p-1}2^a \cdot (\frac{a}{p} )$

I am trying to solve the following problems ($p$ is an odd prime). Find the sum $$\sum_{a=1}^{p-1}a \cdot \left (\frac{a}{p} \right),$$ Find the sum $$\sum_{a=1}^{p-1} 2^a \cdot \left (\frac{a}...
3
votes
0answers
247 views

the number of solutions of the congruence $x^2 \equiv a \pmod m$ is $\prod_{p \mid m} \left(1+ \left(\dfrac{a}{p} \right) \right).$

Suppose that $m$ is odd. Show that if $\gcd(a,p) = 1$ then the number of solutions of the congruence $x^2 \equiv a \mod m$ is $\displaystyle \prod_{p \mid m} \left(1+ \left(\dfrac{a}{p} \right) \right)...
2
votes
0answers
352 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 \...
2
votes
0answers
34 views

Legendre symbol trouble.

I did the same calcultation, for the legrange symbol, twice and got two different answers. Could someone please point out where I went wrong for future reference. 1) $\bigg(\frac{79}{81}\bigg)=(-1)^{\...
2
votes
0answers
111 views

Legendre symbols as multiplicative homomorphisms in number fields

$\newcommand{\legendre}[2]{\genfrac{(}{)}{}{}{#1}{#2}}$ Suppose we have a finite set of rational primes $B=\{p_1,\ldots,p_k\}$, and $V=\{ x\in\mathbb{Q}^*~|~x\text{ contains only primes in B} \}$. So ...
2
votes
0answers
84 views

Legendre symbol multiplicativity

Is there some formal proof of Legendre symbol's being multiplicative? It seems pretty intuitive but I can't think of a way to formally show it?
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
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 ...
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 ...
1
vote
0answers
27 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)$ ...
1
vote
0answers
347 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 ...
1
vote
1answer
26 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 ...
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 \...
1
vote
1answer
87 views

How can we summarize Legendre symbol $(\frac{11}{p})$

We note that $11\equiv 3 \pmod 4$. So by using the law of quadratic reciprocity to get $(\frac{p}{11})$, we need to discuss the residue of $p\pmod 4$. I'm wondering how to give a specific formula ...
1
vote
1answer
79 views

Divisor sum or möbius inversion of the Jacobi Symbol?

We're doing number theory and we've separately covered the topics of Quadratic Reciprocity and Multiplicative Functions. I just noticed that if one of the parameters in the Jacobi symbol is constant -...
1
vote
2answers
77 views

Finding $n$-th root of $p_1$ modulo $p_2$

How to calculate $n$-th root of a prime number $p_1\ \mbox{modulo}\ p_2$? That is: $x = p_1^\frac{1}{n}\ \bmod \ p_2$. I have a notion that somehow Legendre symbols can be use, however I can't quite ...
1
vote
1answer
534 views

Expansion in terms of legendre polynomial

Obtain the first three terms in the expansion of function in terms of legendre polynomial F(x) in a series of the form $$ F(x) = \sum_{k=0}^{\infty} A_k P_k(x) $$ where $$F(x)=\{\cos(x) \...
1
vote
0answers
47 views

A peculiar trigonometric sums with squares and Legendre symbols

Let $p$ be a prime number of form $8k + 1$. Let $C(p) :=\sum_{k = 0}^{p-1} \cos{\left( \frac{-2k^2 \pi}{p}\right)} \cdot \left( \frac{k}{p} \right)$ where $\left( \frac{k}{p} \right)$ is the Legendre ...
1
vote
1answer
75 views

Show that set of reduced residue classes is a subgroup of the multiplicative group of reduced residue classes

Let m $\in Z^+$ and let G denote the set of those residue classes a(mod m) such that $a^\frac{m-1}{2} = \left(\frac{a}{m}\right)$ (mod m). Show that if a $\in$ G and b $\in$ G then ab $\in$ G. Also ...
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
0answers
117 views

Discrete logarithm problem, existence and parity

Let $p>2$ be a prime number such that $p-1=2^st, s>0,t$ odd. Let $a,d\in \mathbb … {Z}^* /p \mathbb{Z}$ with $\left(\frac{a}{p}\right)=1$ and $\left(\frac{d}{p}\right)=-1$, where $\left(\frac{a}{...
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 ...
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
0answers
25 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 ...
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$?
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??
0
votes
0answers
58 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 ...
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
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(\...
0
votes
1answer
43 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 ...
0
votes
1answer
107 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
36 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}) =...
0
votes
0answers
80 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 ...
0
votes
1answer
70 views

Evaluate the Legendre Symbols (503/773)

Evaluate the Legendre Symbols (503/773) Solution: (503/773) = (270/503) = (2/503)(3^3/503)(5/503) = 1*(5/503)(3/503) = (503/5)(-1)(503/3) = -(3/5)(2/3) = -1 I don't understand how they obtain (-(3/5)...
0
votes
1answer
93 views

Legendre Symbol by Fermat's little theorem.

My work: How do continue with part $b$, I'm so confused.
0
votes
1answer
44 views

Showing $\sum_{b=0}^{N-1}\left(\frac{b}{p}\right)\zeta_M^{-kb} = 0$

I want to evaluate $$\sum_{b=0}^{N-1}\left(\frac{b}{p}\right)\zeta_M^{-kb}$$ for $p$ an odd prime, $p|N$, $M|N$, $(k,M)=1$. $\left(\frac{b}{p}\right)$ is the Legendre symbol. I'm fairly sure it should ...
0
votes
1answer
73 views

Numbers with prescribed Legendre symbols

In this text the "old" definition of the Legendre symbol is used: $\left( \frac{a}{p}\right) = \begin{cases} +1, & \text{ if $a$ is a quadratic residue } \mod{p} \\ -1 & \text{ if $a$ is a ...
0
votes
2answers
86 views

Show that $x^2+x+23\equiv 0\mod 173$ has a solution $\iff \left(\frac{28}{173}\right) = 1$

Show that $x^2+x+23\equiv 0\mod 173$ has a solution $\iff$ the legendre symbol $\left(\frac{28}{173}\right) = 1$ How can I determine this? I dont see the relation between the legendere symbol (...
0
votes
0answers
37 views

What is the solution to $F\left(n\right)=F\left(n-1\right)+\left(\frac{2}{n}\right)F\left(n-2\right)$ with Legendre symbol?

The recurrence $F\left(n\right)=F\left(n-1\right)+\left(\frac{2}{n}\right)F\left(n-2\right) $ was proposed here Because of the way the question was formatted, a commenter asked if the $\left(\frac{2}{...
0
votes
0answers
21 views

The map $\left(\frac{.}{p}\right):=\mathbb F_p \rightarrow [\pm1]$ taking $a\in \mathbb F_p$ to $\left(\frac{a}{p}\right)$ is homomorphism

Prove that the map $\left(\frac{.}{p}\right):=\mathbb F_p \rightarrow [\pm1]$ taking $a\in \mathbb F_p$ to $\left(\frac{a}{p}\right)$ is a homomorphism I don't know how to even start this problem. ...
0
votes
1answer
213 views

Verifying quadratic reciprocity for the Jacobi symbol

I am trying to prove: If $m,n$ are odd coprime positive integers, then $$\Big(\frac mn\Big)\Big(\frac nm\Big)=(-1)^{\large\frac{m-1}2\frac{n-1}2},$$ where $\big(\frac mn\big)$ is the Jacobi ...
-1
votes
1answer
23 views

Verification: have I worked this legendre symbol correctly

Compute $(\frac{92}{11}$). Now $92^2 \equiv x^2\ mod(11) $ Now since there is no such x that satisfies this, so the legendre symbol is $-1$. Is this right? Also, can somebody explain in a slightly ...