An integer $a$ is a quadratic residue modulo $p$ if $a \equiv x^2 \pmod p$ for some integer $x$. If $a$ is not a quadratic residue modulo $p$, it is said to be a quadratic nonresidue modulo $p$.

1,058 questions
Filter by
Sorted by
Tagged with
18 views

Let Define: $$Q1=\{i^2\ mod\ p | 0\leq i<p\}$$ $$Q2=\{(-1)^i\cdot i^2\ mod\ p | 0\leq i<p\}$$ Let notice that for $p=47$ it can be shown that $|Q1|=24$ and $|Q2|=47$ but for other primary for ...
63 views

Number of Solutions of the Hyperbola Equations over Finite Fields

I have a problem with proving the number of points of the hyperbola equation $H_u: x^2 - y^2 = u$ (for every u > 0 in finite field $F_p$) in the finite fields. I have to prove that the number of ...
• 31
36 views

Problem regarding quadratic recidues that I cannot solve [duplicate]

The problem is as follows: Let $p$ be a prime and assume that $p=1$ mod 5. Let $c\in\left(\mathbb{Z}/p\mathbb{Z}\right)^{\times}$ be an element of order 5 and let $g=2(c+c^{-1})+1$ Show that $g^2=5$ ...
• 15
59 views

For every prime p there is a sum of squares congruent to -1 mod p [duplicate]

For every prime $p$, there exists $a,b \in \mathbb{Z}$ such that $p\mid a^2+b^2+1$ For context, this question shows up as a statement on a hint to showing that every positive integer is a sum of 4 ...
• 464
32 views

Find any or all Lipschitz quaternions corresponding to a given quaternion norm

In this answer, in response to the question "How to find $2+7𝑖$ from $53$?", user @Cocopuffs provided a reference to a Jacobsthal sum, which enables obtaining a Gaussian integer, based on a ...
• 19
1 vote
37 views

Sum of the Multiplicative Legendre's symbol

Let $p$ a be odd prime show that $\displaystyle\sum_{a=1}^{p-2}\left(\frac{a(a+1)}{p}\right)=-1$. Nota Bene : The $(\frac{a}{p})$ is $\textbf{Legendre Symbol}$
1 vote
25 views

• 1,770
39 views

• 19.5k
1 vote
43 views

• 181
65 views

How did we discover that this quadratic residue oriented PRNG generates unique numbers in a sequence?

Question (tl;dr) How do we know that even for extremely large numbers like even far past $32^{15}$ (any bigint, or any number really), that as you increment the sequence from $0$ to $n$, $n$ being the ...
• 3,166
63 views

How to find the amount of solutions of polynomial congruence?

The given congruence is $x^4-5x-6 ≡ 0$ mod $(100^{100})$. Find the amount of it’s solutions. I’ve factorised it: $(x+1)(x-2)(x^2+x+3) ≡ 0$ mod $(100^{100})$. From here I get solutions for the first ...
• 83
1 vote
26 views

• 405
67 views

Incongruent Solutions of a Quadratic congruence

I have been reading up on finding incongruent solutions of quadratic congruences and have stumbled upon an answer to a question asked here. The answer I am confused about is the following: "if ...
• 51
73 views

How to find squares mod $m$, i.e $x$ in $x^2 \equiv a \mod m$, without factoring $m$?

I have very large integers $m$, where ( $\log_2(m)> 630$), and I need to find square roots modulo m. I am aware of several theorems that allow me to find the roots $\mod m$ when m is a power of a ...
• 942
190 views

Number of quadratic congruences modulo $n$ having exactly $k$ solutions

Given integers $n$ and $k$, find the number of quadratic congruences of the form $$ax^2 + bx + c \equiv 0 \pmod{n}$$ having exactly $k$ solutions in $\mathbb{Z}_n$, where $a, b, c \in \mathbb{Z}_n$....
• 277
72 views

Determine the number of distinct solutions of $(x^2-1)(x^2+1)\equiv 0 \pmod {4\cdot31^3}$ [closed]

I want to determine the number of distinct solutions of $(x^2-1)(x^2+1)\equiv 0 \pmod{4\times 31^3}$,if I call LHS as $f(x)$,then $f(x)\equiv 0 \pmod{4}$ and $f(x)\equiv 0 \pmod{31^3}$.Now I do not ...
• 2,043
I'm trying to solve the equation $$E(x)=\frac{(1+ix)^{1/2}-(1-ix)^{1/2}}{(1+ix)^{1/2}+(1-ix)^{1/2}} \mod p,$$ where $p$ is a prime and $1+ix$ is a Gaussian integer over $p$. For some values of $x$, ...