# Congruences

The subject of congruences is a field of mathematics that covers the integers, their relationship to each other and also the effect of arithmetic operations on their relationship to each other.

Expressed mathematically:

${\displaystyle A\equiv B{\pmod {N}}}$

read as: A is congruent with B modulo N.

 ${\displaystyle A,B,N}$ are integers and ${\displaystyle N>1.}$

This means that:

• A modulo N equals B modulo N,
• the difference, A-B, is exactly divisible by N, or
• ${\displaystyle A-B=K\cdot N.}$

where p modulo N or p % N is the remainder when p is divided by N.

For example: ${\displaystyle 23\equiv 8{\pmod {5}}}$ because division ${\displaystyle {\frac {23-8}{5}}}$ is exact without remainder, or ${\displaystyle 5\mid (23-8).}$

Similarly, ${\displaystyle 39\not \equiv 29\,{\pmod {7}}}$ because division ${\displaystyle {\frac {39-29}{7}}}$ is not exact, or ${\displaystyle 7\nmid (39-29).}$

 If ${\displaystyle A\equiv B{\pmod {N}},}$ then: ${\displaystyle A+q\equiv B+q{\pmod {N}}.}$ Proof: ${\displaystyle A-B=K\cdot N}$, therefore ${\displaystyle A=B+K\cdot N.}$ ${\displaystyle (A+q)-(B+q)=B+K\cdot N+q-B-q=K\cdot N}$ which is exactly divisible by N.

 If ${\displaystyle A\equiv B{\pmod {N}},}$ and ${\displaystyle C\equiv D{\pmod {N}},}$ then: ${\displaystyle A+C\equiv B+D{\pmod {N}}.}$ Proof: ${\displaystyle A-B=K_{1}\cdot N}$, therefore ${\displaystyle A=B+K_{1}\cdot N}$ and ${\displaystyle C=D+K_{2}\cdot N}$ ${\displaystyle (A+C)-(B+D)}$ ${\displaystyle =B+K_{1}\cdot N+D+K_{2}\cdot N-B-D}$ ${\displaystyle =N(K_{1}+K_{2})}$ which is exactly divisible by N.

## Law of Common Congruence

 If ${\displaystyle A\equiv B{\pmod {N}}}$ and ${\displaystyle C\equiv B{\pmod {N}},}$ then: ${\displaystyle A\equiv C{\pmod {N}}.}$ Proof: ${\displaystyle A=B+K_{1}\cdot N}$ and ${\displaystyle C=B+K_{2}\cdot N.}$ ${\displaystyle A-C=B+K_{1}\cdot N-B-K_{2}\cdot N=(K_{1}-K_{2})N}$ which is exactly divisible by N.

## Law of Multiplication

### by a constant

 If ${\displaystyle A\equiv B{\pmod {N}}}$ then: ${\displaystyle A\cdot p\equiv B\cdot p{\pmod {N}}.}$ Proof: ${\displaystyle A\cdot p-B\cdot p=p(A-B)}$ which is exactly divisible by N.

### by another congruence

 If ${\displaystyle A\equiv B{\pmod {N}}}$ and ${\displaystyle C\equiv D{\pmod {N}},}$ then: ${\displaystyle A\cdot C\equiv B\cdot D{\pmod {N}}.}$ Proof: ${\displaystyle A=B+K_{1}\cdot N}$ and ${\displaystyle C=D+K_{2}\cdot N.}$ ${\displaystyle A\cdot C-B\cdot D}$ ${\displaystyle =(B+K_{1}\cdot N)(D+K_{2}\cdot N)-B\cdot D}$ ${\displaystyle =B\cdot D+B\cdot K_{2}\cdot N+K_{1}\cdot N\cdot D+K_{1}\cdot N\cdot K_{2}\cdot N-B\cdot D}$ ${\displaystyle =N(B\cdot K_{2}+K_{1}\cdot D+K_{1}\cdot K_{2}\cdot N)}$ which is exactly divisible by N.

## Law of squares

 If ${\displaystyle A\equiv B{\pmod {N}}}$ then: ${\displaystyle A^{2}\equiv B^{2}{\pmod {N}}.}$ Proof: ${\displaystyle A^{2}-B^{2}=(A+B)(A-B)}$ which is exactly divisible by N.

## Law of Division?

 A simple example shows that a "law of division" does not exist. ${\displaystyle 24\equiv 14{\pmod {10}}.}$ However ${\displaystyle {\frac {24}{2}}\not \equiv {\frac {14}{2}}{\pmod {10}}}$ Because ${\displaystyle 12-7=5}$ is not exactly divisible by ${\displaystyle 10}$

## Introduction

A quadratic congruence is a congruence that contains at least one exact square, for example:

${\displaystyle x^{2}\equiv y{\pmod {N}}}$ or ${\displaystyle x^{2}\equiv y^{2}{\pmod {N}}.}$

Initially, let us consider the congruence: ${\displaystyle x^{2}\equiv y{\pmod {N}}.}$

If ${\displaystyle y=x^{2}-N,}$ then:

${\displaystyle x^{2}\equiv y{\pmod {N}}.}$

Proof: ${\displaystyle x^{2}-y=x^{2}-(x^{2}-N)=N}$ which is exactly divisible by ${\displaystyle N.}$

Consider an example with real numbers.

Let ${\displaystyle N=257}$ and ${\displaystyle 26\geq x\geq 6.}$

N = 257
${\displaystyle x}$ ${\displaystyle x^{2}-N}$
6 -221
7 -208
8 -193
9 -176
10 -157
11 -136
12 -113
13 -88
14 -61
15 -32
16 -1
17 32
18 67
19 104
20 143
21 184
22 227
23 272
24 319
25 368
26 419

A cursory glance at the values of ${\displaystyle x^{2}-N}$ indicates that the value ${\displaystyle x^{2}-N}$ is never divisible by ${\displaystyle 5.}$

Proof: ${\displaystyle N\equiv 2{\pmod {5}}}$ therefore ${\displaystyle N-2=k5}$ or ${\displaystyle N=5k+2.}$

The table shows all possible values of ${\displaystyle x\ \%\ 5}$ and ${\displaystyle y\ \%\ 5:}$

${\displaystyle x}$ ${\displaystyle x^{2}}$ ${\displaystyle y=x^{2}-N}$
${\displaystyle 5p+0}$ ${\displaystyle 25p^{2}+\ \ 0p+\ \ 0}$ ${\displaystyle 25p^{2}+\ \ 0p+\ \ 0\ \ -\ \ (5k+2)\ \ =\ \ 25p^{2}+\ \ 0p\ \ -\ \ 5k-\ \ 2}$
${\displaystyle 5p+1}$ ${\displaystyle 25p^{2}+10p+\ \ 1}$ ${\displaystyle 25p^{2}+10p+\ \ 1\ \ -\ \ (5k+2)\ \ =\ \ 25p^{2}+10p\ \ -\ \ 5k-\ \ 1}$
${\displaystyle 5p+2}$ ${\displaystyle 25p^{2}+20p+\ \ 4}$ ${\displaystyle 25p^{2}+20p+\ \ 4\ \ -\ \ (5k+2)\ \ =\ \ 25p^{2}+20p\ \ -\ \ 5k+\ \ 2}$
${\displaystyle 5p+3}$ ${\displaystyle 25p^{2}+30p+\ \ 9}$ ${\displaystyle 25p^{2}+30p+\ \ 9\ \ -\ \ (5k+2)\ \ =\ \ 25p^{2}+30p\ \ -\ \ 5k+\ \ 7}$
${\displaystyle 5p+4}$ ${\displaystyle 25p^{2}+40p+16}$ ${\displaystyle 25p^{2}+40p+16\ \ -\ \ (5k+2)\ \ =\ \ 25p^{2}+40p\ \ -\ \ 5k+14}$

As you can see, the value ${\displaystyle y=x^{2}-N}$ is never exactly divisible by ${\displaystyle 5.}$

If you look closely, you will see also that it is never exactly divisible by ${\displaystyle 3}$ or ${\displaystyle 7.}$

However, you can see at least one value of ${\displaystyle y}$ exactly divisible by ${\displaystyle 11}$ and at least one value of ${\displaystyle y}$ exactly divisible by ${\displaystyle 13.}$

The table shows all possible values of ${\displaystyle x\ \%\ 11}$ and ${\displaystyle y\ \%\ 11:}$

${\displaystyle x}$ ${\displaystyle x^{2}}$ ${\displaystyle y=x^{2}-N}$
${\displaystyle 11p+\ \ 0}$ ${\displaystyle 121p^{2}+\ \ }$${\displaystyle \ \ 0p+\ \ }$${\displaystyle \ \ 0}$ ${\displaystyle 121p^{2}+\ \ }$${\displaystyle \ \ 0p-11k-\ \ 4\ \ =\ \ 121p^{2}+\ \ }$${\displaystyle \ \ 0p-11(k+1)+\ \ 7\ \ }$${\displaystyle \ \ }$
${\displaystyle 11p+\ \ 1}$ ${\displaystyle 121p^{2}+\ \ 22p+\ \ }$${\displaystyle \ \ 1}$ ${\displaystyle 121p^{2}+\ \ 22p-11k-\ \ 3\ \ =\ \ 121p^{2}+\ \ 22p-11(k+1)+\ \ 8\ \ }$${\displaystyle \ \ }$
${\displaystyle 11p+\ \ 2}$ ${\displaystyle 121p^{2}+\ \ 44p+\ \ }$${\displaystyle \ \ 4}$ ${\displaystyle 121p^{2}+\ \ 20p-11k+\ \ 0\ \ =\ \ 121p^{2}+\ \ 20p-11k+\ \ 0\ \ }$${\displaystyle \ \ }$${\displaystyle \ \ }$${\displaystyle \ \ }$${\displaystyle \ \ *}$
${\displaystyle 11p+\ \ 3}$ ${\displaystyle 121p^{2}+\ \ 66p+\ \ }$${\displaystyle \ \ 9}$ ${\displaystyle 121p^{2}+\ \ 66p-11k+\ \ 5\ \ =\ \ 121p^{2}+\ \ 66p-11k+\ \ 5\ \ }$${\displaystyle \ \ }$${\displaystyle \ \ }$${\displaystyle \ \ }$${\displaystyle \ \ }$${\displaystyle \ \ }$
${\displaystyle 11p+\ \ 4}$ ${\displaystyle 121p^{2}+\ \ 88p+\ \ 16}$ ${\displaystyle 121p^{2}+\ \ 88p-11k+12\ \ =\ \ 121p^{2}+\ \ 88p-11(k-1)+\ \ 1\ \ }$${\displaystyle \ \ }$
${\displaystyle 11p+\ \ 5}$ ${\displaystyle 121p^{2}+110p+\ \ 25}$ ${\displaystyle 121p^{2}+110p-11k+21\ \ =\ \ 121p^{2}+110p-11(k-1)+10\ \ }$${\displaystyle \ \ }$
${\displaystyle 11p+\ \ 6}$ ${\displaystyle 121p^{2}+132p+\ \ 36}$ ${\displaystyle 121p^{2}+132p-11k+32\ \ =\ \ 121p^{2}+132p-11(k-2)+10\ \ }$${\displaystyle \ \ }$
${\displaystyle 11p+\ \ 7}$ ${\displaystyle 121p^{2}+154p+\ \ 49}$ ${\displaystyle 121p^{2}+154p-11k+45\ \ =\ \ 121p^{2}+154p-11(k-4)+\ \ 1\ \ }$${\displaystyle \ \ }$
${\displaystyle 11p+\ \ 8}$ ${\displaystyle 121p^{2}+176p+\ \ 64}$ ${\displaystyle 121p^{2}+176p-11k+60\ \ =\ \ 121p^{2}+176p-11(k-5)+\ \ 5\ \ }$${\displaystyle \ \ }$
${\displaystyle 11p+\ \ 9}$ ${\displaystyle 121p^{2}+198p+\ \ 81}$ ${\displaystyle 121p^{2}+198p-11k+77\ \ =\ \ 121p^{2}+198p-11(k-7)+\ \ 0\ \ *}$
${\displaystyle 11p+10}$ ${\displaystyle 121p^{2}+220p+100}$ ${\displaystyle 121p^{2}+220p-11k+96\ \ =\ \ 121p^{2}+220p-11(k-8)+\ \ 8\ \ }$${\displaystyle \ \ }$

The two lines marked by an ${\displaystyle *}$ show values of ${\displaystyle y}$ exactly divisible by ${\displaystyle 11.}$ The two values of ${\displaystyle x,}$ ${\displaystyle 11p+2}$ and ${\displaystyle 11p+9,}$ or ${\displaystyle 11p\pm 2}$ are solutions of the congruence.

Why are values of ${\displaystyle y}$ divisible by some primes and not divisible by other primes? An interesting question that leads us to the topic of quadratic residues.

Consider all the congruences for prime number ${\displaystyle 5:}$

${\displaystyle x^{2}\equiv y{\pmod {5}}}$ for ${\displaystyle 5>x\geq 0.}$

${\displaystyle x}$ ${\displaystyle x^{2}}$ ${\displaystyle (x^{2})\ \%\ 5}$
0 0 0
1 1 1
2 4 4
3 9 4
4 16 1

Quadratic residues of ${\displaystyle 5}$ are ${\displaystyle 0,1,4.}$

Values ${\displaystyle 2,3}$ are not quadratic residues of ${\displaystyle 5.}$ These values are quadratic non-residues.

To calculate the quadratic residues of a small prime ${\displaystyle p:}$

# python code:
L1 = []
for	v in range (p>>1, -1, -1) :
L1 += [(v*v) % p]
return L1

[3, 5, 9, 4, 1, 0]

Quadratic residues of ${\displaystyle 11}$ are ${\displaystyle 0,1,3,4,5,9.}$

The method presented here answers the question, "What are the quadratic residues of p?"

If ${\displaystyle p}$ is a very large prime, the question is often, "Is r a quadratic residue of p?" The answer is found in advanced number theory.

Let us return to quadratic residues mod ${\displaystyle N=257.}$

${\displaystyle N\ \%\ 5=2,}$ therefore ${\displaystyle N}$ is not a quadratic residue of ${\displaystyle 5.}$ This is why ${\displaystyle x^{2}-N}$ is never divisible by ${\displaystyle 5}$ exactly.

${\displaystyle N\ \%\ 11=4,}$ therefore ${\displaystyle N}$ is a quadratic residue of ${\displaystyle 11}$ and a value of ${\displaystyle x}$ that satisfies the congruence ${\displaystyle x^{2}\equiv 4{\pmod {257}}}$ has form ${\displaystyle 11p\pm 2.}$

From the table above:

N = 257
${\displaystyle x}$ ${\displaystyle x^{2}\ -\ N}$
9 -176
13 -88
20 143
24 319

These ${\displaystyle 4}$ values of ${\displaystyle x^{2}-N}$ are exactly divisible by ${\displaystyle 11.}$

${\displaystyle x=9}$ is ${\displaystyle 11\cdot 1-2.}$

${\displaystyle x=13}$ is ${\displaystyle 11\cdot 1+2.}$

${\displaystyle x=20}$ is ${\displaystyle 11\cdot 2-2.}$

${\displaystyle x=24}$ is ${\displaystyle 11\cdot 2+2.}$

### Products

This section uses prime number ${\displaystyle 41}$ as an example.

Using quadResidues(p) quadratic residues of ${\displaystyle 41}$ are:

qr41 = [0, 1, 2, 4, 5, 8, 9, 10, 16, 18, 20, 21, 23, 25, 31, 32, 33, 36, 37, 39, 40]

Quadratic non-residues of ${\displaystyle 41}$ are:

qnr41 = [3, 6, 7, 11, 12, 13, 14, 15, 17, 19, 22, 24, 26, 27, 28, 29, 30, 34, 35, 38]

#### of 2 residues

A simple test to verify that the product of 2 residues is a residue:

# Python code.
for index1 in range (0, len(qr41)) :
v1 = qr41[index1]
for index2 in range (index1, len(qr41)) :
v2 = qr41[index2]
residue = (v1*v2) % 41
if residue not in qr41 : print ('residue',residue,'not quadratic.')

This test shows that, at least for prime number ${\displaystyle 41,}$ the product of 2 residues is a residue. Advanced math proves that this is true for all primes.

#### of 2 non-residues

A simple test to verify that the product of 2 non-residues is a residue:

# Python code.
for index1 in range (0, len(qnr41)) :
v1 = qnr41[index1]
for index2 in range (index1, len(qnr41)) :
v2 = qnr41[index2]
residue = (v1*v2) % 41
if residue not in qr41 : print ('residue',residue,'not quadratic.')

This test shows that, at least for prime number ${\displaystyle 41,}$ the product of 2 non-residues is a residue. Advanced math proves that this is true for all primes.

#### of residue and non-residue

A simple test to verify that the product of residue and non-residue is non-residue:

# Python code.
for index1 in range (1, len(qr41)) :
v1 = qr41[index1]
for index2 in range (0, len(qnr41)) :
v2 = qnr41[index2]
residue = (v1*v2) % 41
if residue not in qnr41 : print ('residue',residue,'quadratic.')

This test shows that, at least for prime number ${\displaystyle 41,}$ the product of residue and non-residue is non-residue. Advanced math proves that this is true for all primes.

 Some authors may consider ${\displaystyle 0}$ as not a legitimate residue. ${\displaystyle 0}$ is not included as a residue in the test above.

## Euler's criterion

In number theory, Euler's criterion is a formula for determining whether or not an integer is a quadratic residue modulo a prime number. Precisely,

Let p be an odd prime and a be an integer coprime to p. Then

${\displaystyle a^{\tfrac {p-1}{2}}\equiv {\begin{cases}\;\;\,1{\pmod {p}}&{\text{ if there is an integer }}x{\text{ such that }}a\equiv x^{2}{\pmod {p}},\\-1{\pmod {p}}&{\text{ if there is no such integer.}}\end{cases}}}$

Euler's criterion can be concisely reformulated using the Legendre symbol:

${\displaystyle \left({\frac {a}{p}}\right)\equiv a^{\tfrac {p-1}{2}}{\pmod {p}}.}$
${\displaystyle \left({\frac {a}{p}}\right)={\begin{cases}1&{\text{if }}a{\text{ is a quadratic residue modulo }}p{\text{ and }}a\not \equiv 0{\pmod {p}},\\-1&{\text{if }}a{\text{ is a non-quadratic residue modulo }}p,\\0&{\text{if }}a\equiv 0{\pmod {p}}.\end{cases}}}$

It is known that ${\displaystyle 3}$ is a quadratic residue modulo ${\displaystyle 11.}$

Therefore ${\displaystyle (3^{5})\ \%\ 11}$ should be ${\displaystyle 1.}$

# python code:
>>> (3**5) % 11
1

It is known that ${\displaystyle 7}$ is a quadratic non-residue modulo ${\displaystyle 11.}$

Therefore ${\displaystyle (7^{5})\ \%\ 11}$ should be ${\displaystyle -1.}$

# python code:
>>> (7**5) % 11
10
${\displaystyle 10\equiv -1{\pmod {11}}}$

Python's decimal module provides a method for computing ${\displaystyle (a^{x})\ \%\ p}$ very efficiently for both small and very large numbers.

# python code:
>>> import decimal
>>> decimal.Context().power(3,5,11)
Decimal('1')
>>> decimal.Context().power(7,5,11)
Decimal('10')
>>>
>>> a = 3456789
>>> p = 761838257287
>>> decimal.Context().power(a, p>>1, p)
Decimal('761838257286')
${\displaystyle 761838257286\equiv -1{\pmod {761838257287}}}$

Value ${\displaystyle a=3456789}$ is not a quadratic residue modulo ${\displaystyle p=761838257287.}$

 An exact square such as ${\displaystyle 1,4,9,16,25,\dots }$ is always a quadratic residue modulo an odd prime ${\displaystyle p.}$

### Product of 2 residues

Let ${\displaystyle a,b}$ be quadratic residues modulo odd prime ${\displaystyle p.}$

Let ${\displaystyle q={\frac {p-1}{2}}.}$

Then:

${\displaystyle a^{q}\equiv 1{\pmod {p}}}$

${\displaystyle b^{q}\equiv 1{\pmod {p}}}$

By law of multiplication:

${\displaystyle (a^{q})(b^{q})\equiv (1)(1){\pmod {p}}}$ or

${\displaystyle (a\cdot b)^{q}\equiv 1{\pmod {p}}}$

Product ${\displaystyle (a\cdot b)}$ of 2 quadratic residues ${\displaystyle a,b}$ is quadratic residue.

Similarly, product of 2 non-residues is residue, and product of residue and non-residue is non-residue.

## Factors of integer N

Several modern methods for determining the factors of a given integer attempt to create two congruent squares modulo integer ${\displaystyle N.}$

${\displaystyle x^{2}\equiv y^{2}{\pmod {N}}}$

This means that the difference between the two squares is exactly divisible by ${\displaystyle N}$: ${\displaystyle N\mid (x^{2}-y^{2}).}$

Integer ${\displaystyle N}$ always contains the factors ${\displaystyle N,1,}$ called trivial factors.

If ${\displaystyle N}$ contains two non-trivial factors ${\displaystyle p,q,}$ then:

${\displaystyle {\frac {(x+y)(x-y)}{p\cdot q}}.}$

With a little luck ${\displaystyle p\mid (x+y)}$ and ${\displaystyle q\mid (x-y)}$ in which case:

${\displaystyle p={\text{igcd}}(x+y,N)}$ and ${\displaystyle q={\text{igcd}}(x-y,N)}$ where

"${\displaystyle {\text{igcd}}}$" is function "${\displaystyle {\text{integer greatest common divisor.}}}$"

### A simple example:

We will use quadratic congruences to calculate factors of ${\displaystyle N=4171}$ for ${\displaystyle 164\geq x\geq 1.}$

#### Right hand side exact square

One congruence produced an exact square for y:

${\displaystyle x}$ ${\displaystyle x^{2}}$ ${\displaystyle y=x^{2}-N}$
70 4900 729
${\displaystyle 4900\equiv 729{\pmod {N}}}$
${\displaystyle 70^{2}\equiv 27^{2}{\pmod {N}}}$

${\displaystyle p={\text{igcd}}(70-27,4171)}$ ${\displaystyle ={\text{igcd}}(43,4171)}$ ${\displaystyle =43.}$

${\displaystyle q={\text{igcd}}(70+27,4171)}$ ${\displaystyle ={\text{igcd}}(97,4171)}$ ${\displaystyle =97.}$

Non-trivial factors of ${\displaystyle 4171}$ are ${\displaystyle 43,97.}$

#### Right hand side negative

Table below contains a sample of values of ${\displaystyle x}$ that produce negative ${\displaystyle y:}$

${\displaystyle x}$ ${\displaystyle x^{2}}$ ${\displaystyle y=x^{2}-N}$
${\displaystyle \ \ }$7 ${\displaystyle \ \ \ \ }$49 -4122${\displaystyle \ \ \ \ \ \ }$
${\displaystyle \ \ }$8 ${\displaystyle \ \ \ \ }$64 -4107${\displaystyle \ \ }$**
${\displaystyle \ \ }$9 ${\displaystyle \ \ \ \ }$81 -4090${\displaystyle \ \ \ \ \ \ }$
10 ${\displaystyle \ \ }$100 -4071${\displaystyle \ \ \ \ \ \ }$
11 ${\displaystyle \ \ }$121 -4050${\displaystyle \ \ }$!!
12 ${\displaystyle \ \ }$144 -4027${\displaystyle \ \ \ \ \ \ }$
60 3600 ${\displaystyle \ \ }$-571${\displaystyle \ \ \ \ \ \ }$
61 3721 ${\displaystyle \ \ }$-450${\displaystyle \ \ }$!!
62 3844 ${\displaystyle \ \ }$-327${\displaystyle \ \ \ \ \ \ }$
63 3969 ${\displaystyle \ \ }$-220${\displaystyle \ \ \ \ \ \ }$
64 4096 ${\displaystyle \ \ \ \ }$-75${\displaystyle \ \ }$**
##### Non-trivial result 1

The congruences:

${\displaystyle x}$ ${\displaystyle x^{2}}$ ${\displaystyle y=x^{2}-N}$
${\displaystyle \ \ }$8 ${\displaystyle \ \ \ \ }$64 -4107${\displaystyle \ \ }$**
64 4096 ${\displaystyle \ \ \ \ }$-75${\displaystyle \ \ }$**
${\displaystyle 64\equiv -4107{\pmod {N}}}$
${\displaystyle 4096\equiv -75{\pmod {N}}}$
${\displaystyle 64\cdot 4096\equiv -4107\cdot (-75){\pmod {N}}}$
${\displaystyle 262144\equiv 308025{\pmod {N}}}$
${\displaystyle 512^{2}\equiv 555^{2}{\pmod {4171}}}$

${\displaystyle p={\text{igcd}}(555-512,4171)}$ ${\displaystyle ={\text{igcd}}(43,4171)}$ ${\displaystyle =43.}$

${\displaystyle q={\text{igcd}}(555+512,4171)}$ ${\displaystyle ={\text{igcd}}(1067,4171)}$ ${\displaystyle =97.}$

Non-trivial factors of ${\displaystyle 4171}$ are ${\displaystyle 43,97.}$

##### Non-trivial result 2

The congruences:

${\displaystyle x}$ ${\displaystyle x^{2}}$ ${\displaystyle y=x^{2}-N}$
11 121 -4050!!
61 3721 -450!!
${\displaystyle 121\equiv -4050{\pmod {N}}}$
${\displaystyle 3721\equiv -450{\pmod {N}}}$
${\displaystyle 121\cdot 3721\equiv -4050\cdot (-450){\pmod {N}}}$
${\displaystyle 450241\equiv 1822500{\pmod {N}}}$
${\displaystyle 671^{2}\equiv 1350^{2}{\pmod {4171}}}$

${\displaystyle p={\text{igcd}}(1350-671,4171)}$ ${\displaystyle ={\text{igcd}}(679,4171)}$ ${\displaystyle =97.}$

${\displaystyle q={\text{igcd}}(1350+671,4171)}$ ${\displaystyle ={\text{igcd}}(2021,4171)}$ ${\displaystyle =43.}$

Non-trivial factors of ${\displaystyle 4171}$ are ${\displaystyle 43,97.}$

#### Right hand side positive

Table below contains a sample of values of ${\displaystyle x}$ that produce positive ${\displaystyle y:}$

${\displaystyle x}$ ${\displaystyle x^{2}}$ ${\displaystyle y=x^{2}-N}$
${\displaystyle \ \ }$65 ${\displaystyle \ \ }$4225 ${\displaystyle \ \ \ \ \ \ }$54${\displaystyle \ \ }$**${\displaystyle \ \ \ \ }$
${\displaystyle \ \ }$66 ${\displaystyle \ \ }$4356 ${\displaystyle \ \ \ \ }$185${\displaystyle \ \ \ \ \ \ \ \ \ \ }$
${\displaystyle \ \ }$88 ${\displaystyle \ \ }$7744 ${\displaystyle \ \ }$3573${\displaystyle \ \ \ \ \ \ \ \ \ \ }$
${\displaystyle \ \ }$89 ${\displaystyle \ \ }$7921 ${\displaystyle \ \ }$3750${\displaystyle \ \ }$**!!
${\displaystyle \ \ }$90 ${\displaystyle \ \ }$8100 ${\displaystyle \ \ }$3929${\displaystyle \ \ \ \ \ \ \ \ \ \ }$
144 20736 16565${\displaystyle \ \ \ \ \ \ \ \ \ \ }$
145 21025 16854${\displaystyle \ \ \ \ \ \ }$!!
146 21316 17145${\displaystyle \ \ \ \ \ \ \ \ \ \ }$
##### Non-trivial result

The congruences:

${\displaystyle x}$ ${\displaystyle x^{2}}$ ${\displaystyle y=x^{2}-N}$
65 4225 ${\displaystyle \ \ \ \ }$54${\displaystyle \ \ }$**${\displaystyle \ \ \ \ }$
89 7921 3750${\displaystyle \ \ }$**!!
${\displaystyle 4225\equiv 54{\pmod {N}}}$
${\displaystyle 7921\equiv 3750{\pmod {N}}}$
${\displaystyle 4225\cdot 7921\equiv 54\cdot 3750{\pmod {N}}}$
${\displaystyle 33466225\equiv 202500{\pmod {N}}}$
${\displaystyle 5785^{2}\equiv 450^{2}{\pmod {4171}}}$

${\displaystyle p={\text{igcd}}(5785-450,4171)}$ ${\displaystyle ={\text{igcd}}(5335,4171)}$ ${\displaystyle =97.}$

${\displaystyle q={\text{igcd}}(5785+450,4171)}$ ${\displaystyle ={\text{igcd}}(6235,4171)}$ ${\displaystyle =43.}$

Non-trivial factors of ${\displaystyle 4171}$ are ${\displaystyle 43,97.}$

##### Trivial result

The congruences:

${\displaystyle x}$ ${\displaystyle x^{2}}$ ${\displaystyle y=x^{2}-N}$
${\displaystyle \ \ }$89 ${\displaystyle \ \ }$7921 ${\displaystyle \ \ }$3750${\displaystyle \ \ }$**!!
145 21025 16854${\displaystyle \ \ \ \ \ \ }$!!
${\displaystyle 7921\equiv 3750{\pmod {N}}}$
${\displaystyle 21025\equiv 16854{\pmod {N}}}$
${\displaystyle 7921\cdot 21025\equiv 3750\cdot 16854{\pmod {N}}}$
${\displaystyle 166539025\equiv 63202500{\pmod {N}}}$
${\displaystyle 12905^{2}\equiv 7950^{2}{\pmod {4171}}}$

${\displaystyle p={\text{igcd}}(12905-7950,4171)}$ ${\displaystyle ={\text{igcd}}(4955,4171)}$ ${\displaystyle =1.}$

${\displaystyle q={\text{igcd}}(12905+7950,4171)}$ ${\displaystyle ={\text{igcd}}(20855,4171)}$ ${\displaystyle =4171.}$

This congruence produced the trivial factors of ${\displaystyle 4171.}$

#### With 3 congruences

The congruences:

${\displaystyle x}$ ${\displaystyle x^{2}}$ ${\displaystyle y=x^{2}-N}$
${\displaystyle \ \ }$56 ${\displaystyle \ \ }$3136 -1035
${\displaystyle \ \ }$59 ${\displaystyle \ \ }$3481 ${\displaystyle \ \ }$-690
145 21025 16854
${\displaystyle 3136\equiv -1035{\pmod {N}}}$
${\displaystyle 3481\equiv -690{\pmod {N}}}$
${\displaystyle 21025\equiv 16854{\pmod {N}}}$
${\displaystyle 3136\cdot 3481\cdot 21025\equiv -1035\cdot -690\cdot 16854{\pmod {N}}}$
${\displaystyle 229517646400\equiv 12036284100{\pmod {N}}}$
${\displaystyle 479080^{2}\equiv 109710^{2}{\pmod {4171}}}$

${\displaystyle p={\text{igcd}}(479080-109710,4171)}$ ${\displaystyle =43.}$

${\displaystyle q={\text{igcd}}(479080+109710,4171)}$ ${\displaystyle =97.}$

Non-trivial factors of ${\displaystyle 4171}$ are ${\displaystyle 43,97.}$