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,055 questions
Filter by
Sorted by
Tagged with
28 views

### Quadratic Residue Modulo and Square Root [closed]

mod(56,101).sqrt() For some reason, this outputs 37, but when you manually solve it modulo first and square root after, it outputs 7.48. What could be behind this? ...
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 ...
1 vote
36 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
24 views

39 views

1 vote
43 views

64 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 ...
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 ...
1 vote
26 views

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 ...
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 ...
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$....
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 ...
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$, ...