# 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.

 Programming language python, for example, accepts the following modular arithmetic: >>> 14%(1) 0 >>> 14%(-3) -1  On this page we'll say that ${\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}$

If division of operators is performed carefully, division can be very useful.

### Factor common to (A, B)

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

If ${\displaystyle A,B}$ share a common factor ${\displaystyle p}$ then:

${\displaystyle p\cdot a\equiv p\cdot b{\pmod {N}}.}$

Provided that factor ${\displaystyle p}$ does not divide ${\displaystyle N,}$ then:

${\displaystyle a\equiv b{\pmod {N}}.}$

Proof: division ${\displaystyle {\frac {p\cdot a-p\cdot b}{N}}={\frac {p(a-b)}{N}}}$ is exact.

Factor ${\displaystyle p}$ does not divide ${\displaystyle N,}$ therefore division ${\displaystyle {\frac {a-b}{N}}}$ must be exact.

For example : ${\displaystyle 42\equiv 207{\pmod {55}}}$

${\displaystyle 3\cdot 14\equiv 3\cdot 69{\pmod {55}}}$

${\displaystyle 14\equiv 69{\pmod {55}}}$

### Factor common to (A, B, N)

If operands ${\displaystyle A,B,N}$ all share a common factor ${\displaystyle p}$ then:

${\displaystyle p\cdot a\equiv p\cdot b{\pmod {(p\cdot n)}}}$ in which case:

${\displaystyle a\equiv b{\pmod {n}}.}$

Proof: division ${\displaystyle {\frac {p(a-b)}{p\cdot n}}}$ is exact.

Therefore, division ${\displaystyle {\frac {a-b}{n}}}$ must be exact.

For example: ${\displaystyle 22\equiv 77{\pmod {55}}.}$

Therefore: ${\displaystyle 2\equiv 7{\pmod {5}}.}$

# Linear congruences

A linear congruence is similar to a linear equation, except that it is expressed in modular format:

${\displaystyle A\cdot x\equiv B{\pmod {N}}}$ where ${\displaystyle A,B,N}$ are integers and ${\displaystyle N>1.}$

If ${\displaystyle A\cdot x\equiv B{\pmod {N}},}$ then ${\displaystyle A\cdot x+C\equiv B+C{\pmod {N}}}$

Proof is similar to that offered above.

 Note that the congruence ${\displaystyle (A+C)\cdot x\equiv B+C{\pmod {N}}}$ is not valid, except for ${\displaystyle C=p\cdot N.}$ Generally: ${\displaystyle (A+p\cdot N)\cdot (x+q\cdot N)\equiv (B+r\cdot N){\pmod {N}}.}$ Proof: ${\displaystyle (A+p\cdot N)\cdot (x+q\cdot N)-(B+r\cdot N)}$ ${\displaystyle =A\cdot x+A\cdot q\cdot N+p\cdot N\cdot x+p\cdot N\cdot q\cdot N-B-r\cdot N}$ ${\displaystyle =A\cdot x-B+N\cdot (A\cdot q+p\cdot x+p\cdot N\cdot q-r)}$ which is exactly divisible by ${\displaystyle N.}$ A corollary of this proof is: ${\displaystyle (A\%N)\cdot (x\%N)\equiv (B\%N){\pmod {N}}.}$

## Law of multiplication

If ${\displaystyle A\cdot x\equiv B{\pmod {N}},}$ then ${\displaystyle C\cdot A\cdot x\equiv C\cdot B{\pmod {N}},}$

Proof: ${\displaystyle C\cdot A\cdot x-C\cdot B}$

${\displaystyle =C\cdot (A\cdot x-B)}$ which is exactly divisible by ${\displaystyle N.}$

## Simplify the congruence

Simplifying the congruence means reducing the value of ${\displaystyle A}$ as much as possible.

For example: ${\displaystyle 30121\cdot x\equiv 30394{\pmod {35893}}}$

>>> [ v%13 for v in (30121,  30394, 35893) ]
[0, 0, 0]

Three values share a common prime factor ${\displaystyle 13.}$

Therefore: ${\displaystyle {\frac {30121}{13}}\cdot x\equiv {\frac {30394}{13}}{\pmod {\frac {35893}{13}}}}$

>>> [ int(v/13) for v in (30121,  30394, 35893) ]
[2317, 2338, 2761]

${\displaystyle 2317\cdot x\equiv 2338{\pmod {2761}}}$

>>> [ v%7 for v in (2317, 2338, 2761)]
[0, 0, 3]

Two values share a common prime factor ${\displaystyle 7.}$

Therefore: ${\displaystyle {\frac {2317}{7}}\cdot x\equiv {\frac {2338}{7}}{\pmod {2761}}}$

>>> [ int(v/7) for v in (2317, 2338)]
[331, 334]

${\displaystyle 331\cdot x\equiv 334{\pmod {2761}}}$

>>> x
64530
>>> (30121*x - 30394) % 35893
0
>>> (331*x - 334) % 2761
0
 Linear congruence ${\displaystyle 30121\cdot x\equiv 30394{\pmod {35893}}}$ has been reduced to ${\displaystyle 331\cdot x\equiv 334{\pmod {2761}}.}$

### Python code

# python code.
def simplifyLinearCongruence (a,b,N, debug=0) :
'''
result = simplifyLinearCongruence (a,b,N, debug) :
result may be:
None
tuple p,q,n

For example:
6x /// 28 mod 31
3x /// 14 mod 31

The following is better:
6x /// 28 mod 31
6x /// -(-28) mod 31
6x /// -(3)   mod 31
2x /// -(1)   mod 31
2x ///   30   mod 31
x ///   15   mod 31

Another example:
23x ///     28 mod 31
-(-23)x /// -(-28) mod 31
-(8)x ///   -(3) mod 31
8x ///      3 mod 31  # multiply by -1.
8x ///  -(-3) mod 31
8x ///  -(28) mod 31
2x ///   -(7) mod 31  # divide by 4
2x ///     24 mod 31
x ///     12 mod 31  # divide by 2
'''

localLevel = (debug & 0xF00) >> 8
# This function is recursive.
# localLevel is depth of recursion.
debug_ = (debug & 0xF0) >> 4
if debug_ & 0b1000 : debug_ |= 0b100
if debug_ & 0b100  : debug_ |= 0b10
if debug_ & 0b10   : debug_ |= 0b1
# if debug_ == 0 : Print nothing.
# if debug_  & 1 : Print important info.
# if debug_  & 2 : Print less important info.
# if debug_  & 4 : Print less important info.
# if debug_  & 8 : Print everything.

thisName = 'simplifyLinearCongruence(), (localLevel=' + str(localLevel) + '):'

if debug_ & 0b10 : print (thisName, 'a,b,N =',a,b,N)

a,b = a%N, b%N
if a == 0:
if debug_ & 1 : print (thisName, 'a%N must be non-zero.')
return None
if a == 1 : return a,b,N
if a > (N >> 1) :
a,b = N-a, N-b
if debug_ & 0b10 : print (thisName, 'a,b,N =',a,b,N)
if a == 1 : return a,b,N

gcd1 = iGCD(N,a)
if gcd1 == 1 :
gcd2 = iGCD(a,b)
gcd3 = iGCD(a,N-b)
if (gcd2 > gcd3) :
if debug_ & 0b100 : print (thisName, 'gcd2 =',gcd2)
a,b = [ divmod(v,gcd2)[0] for v in (a,b) ]
return a,b,N
if (gcd3 == 1) : return a,b,N
if debug_ & 0b100 : print (thisName, 'gcd3 =',gcd3)
# ax /// b mod N
# ax /// -(-b) mod N
# ax /// -(N-b) mod N
# gcd3 = iGCD(a,N-b)
# a_*x /// -(b_) mod N
# a_*x /// N-b_ mod N
a_,b_ = [ divmod(v,gcd3)[0] for v in (a,N-b) ]
b_ = N - b_
return simplifyLinearCongruence(a_,b_,N,debug+0x100)
if debug_ & 0b100 : print (thisName, 'gcd1 =',gcd1)
if b % gcd1 :
if debug_ & 0b1 : print (thisName, 'No solution for',a,b,N)
return None
p,q,n = [ divmod(v,gcd1)[0] for v in (a,b,N) ]
return simplifyLinearCongruence(p,q,n,debug+0x100)

 result = simplifyLinearCongruence (23, 28, 31, 0b1000<<4) print ('result =',result)  simplifyLinearCongruence(), (localLevel=0): a,b,N = 23 28 31 simplifyLinearCongruence(), (localLevel=0): a,b,N = 8 3 31 simplifyLinearCongruence(), (localLevel=0): gcd3 = 4 simplifyLinearCongruence(), (localLevel=1): a,b,N = 2 24 31 simplifyLinearCongruence(), (localLevel=1): gcd2 = 2 result = (1, 12, 31)
 result = simplifyLinearCongruence (505563, 509218, 610181, 0b1000<<4) print ('result =',result)  simplifyLinearCongruence(), (localLevel=0): a,b,N = 505563 509218 610181 simplifyLinearCongruence(), (localLevel=0): a,b,N = 104618 100963 610181 simplifyLinearCongruence(), (localLevel=0): gcd1 = 17 simplifyLinearCongruence(), (localLevel=1): a,b,N = 6154 5939 35893 simplifyLinearCongruence(), (localLevel=1): gcd3 = 34 simplifyLinearCongruence(), (localLevel=2): a,b,N = 181 35012 35893 result = (181, 35012, 35893)

## Solve the congruence

Solution of congruence is a value of ${\displaystyle x}$ that satisfies the congruence.

Solving the linear congruence means continuously simplifying the congruence by reducing the value of ${\displaystyle A}$ until ${\displaystyle A}$ becomes ${\displaystyle 1}$ at which point the congruence is solved.

### Example 1

For example: ${\displaystyle 1327\cdot x\equiv -4539{\pmod {29}}}$ becomes in turn:

${\displaystyle 22\cdot x\equiv 14{\pmod {29}}}$

${\displaystyle 11\cdot x\equiv 7{\pmod {29}}}$

${\displaystyle 33\cdot x\equiv 21{\pmod {29}}}$

${\displaystyle 4\cdot x\equiv 21{\pmod {29}}}$

${\displaystyle 28\cdot x\equiv 147{\pmod {29}}}$

${\displaystyle -1\cdot x\equiv 147{\pmod {29}}}$

${\displaystyle 1\cdot x\equiv -147{\pmod {29}}}$

${\displaystyle 1\cdot x\equiv 27{\pmod {29}}}$

Yes: ${\displaystyle (1327*27-(-4539))\ \%\ 29=0.}$

### Example 2

For example, solve ${\displaystyle 439\cdot x\equiv 2157{\pmod {2693}}}$

${\displaystyle {\text{quotient, remainder = divmod(2693, 439)}}}$

${\displaystyle {\text{quotient, remainder = 6, 59}}}$

${\displaystyle {\text{remainder}}\ <=\ (439\ >>\ 1),}$ therefore:

${\displaystyle {\text{A = remainder = 59}}}$

${\displaystyle {\text{B}}=(-{\text{B}}*{\text{quotient}})\%{\text{N}}=523}$

${\displaystyle 59\cdot x\equiv 523{\pmod {2693}}}$

${\displaystyle {\text{quotient, remainder = divmod(2693, 59)}}}$

${\displaystyle {\text{quotient, remainder = 45, 38}}}$

${\displaystyle {\text{remainder}}>(59>>1),}$ therefore:

${\displaystyle {\text{A}}={\text{A}}-{\text{remainder}}=21}$

${\displaystyle {\text{B}}=({\text{B}}*({\text{quotient}}+1))\%{\text{N}}=2514}$

 ${\displaystyle {\text{New value of}}\ A}$ is always ${\displaystyle <=\ {\frac {{\text{Old value of}}\ A}{2}}.}$

${\displaystyle 21\cdot x\equiv 2514{\pmod {2693}}}$

${\displaystyle 7\cdot x\equiv 838{\pmod {2693}}}$

${\displaystyle {\text{quotient, remainder = divmod(2693, 7)}}}$

${\displaystyle {\text{quotient, remainder = 384, 5}}}$

${\displaystyle {\text{remainder}}>(7>>1),}$ therefore:

${\displaystyle {\text{A}}={\text{A}}-{\text{remainder}}=2}$

${\displaystyle {\text{B}}=({\text{B}}*({\text{quotient}}+1))\%{\text{N}}=2163}$

${\displaystyle 2\cdot x\equiv 2163{\pmod {2693}}}$

${\displaystyle {\text{quotient, remainder = divmod(2693, 2)}}}$

${\displaystyle {\text{quotient, remainder = 1346, 1}}}$

${\displaystyle {\text{remainder}}\ <=\ (2\ >>\ 1),}$ therefore:

${\displaystyle {\text{A = remainder = 1}}}$

${\displaystyle {\text{B}}=(-{\text{B}}*{\text{quotient}})\%{\text{N}}=2428}$

${\displaystyle 1\cdot x\equiv 2428{\pmod {2693}}}$

### Example 3

Method described here is algorithm used in python code below.

For example, solve the linear congruence:

${\displaystyle 113\cdot x\equiv 263{\pmod {311}}\ \dots \ (1).}$

${\displaystyle 113\cdot x=263+311\cdot p\ \dots \ (2)}$

${\displaystyle 311\cdot p-(-263)=113\cdot x}$

${\displaystyle 311\cdot p\equiv -263{\pmod {113}}}$

${\displaystyle 85\cdot p\equiv 76{\pmod {113}}}$

${\displaystyle (113-85)\cdot p\equiv (113-76){\pmod {113}}}$

${\displaystyle 28\cdot p\equiv 37{\pmod {113}}}$

${\displaystyle 28\cdot p=37+113\cdot q\ \dots \ (3)}$

${\displaystyle 113\cdot q\equiv -37{\pmod {28}}}$

${\displaystyle 1\cdot q\equiv 19{\pmod {28}}}$

From ${\displaystyle (3):\ p={\frac {37+113\cdot q}{28}}={\frac {37+113\cdot 19}{28}}=78}$

From ${\displaystyle (2):\ x={\frac {263+311\cdot p}{113}}={\frac {263+311\cdot 78}{113}}=217}$

Check:

# python code.
>>> (113*217 - 263) / 311
78.0
>>>


### Modular Inverses

If you have to perform many calculations with constant ${\displaystyle A,N,}$ it may be worthwhile to calculate ${\displaystyle A\cdot x\equiv 1{\pmod {N}}.}$

Let ${\displaystyle A^{'}}$ be a solution of this congruence. Then:

${\displaystyle A\cdot A^{'}\equiv 1{\pmod {N}}.}$

${\displaystyle A}$ and ${\displaystyle A^{'}}$ are modular inverses because their product is ${\displaystyle \equiv 1{\pmod {N}}.}$

For ${\displaystyle A\cdot x\equiv B_{0}{\pmod {N}}.}$

${\displaystyle A\cdot A^{'}\cdot x\equiv A^{'}\cdot B_{0}{\pmod {N}}.}$

${\displaystyle 1\cdot x\equiv A^{'}\cdot B_{0}{\pmod {N}},}$ and likewise for

${\displaystyle 1\cdot x\equiv A^{'}\cdot B_{1}{\pmod {N}},}$

${\displaystyle 1\cdot x\equiv A^{'}\cdot B_{2}{\pmod {N}},}$

${\displaystyle 1\cdot x\equiv A^{'}\cdot B_{3}{\pmod {N}}.}$

### With N composite

When ${\displaystyle N}$ is composite, it may happen that the process of simplifying the congruence ${\displaystyle A\cdot x\equiv B{\pmod {N}}\ \dots \ (1)}$ produces another congruence ${\displaystyle a\cdot x\equiv b{\pmod {n}}}$ where division ${\displaystyle {\frac {N}{n}}}$ is exact.

Let ${\displaystyle x_{1}}$ be a solution of congruence ${\displaystyle a\cdot x\equiv b{\pmod {n}}.}$ Then, every solution of this congruence has form ${\displaystyle x_{1}+K\cdot n.}$

Solution ${\displaystyle x_{1}+K\cdot n}$ is also a solution of congruence ${\displaystyle (1):}$

${\displaystyle A\cdot (x_{1}+K\cdot n)\equiv B{\pmod {N}}.}$

For example :

${\displaystyle 63\cdot x\equiv 56{\pmod {77}}}$

${\displaystyle 9\cdot x\equiv 8{\pmod {11}}}$

${\displaystyle 2\cdot x\equiv 3{\pmod {11}}}$

${\displaystyle 2\cdot x\equiv 3+11{\pmod {11}}}$

${\displaystyle x\equiv 7{\pmod {11}}}$

${\displaystyle x_{1}=7+11\cdot K.}$

# python code
>>> A,B,N
(63, 56, 77)
>>> for K in range(0,7) :
...     x1 = 7 + 11*K
...     remainder = (A*x1 - B) % 77 ; K, x1, remainder
...
(0,  7, 0)
(1, 18, 0)
(2, 29, 0)
(3, 40, 0)
(4, 51, 0)
(5, 62, 0)
(6, 73, 0)
>>>


### python code

def solveLinearCongruence (ABN, debug = 0) :
'''
result = solveLinearCongruence (ABN, debug = 0)

debug contains instructions for :
solveLinearCongruence (), debug & 0xF
simplifyLinearCongruence (), debug & 0xFF0

All operations involve integers. Hence use of function:
quotient, remainder =  divmod(dividend, divisor)
'''
thisName = 'solveLinearCongruence ():'
debug_ = debug & 0xF
# if debug_ == 0 : Print nothing.
# if debug_  & 1 : Print important info.
# if debug_  & 2 : Print less important info.
# if debug_  & 4 : Print less important info.
# if debug_  & 8 : Print everything.
if debug_ & 0b1000 : debug_ |= 0b100
if debug_ & 0b100  : debug_ |= 0b10
if debug_ & 0b10   : debug_ |= 0b1

status = 0
try :
(len(ABN) == 3) or (1/0)
# If (length(ABN) != 3), division (1/0) generates a convenient exception.
A,B,N = [ p for q in ABN for p in [int(q)] if ( p == q ) ]
except : status = 1
if status :
if debug_ & 0b1 : print (thisName, 'Error extracting 3 integer values from ABN.' )
return None
if N < 2 :
if debug_ & 0b1 : print (thisName, 'N must be > 1.' )
return None

if debug_ & 0b10   :
print ()
print (thisName)
if debug_ & 0b100  : print ('    ABN =',ABN)
if debug_ & 0b100  : print ('    len(N) =',len(str(N)))
if debug_ & 0b1000 : print ('    debug =',hex(debug))

result = simplifyLinearCongruence (A,B,N, debug)
if type(result) != tuple :
if debug_ & 0b1 : print (thisName, 'type(result) != tuple', type(result) )
return None
a,b,n = result

stack = []
while 1 :
a, b = a%n, b%n
if debug_ & 0b1000 : print (thisName,'a,b,n =', a,b,n)
if a == 1:
x = b ; break
if a > (n>>1) :
a, b = n-a, n-b
if debug_ & 0b1000 : print (thisName,'  a,b,n =', a,b,n)
if a == 1:
x = b ; break
stack += [(a,b,n)]
# ax /// b mod N
# ax = b + pN
# Np -(-b) = ax
# Np /// -b mod a
a,b,n = n,-b,a

if debug_ & 0b100 : print (thisName,'length of stack =', len(stack))

while stack :
a,b,n = stack[-1]
del (stack[-1])
x,r = divmod(b+x*n, a)
if debug_ & 0b1000 : print (thisName,'x =',x)
if r :
if debug_ & 0b1 : print (thisName, 'Internal error 1 after divmod()')
return None

if debug_ & 0b1 :
# Final check.
q,r = divmod(A*x-B, N)
if r :
print (thisName, 'Internal error 2 after divmod()')
return None

return x

 During testing on my computer with ${\displaystyle N}$ a random integer containing 10,077 decimal digits, length of stack was 13,514 and time to produce solution was about 13 seconds.

## Exercises

### Solve linear Diophantine equation.

#### With 2 unknowns

Given: ${\displaystyle 21613x+31013y=4095605616\ \dots \ (1)}$

Calculate all values of ${\displaystyle x,y}$ for which both ${\displaystyle x,y}$ are positive integers.

Put equation ${\displaystyle (1)}$ in form of congruence:

${\displaystyle ax+by=s}$

${\displaystyle -by+s=ax}$

${\displaystyle -by-(-s)=ax}$

${\displaystyle -by\equiv -s{\pmod {a}}}$

${\displaystyle by\equiv s{\pmod {a}}}$

${\displaystyle 31013y\equiv 4095605616{\pmod {21613}}}$

${\displaystyle 9400y\equiv 6955{\pmod {21613}}\ \dots \ (2)}$

Solve congruence ${\displaystyle (2):}$

solveLinearCongruence ():
ABN = (9400, 6955, 21613)
len(N) = 5
debug = 0x8
solveLinearCongruence (): a,b,n = 1880 1391 21613
solveLinearCongruence (): a,b,n = 933 489 1880
solveLinearCongruence (): a,b,n = 14 444 933
solveLinearCongruence (): a,b,n = 9 4 14
solveLinearCongruence ():   a,b,n = 5 10 14
solveLinearCongruence (): a,b,n = 4 0 5
solveLinearCongruence ():   a,b,n = 1 5 5
solveLinearCongruence (): length of stack = 4
solveLinearCongruence (): x = 16
solveLinearCongruence (): x = 1098
solveLinearCongruence (): x = 2213
solveLinearCongruence (): x = 25442

y1 = 25442

Put equation ${\displaystyle (1)}$ in form of congruence:

${\displaystyle ax+by=s}$

${\displaystyle -ax+s=by}$

${\displaystyle -ax-(-s)=by}$

${\displaystyle -ax\equiv -s{\pmod {b}}}$

${\displaystyle ax\equiv s{\pmod {b}}}$

${\displaystyle 21613x\equiv 4095605616{\pmod {31013}}}$

${\displaystyle 21613x\equiv 28836{\pmod {31013}}\ \dots \ (3)}$

Solve congruence ${\displaystyle (3):}$

solveLinearCongruence ():
ABN = (21613, 28836, 31013)
len(N) = 5
debug = 0x8
solveLinearCongruence (): a,b,n = 1175 11902 31013
solveLinearCongruence (): a,b,n = 463 1023 1175
solveLinearCongruence (): a,b,n = 249 366 463
solveLinearCongruence ():   a,b,n = 214 97 463
solveLinearCongruence (): a,b,n = 35 117 214
solveLinearCongruence (): a,b,n = 4 23 35
solveLinearCongruence (): a,b,n = 3 1 4
solveLinearCongruence ():   a,b,n = 1 3 4
solveLinearCongruence (): length of stack = 5
solveLinearCongruence (): x = 32
solveLinearCongruence (): x = 199
solveLinearCongruence (): x = 431
solveLinearCongruence (): x = 1096
solveLinearCongruence (): x = 28938

x1 = 28938

From congruence ${\displaystyle (2):\ y=y_{1}+pa}$

From congruence ${\displaystyle (3):\ x=x_{1}+qb}$

Put these values of ${\displaystyle x,y}$ in equation ${\displaystyle (1):}$

${\displaystyle a(x_{1}+qb)+b(y_{1}+pa)=s}$

${\displaystyle a(x_{1})+aqb+b(y_{1})+bpa=s}$

${\displaystyle aqb+bpa=s-(a(x_{1})+b(y_{1}))}$

${\displaystyle ab(q+p)=s-(a(x_{1})+b(y_{1}))}$

${\displaystyle p+q={\frac {s-(a(x_{1})+b(y_{1}))}{ab}}}$

${\displaystyle p+q=4}$

# python code
for p in range (-3,7) :
y = y1 + p*a
q = 4-p
x = x1 + q*b
status = ''
if (x > 0) and (y > 0) : status = '****'
print ()
print ('x,y =',x,y,status)
# Verify:
print ('    a*x + b*y == s:', a*x + b*y == s)

x,y = 246029 -39397
a*x + b*y == s: True

x,y = 215016 -17784
a*x + b*y == s: True

x,y = 184003 3829 ****
a*x + b*y == s: True

x,y = 152990 25442 ****
a*x + b*y == s: True

x,y = 121977 47055 ****
a*x + b*y == s: True

x,y = 90964 68668 ****
a*x + b*y == s: True

x,y = 59951 90281 ****
a*x + b*y == s: True

x,y = 28938 111894 ****
a*x + b*y == s: True

x,y = -2075 133507
a*x + b*y == s: True

x,y = -33088 155120
a*x + b*y == s: True

Values of ${\displaystyle x,y}$ highlighted with ${\displaystyle {\text{****}}}$ are all positive, integer values of ${\displaystyle x,y.}$

#### With 3 unknowns

Given: ${\displaystyle 2200013x+1600033y+2800033z=33420571802161\ \dots \ (1).}$

Solve ${\displaystyle (1)}$ for integer values of ${\displaystyle x,y,z.}$

Put equation ${\displaystyle (1)}$ in form of congruence:

${\displaystyle 2200013x+1600033y-33420571802161=-2800033z}$

${\displaystyle 2200013x+1600033y\equiv 33420571802161{\pmod {2800033}}}$

${\displaystyle 2200013x+1600033y\equiv 2321520{\pmod {2800033}}}$

Let ${\displaystyle 2200013x+1600033y=2321520\ \dots \ (2).}$

Solve ${\displaystyle (2)}$ for integer values of ${\displaystyle x,y.}$

${\displaystyle 1600033y\equiv 2321520{\pmod {2200013}}}$

${\displaystyle y_{1}=710184}$

${\displaystyle y=710184+p2200013}$

From ${\displaystyle (1):\ 2200013x+1600033y+2800033z=33420571802161}$

${\displaystyle 2200013x+2800033z=33420571802161-1600033y}$

Using ${\displaystyle y=y_{1}:}$

${\displaystyle A\cdot x+C\cdot z=D\_}$ or:

${\displaystyle 2200013x+2800033z=32284253966089\ \dots \ (3)}$

Solve ${\displaystyle (3)}$ for integer values of ${\displaystyle x,z.}$

${\displaystyle x_{1}=2283529}$

${\displaystyle x=2283529+q\cdot C}$

# python code.
L1 = []
for increment in range (-2*C, 7*C, C) :
x = x1 + increment
# Ax + Cz = D_
# Cz = D_ - A*x
z,rem = divmod(D_ - A*x, C)
status = ''
if (x>0) and (z>0) : status = '****'
print (x,z,rem,status)
print ('    A*x + B*y1 + C*z == D:', A*x + B*y1 + C*z == D)
L1 += [(x,z)]

 Figure 3. Line that is intersection of 2 planes. This line is intersection of 2 planes in Figure 2 above. Every point on line has value ${\displaystyle y=710184.}$ There are exactly 5 points for which all of ${\displaystyle x,y,z}$ are both integer and positive. -3316537 14135790 0 # Remainder 0 shows that calculation of z is exact. A*x + B*y1 + C*z == D: True -516504 11935777 0 A*x + B*y1 + C*z == D: True 2283529 9735764 0 **** A*x + B*y1 + C*z == D: True 5083562 7535751 0 **** A*x + B*y1 + C*z == D: True 7883595 5335738 0 **** A*x + B*y1 + C*z == D: True 10683628 3135725 0 **** A*x + B*y1 + C*z == D: True 13483661 935712 0 **** A*x + B*y1 + C*z == D: True 16283694 -1264301 0 A*x + B*y1 + C*z == D: True 19083727 -3464314 0 A*x + B*y1 + C*z == D: True Values of ${\displaystyle x,z}$ highlighted with ${\displaystyle {\text{****}}}$ are all positive, integer values of ${\displaystyle x,z.}$
 This section shows that all calculated points are in fact on same line. # python code. # This code displays direction numbers from 1 point to next. for p in range (1,len(L1)) : this = L1[p]; x1,z1 = this last = L1[p-1] ; x2,z2 = last print (x1-x2,z1-z2)  2800033 -2200013 2800033 -2200013 2800033 -2200013 2800033 -2200013 2800033 -2200013 2800033 -2200013 2800033 -2200013 2800033 -2200013 Direction numbers are consistent. Therefore, all points are on same line. Recall original equation: ${\displaystyle 2200013x+1600033y+2800033z=33420571802161\ \dots \ (1).}$ ${\displaystyle 2800033}$ is coefficient of ${\displaystyle z.}$ ${\displaystyle 2200013}$ is coefficient of ${\displaystyle x.}$

There is not only an infinite number of points for which all of ${\displaystyle x,y,z}$ are of type integer.

There is also an infinite number of lines similar to the example in this section.

This example used ${\displaystyle y=710184.}$

However, ${\displaystyle y}$ can be ${\displaystyle 710184+p\cdot 2200013}$ where ${\displaystyle p}$ is any integer.

##### More examples
###### #2

In this example:

• Plane ${\displaystyle \pi _{1}}$ is same as plane ${\displaystyle \pi _{1}}$ above.
• Plane ${\displaystyle \pi _{2}}$ is defined as: ${\displaystyle y=9510236=710184+4\cdot 2200013.}$
###### #3

In this example:

• Plane ${\displaystyle \pi _{1}}$ is same as plane ${\displaystyle \pi _{1}}$ above.
• Plane ${\displaystyle \pi _{2}}$ is defined as: ${\displaystyle z=-3464314.}$

### Solve simultaneous linear congruences.

Given:

${\displaystyle x\equiv 7{\pmod {19}}\ \dots \ (1)}$

${\displaystyle x\equiv 25{\pmod {31}}\ \dots \ (2)}$

Calculate all values of ${\displaystyle x}$ that satisfy both congruences ${\displaystyle (1),(2).}$

From ${\displaystyle (1):\ x=7+19\cdot p\ \dots \ (3)}$

From ${\displaystyle (2):\ x=25+31\cdot q\ \dots \ (4)}$

Combine ${\displaystyle (3),(4):}$

${\displaystyle 7+19\cdot p\ =25+31\cdot q}$

${\displaystyle 19\cdot p\ +7-25=31\cdot q}$

${\displaystyle 19\cdot p\ -18=31\cdot q}$

${\displaystyle 19\cdot p\ \equiv 18{\pmod {31}}}$

${\displaystyle p\ \equiv 14{\pmod {31}}}$

${\displaystyle p=14+31\cdot r}$

Substitute this value of ${\displaystyle p}$ into ${\displaystyle (3):}$

${\displaystyle x=7+19\cdot (14+31\cdot r)}$

${\displaystyle x=7+19\cdot 14+19\cdot 31\cdot r}$

${\displaystyle x=273+589\cdot r}$ where ${\displaystyle r}$ is type integer.

Check:

${\displaystyle (273+589\cdot r)\ \%\ 19=7+0=7.}$

${\displaystyle (273+589\cdot r)\ \%\ 31=25+0=25.}$

## 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.}$