Articles of quadratic residues

Solvability of $a \equiv x^2 \mod b$

Suppose you want to prove that $\exists x \in \mathbb{Z}$ with $a \equiv x^2 \mod b$. Write $b = \prod_{i = 1}^{k} p_i^{e_i}$, the prime factorisation of $b$. Why is the equivalent with finding solutions to $a \equiv x_i^2 \mod p_i$? How does one apply the Chinese Remainder Theorem here? Thanks in advance!

Quadratic Residue modulo $nm$

Let $m$ and $n$ be relatively prime and $b \in (\mathbb Z/ mn \mathbb Z)^\times$. Then $b$ is a quadratic residue modulo $mn$ if and only if $b$ is a quadratic residue modulo $m$ and modulo $n$. I am struggling with this proof. It seems like I should be able to do it but every […]

Quadratic reciprocity: Tell if $c$ got quadratic square root mod $p$

I am reading the wiki article about Quadratic reciprocity and I don’t understand how can I tell if some integer $c$ got quadratic root mod $p$? So far I am using brute search to find $y$ such that $x= c\mod p$ $y^2 \equiv x \bmod p$ for some $y \in \{0,1,\ldots,p\}$ How can I use […]

Deciding if a number is a square in $\Bbb Z/n\Bbb Z$

I am looking for a systematic way of deciding if a given number is a square in $\Bbb Z/n\Bbb Z$. E.g. is $89$ a square in $\Bbb Z/n\Bbb Z$ for $n\in \{25,33,49\}$? Brute-forcing it would take too long here. How else can we do this?

For which primes $p$ does $px^2-2y^2=1$ have a solution?

Let $p$ be an odd prime. If $px^2-2y^2=1$ is solvable, we can get Jacobi symbol $(\frac{-2}{p})=1$, so $p=8k+1,8k+3$. But when $k=12$, $p=97$, the Pell equation $97x^2-2y^2=1$ is unsolvable. I think this diophantine equation is unsolvable for many integers. But it satisfies the Jacobi symbol, so my question is for what prime $p$, the diophantine equation […]

Find all primes $p$ such that $14$ is a quadratic residue modulo $p$.

I want to find all primes $p$ for which $14$ is a quadratic residue modulo $p$. I referred to an example that was already posted for finding all odd primes $p$ for which $15$ is a quadratic residue modulo $p$, but I am getting stuck. This is what I have done: $$\left(\frac{14}{p}\right)=\left(\frac{7}{p}\right)\left(\frac{2}{p}\right)=(-1)^{(p-1)/2}\left(\frac{p}{7}\right)\left(\frac{p}{2}\right). $$ There are […]

Elementary proof for: If x is a quadratic residue mod p, then it is a quadratic residue mod p^k

In article solving quadratic congruences, it is shown how to use Hensel’s lemma to iteratively construct solutions to to $x^2 \equiv a \pmod{p^k}$ from the solutions to $x^2 \equiv a \pmod{p}$. The case where $p=2$ is treated separately. While the construction is elegant, it is a tad lengthy and its reliance on Hensel’s lemma makes […]

Prove that if $p$ is an odd prime that divides a number of the form $n^4 + 1$ then $p \equiv 1 \pmod{8}$

Problem Prove that if $p$ is an odd prime that divides a number of the form $n^4 + 1$ then $p \equiv 1 \pmod{8}$ My attempt was, Since $p$ divides $n^4 + 1 \implies n^4 + 1 \equiv 0 \pmod{p} \Leftrightarrow n^4 \equiv -1 \pmod{p}$. It follows that $(n^2)^2 \equiv -1 \pmod{p}$, which implies $-1$ […]

Finding all solutions of $x^{11}\equiv 1\bmod23,$

I am asked to find all solutions of 1) $$x^2\equiv 1\bmod23$$ and to find all solutions of 2) $$x^{11}\equiv 1\bmod23,$$ justifying my work. I think 1) is $1$ and $22$ since if $p$ is an odd prime then $1$ has two distinct square roots modulo $p$, namely $1$ and $p-1$. However I am having difficulty […]

Can every element of a finite field be written as a sum of two non-squares?

We know that any element of a finite field $\mathbb{F_{q}}$ ($q$ odd prime power) can be written as a sum of two squares – is the same true for non-squares? Can any element of a (sufficiently large) finite field be written as a sum of two non-squares? I know that the above is not true […]