The tag has no wiki summary.

learn more… | top users | synonyms

0
votes
1answer
31 views

Quadratic congruences problem $(x^2-a)(x^2-b)(x^2-ab)$ ≡ 0 (mod p)

Let p be an odd prime and let a,b ∈ Z such that p ∤ a. Prove that the congruence $(x^2-a)(x^2-b)(x^2-ab)$ ≡ 0 (mod p) is always solvable. Not sure where to begin here.
3
votes
2answers
86 views

elementary proof that infinite primes quadratic residue modulo $p$

$p \gt 2$ is a prime, then there are infinite primes $q$ such that $q$ is a quadratic residue modulo $p$. With Dirichlet's theorem on arithmetic progressions, the problem is easy! How about ...
1
vote
1answer
41 views

Analytic proof of quadratic reciprocity

Is there any proof of quadratic reciprocity that is more analytic than those described on Wikipedia (http://en.wikipedia.org/wiki/Proofs_of_quadratic_reciprocity)?
3
votes
1answer
54 views

Consecutive quadratic residues

I was studying quadratic reciprocity laws and came across the following question: Is it true that for every $k \in \mathbb{N} $ there exists a prime $p$ such that $1,2,...,k$ are all quadratic ...
1
vote
1answer
31 views

Quadratic Reciprocity as a consequence of Eisenstein Reciprocity

I was recently looking at the wikipedia page on Eisenstein Reciprocity, which says it "extends Quadratic Reciprocity." However, though the two do seem to be related, I don't completely understand how ...
2
votes
1answer
51 views

Prove that S consists of the quadratic residues mod (p) and T consists of the quadratic non-residues mod (p)

All the followings are $\bmod$ $p$ Let p be an odd prime. Suppose that the set $X = \{ 1,2, . . . , p-1\}$ can be written as the union of two nonempty subsets $S$ and $T$, where $S \neq T$, such that ...
2
votes
1answer
158 views

Quadratic Reciprocity Joke

I found a joke on a site made by user Zev Chonoles on quadratic reciprocity, the joke is as follows: $$\text{Quadratic reciprocity: } \left(\frac{p}{q}\right)=\left(\frac{q}{p}\right), \text{ up to ...
2
votes
1answer
30 views

Jacobi symbol $\left(\frac{(n+1)/2}{n}\right)$

Let $(\frac{a}{n})_J$ be Jacobi symbol defined by \begin{equation} \left(\frac{a}{n}\right)_J=\left(\frac{a}{p_1}\right)^{e_1}\left(\frac{a}{p_2}\right)^{e_2}\cdots\left(\frac{a}{p_k}\right)^{e_k} ...
1
vote
2answers
35 views

Number of elements that exist so $b^3 \equiv a\pmod n$, when n is composed of p and q who are prime numbers

Given $2$ prime numbers,$ p$ and $q$, that are both not even, and $3$ doesn't divide $p-1$ or $q-1$, and $n=pq$, how many elements in $Z^*_n$ exists that has $b$ such that $b^3\equiv a\pmod n$ . I ...
5
votes
6answers
290 views

What is the point of quadratic residues?

What is the most motivating way to introduce quadratic residues? Are there any real life examples of quadratic residues? Why is the Law of Quadratic Reciprocity considered as one of the most ...
0
votes
1answer
47 views

Legendre symbols (p/q) = (a/q) [duplicate]

Suppose q and p are odd primes and p = q+4a for some integer a. From the properties of the Legendre symbol and the Law of Quadratic Reciprocity prove that the following two identities hold. (p/q) = ...
0
votes
2answers
52 views

$2^{4n+1} \equiv 1 \pmod{8n+7}$, this has been bugging me

Here is the question: Suppose that $p$ is an odd prime. The law of quadratic reciprocity says that $x^2\equiv 2\pmod p$ has a solution. if $p\equiv1 \text{ or } 7 \pmod 8$. Prove that ...
0
votes
2answers
68 views

If $x^2 \equiv a \bmod p$ has a solution, does it necessarily have infinitely many solutions? [closed]

If not, how would you prove it for a specific case? Such as, for example, $x^2 \equiv 2 \bmod 7$ ?
1
vote
1answer
37 views

Suppose $p$ and $q$ are odd primes and $p = q + 4a$ for some $a$. Prove that $(\frac ap) = (\frac aq)$ holds. [duplicate]

This problem also had me prove that $(\frac pq) = (\frac aq)$, but I've already managed to do that. I've tried messing around with the Law of Quadratic Reciprocity but can't get anything. I've also ...
0
votes
2answers
23 views

Quadratic character of 3

Using the QRL prove that, for any odd prime $p$, $(3/p) = 1$ if $p$ is congruent to $1$ or $11 \pmod{12}$. Using the Quadratic reciprocity law, $(3/p)(p/3)=(-1)^{(3-1)(p-1)/4}$, I get that the ...
1
vote
1answer
37 views

Prove that $\left(\frac2p\right) = 1$ if $p \equiv 1,7 \pmod 8$ and $\left(\frac2p\right) = -1$ if $p \equiv 3,5 \pmod 8$ using ring theory

Let $p$ be an odd prime number and let $\alpha = [X] \in R=\mathbb F_p[X]/\langle X^4+1\rangle$, and $y = \alpha + \alpha^{-1}$ I've proven: 1) $\alpha$ is a primitive eight root of unity in $R$. ...
0
votes
1answer
134 views

Quadratic Reciprocity [duplicate]

For any integer $a$ and any two primes $p,q$ with $(p,q)=1$. Prove that if $p \equiv q\pmod {4a}$, then $\displaystyle\left(\frac ap\right)=\left(\frac aq\right)$ I know I need to write $a=(−1)^{e_0} ...
1
vote
1answer
93 views

Quadratic Reciprocity

For any integer $a$ and any two primes $p,q$ with $(p,q)=1$. Prove that if $p \equiv q$ mod $4a$, then $(\frac{a}{p})=(\frac{a}{q})$ I know I need to write $a=(−1)^{e_0} 2^{e_2} p_1 p_2 \cdots p_r$ ...
1
vote
0answers
39 views

Show that $x^2\equiv a \pmod {2^n}$ has a solution where $a\equiv1 \pmod 8$ and $n\ge3$

Show that $$x^2\equiv a \pmod {2^n}$$ has a solution where $a\equiv1 \pmod 8$ and $n\ge3$ Actually, the question I had to solve was more complicated something like this: $x^2\equiv a ...
4
votes
2answers
98 views

Show that prime $p=4n+1$ is a divisor of $n^{n}-1$

Show that the prime number $p=4n+1$ is a divisor of $n^{n}-1$ Ok, the question itself is simple as hell, but I couldn't think of a simple way to solve this question. I tried to solve the ...
2
votes
0answers
105 views

When quadratic formula $ax^2 + bx +c = 0$ (mod p) is solvable modulo prime p?

I am learning about quadratic congruences and I don't now how to decide, for which a,b,c and p there is a solution of the congruence. It is sufficient if the determinant $\sqrt{b^2-4ac}$ has a ...
0
votes
0answers
35 views

How do I prove that $x^2\equiv-1\pmod{p}$ [duplicate]

How do I prove that $x^2\equiv-1\pmod{p}$ iff $p$ is prime at form: $p=4n+1$. I have to use Wilson theroem... (I'm asking this, becuase I didn't understand it from my prev. Q, how it proves that ...
0
votes
1answer
236 views

Solve quadratic congruence using the Chinese Remainder Theorem

Solve $x^2 \equiv$ -1 (mod 205) I have that as 205 = 5 x 41 this becomes: $x^2$ $\equiv $ -1 (mod 5) $x^2$ $\equiv $ -1 (mod 41) then i'm not sure where to go. I can see 32 is a solution but I ...
2
votes
2answers
98 views

Number Theory: Solutions of $ax^2+by^2\equiv1 \pmod p$

Assume $p$ is a prime number and $\gcd(ab, p)=1$. Show that the number of integer solutions $(x, y)$ of $ax^2+by^2 \equiv 1 \pmod p$ is $$p - \left(\dfrac{-ab}{p}\right)$$ where ...
0
votes
1answer
45 views

Proving something with Wilson's Theorem [continued.]

At first I asked this: Proving something with Wilson theorem. Now I have to prove that if $p=4n+3$ it's impossible to represent $-1$ in the form $x^2$ modulo $p$. How can I prove it? Thank you!
2
votes
2answers
110 views

Proving something with Wilson theorem

I need to prove that $x^2\equiv -1\pmod p$ if $p=4n+1$. ($p$ is prime of course...) I need to use Wilson theorem.
2
votes
1answer
114 views

A condition for an odd prime to be represented by a binary quadratic form of a given discriminant

Let $f = ax^2 + bxy + cy^2$ be an integral binary quadratic form. We say $D = b^2 - 4ac$ is the discriminant of $f$. If $D < 0$ and $a > 0$, we say $f$ is positive definite. It is easy to see ...
0
votes
1answer
412 views

Proofs of the properties of Jacobi symbol

The definition and properties of Jacobi symbol are stated in this article. I don't have a textbook handy containing the proofs of the following properties of Jacobi symbol. It seems to me that not ...
1
vote
1answer
114 views

Quadratic Reciprocity - Legendre Symbols

Find the value of $((1\cdot 2)/73)+((2\cdot 3)/73)+...+((71\cdot 72)/73)$. This is based off each fraction being a Legendre Symbol. I tried to find a pattern... but I could't find anything. Also, I ...
5
votes
0answers
74 views

What should be taught about the reciprocity law for high school gifted student

This autumn I have to teach a mini course for a small group of high school student (mathematical gifted class) on Quadratic Reciprocity Law (3 lectures in ten hours). This is the requirement of the ...
8
votes
1answer
162 views

Quadratic extensions of $\mathbb Q$

This is a question from Lang's ANT, Thm 6, ch.IV, $\S2$. It states that every quadratic extension of $\mathbb{Q}$ is contained in a cyclotomic extension and that it's a direct consequence of the ...
2
votes
1answer
65 views

Find $m, n$ such that $\frac{n^2 + 1}{m^2 + 1 }$ is an integer multiple of a perfect square

I'm trying to find $n,m \in \mathbb{N}$ such that $\sqrt{ \frac{n^2+1}{2(m^2+1)}}$ is rational. I see that if $a,b$ are relatively prime $\sqrt{ \frac{a}{b}}$ is rational if and only if $a,b$ are ...
2
votes
1answer
104 views

Quadratic congruences

Is there an algorithm to solve the quadratic congruence $x^2\equiv D \pmod m$ for any $D$ and $m$? I searched a bit and found algorithms for $m$ prime and $\gcd(D, m) = 1$. None of them gave a ...
2
votes
1answer
70 views

Quadratic residues mod $n$ of $n-1$

While investigating something about square numbers, I started to wonder which numbers $n$ have quadratic residues of $n-1$. Obviously all $n$ of the form $m^2+1$ will work. But there are other numbers ...
1
vote
1answer
48 views

Showing that if $p_1\equiv p_2 \pmod{4n}$, then $(\frac{n}{p_1})=(\frac{n}{p2})$

Let $n$ be an integer and $p_1$, $p_2$ be primes such that $p_1 \equiv p_2 \pmod{4n}$. Prove $\left(\dfrac{n}{p_1}\right)=\left(\dfrac{n}{p_2}\right)$. 2 cases: $p_1=4nk_1+1$, $p_2=4nk_2+1$. ...
3
votes
2answers
146 views

Probability that $x \equiv 3 \pmod{4}$

I am working on a number theory project and I am interested in the following statement: What is the probability that an integer $x$ has the property that $|x| \equiv 3 \mod{4}$? This seems ...
1
vote
2answers
352 views

When computing the Legendre symbol $(\frac{3}{p})$, how to combine different congruences together into one statement?

I try to find Legendre symbol for $\left(\dfrac{3}{p}\right)$. This is what I did so far: case 1: $p=3\mod{4}. $ so $\left(\dfrac{3}{p}\right)=-\left(\dfrac{p}{3}\right)$. now ...
-1
votes
1answer
60 views

Prove of Quadratic residual

Let $p$ be a prime and $q$ a primitive root modulo $p$. How do I show that q is a quadratic residue modulo $p$ if and only if $a \equiv q^{2k}\pmod p$ for some integer $k$?
1
vote
1answer
234 views

If $p \equiv 1 \mod{4}$ is prime, how to find a quadratic nonresidue modulo $p$?

If $p \equiv 3 \mod{4}$ is prime, then $-1$ is a quadratic non-residue modulo $p$. This is not the case when $p \equiv 1 \mod{4}$. How can we find a quadratic non-residue in this case? At least one ...
0
votes
3answers
232 views

Determine the number of solutions for quadratic equation modulo prime

Given that $106$ is quadratic residue $\bmod\ 139$, how can I determine the number of solutions to the following equation? $$x^2 \equiv 106 \pmod{139}$$
3
votes
2answers
198 views

Quadratic Reciprocity: Determine if 11 is a quadratic residue $\mod p $for primes of the form: 44k+5?

I'm currently studying for exams and this has me stuck. A sample question from a past paper states: Use the quadratic reciprocity theorem to determine whether $11$ is a quadratic residue $\mod p$ ...
0
votes
1answer
206 views

Quadratic reciprocity and proving a number is a primitive root

Let $p$ and $q$ be odd primes. Show that 2 is a primitive root of $q$, if $q = 4p + 1$
1
vote
1answer
109 views

Law of Quadratic Reciprocity question

If $p$ and $q = 10p+3$ are odd primes, show that the Legendre symbols $(\frac{p}{q})$ and $(\frac{3}{p})$ are equal.
1
vote
0answers
121 views

solution count of quadratic form congruences

Let $(L,q)$ be an even Lorentzian lattice of signature $(1,l-1)$, i.e., $q(\lambda) \in \Bbb Z$ for all $\lambda \in L$ and the (non-degenerate) quadratic form $q$ is of type $(1,l-1)$ (the ...
3
votes
3answers
81 views

Is 3 ever a seventh power mod a prime $p$ if $p\equiv 1 (7)$

I had a question asking when is 3 a seventh power modulo a prime $p$ if $p=1(7)$. However, I tried to find just one example using mathematica but I went up to primes in the thousands and I still ...
5
votes
1answer
72 views

Proving without reciprocity laws that if $p>0$ a prime such $p=1(5)$ then 5 is a quadratic residue mod $p$.

I've done a similar problem where $p=1(3)$ and showed that $-3$ is a quadratic residue modulo $p$. These problems are sledgehammered by reciprocity laws, so I am trying to prove it directly using the ...
2
votes
2answers
162 views

Where did I go wrong on computing the legendre symbol $\left(\frac{150}{1009}\right)$

Where did I go wrong on computing the legendre symbol $\left(\frac{150}{1009}\right)$. I know the answer is $1$. For some reason every way I compute this legendre symbol I get $-1$: ...
1
vote
1answer
217 views

The meaning of the Jacobi Symbol and its efficient evaluation

Are the following jacobi symbol evaluations correct?: $(\frac{35}{53}) = -1$ $(\frac{68}{233}) = -1$ $(\frac{126}{509}) = 1$ $(\frac{672}{1297}) = 1$ $(\frac{1235}{3499}) = -1$ Also what is the ...
6
votes
1answer
359 views

Primes of the form $p=a^2-2b^2$.

I've stumbled upon this and I was wondering if anyone here could come up with a simple proof: Let $p$ be a prime such that $p\equiv 1 \bmod 8$, and let $a,b\geq 1$ such that $$p=a^2-2b^2.$$ ...
2
votes
1answer
166 views

bound of quadratic nonresidue modulo an odd prime

I heard that if $p$ is an odd prime, there is a quadratic nonresidue modulo $p$ less than $p^{1/2} +1$. How to show this statement?