A linear congruence is similar to a linear equation, except that it is expressed in modular format:
A
⋅
x
≡
B
(
mod
N
)
{\displaystyle A\cdot x\equiv B{\pmod {N}}}
where
A
,
B
,
N
{\displaystyle A,B,N}
are integers and
N
>
1.
{\displaystyle N>1.}
If
A
⋅
x
≡
B
(
mod
N
)
,
{\displaystyle A\cdot x\equiv B{\pmod {N}},}
then
A
⋅
x
+
C
≡
B
+
C
(
mod
N
)
{\displaystyle A\cdot x+C\equiv B+C{\pmod {N}}}
Proof is similar to that offered above.
Note that the congruence
(
A
+
C
)
⋅
x
≡
B
+
C
(
mod
N
)
{\displaystyle (A+C)\cdot x\equiv B+C{\pmod {N}}}
is not valid, except for
C
=
p
⋅
N
.
{\displaystyle C=p\cdot N.}
Generally:
(
A
+
p
⋅
N
)
⋅
(
x
+
q
⋅
N
)
≡
(
B
+
r
⋅
N
)
(
mod
N
)
.
{\displaystyle (A+p\cdot N)\cdot (x+q\cdot N)\equiv (B+r\cdot N){\pmod {N}}.}
Proof:
(
A
+
p
⋅
N
)
⋅
(
x
+
q
⋅
N
)
−
(
B
+
r
⋅
N
)
{\displaystyle (A+p\cdot N)\cdot (x+q\cdot N)-(B+r\cdot N)}
=
A
⋅
x
+
A
⋅
q
⋅
N
+
p
⋅
N
⋅
x
+
p
⋅
N
⋅
q
⋅
N
−
B
−
r
⋅
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}
=
A
⋅
x
−
B
+
N
⋅
(
A
⋅
q
+
p
⋅
x
+
p
⋅
N
⋅
q
−
r
)
{\displaystyle =A\cdot x-B+N\cdot (A\cdot q+p\cdot x+p\cdot N\cdot q-r)}
which is exactly divisible by
N
.
{\displaystyle N.}
A corollary of this proof is:
(
A
%
N
)
⋅
(
x
%
N
)
≡
(
B
%
N
)
(
mod
N
)
.
{\displaystyle (A\%N)\cdot (x\%N)\equiv (B\%N){\pmod {N}}.}
Law of multiplication
edit
If
A
⋅
x
≡
B
(
mod
N
)
,
{\displaystyle A\cdot x\equiv B{\pmod {N}},}
then
C
⋅
A
⋅
x
≡
C
⋅
B
(
mod
N
)
,
{\displaystyle C\cdot A\cdot x\equiv C\cdot B{\pmod {N}},}
Proof:
C
⋅
A
⋅
x
−
C
⋅
B
{\displaystyle C\cdot A\cdot x-C\cdot B}
=
C
⋅
(
A
⋅
x
−
B
)
{\displaystyle =C\cdot (A\cdot x-B)}
which is exactly divisible by
N
.
{\displaystyle N.}
Simplify the congruence
edit
Simplifying the congruence means reducing the value of
A
{\displaystyle A}
as much as possible.
For example:
30121
⋅
x
≡
30394
(
mod
35893
)
{\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
13.
{\displaystyle 13.}
Therefore:
30121
13
⋅
x
≡
30394
13
(
mod
35893
13
)
{\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]
2317
⋅
x
≡
2338
(
mod
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
7.
{\displaystyle 7.}
Therefore:
2317
7
⋅
x
≡
2338
7
(
mod
2761
)
{\displaystyle {\frac {2317}{7}}\cdot x\equiv {\frac {2338}{7}}{\pmod {2761}}}
>>> [ int(v/7) for v in (2317, 2338)]
[331, 334]
331
⋅
x
≡
334
(
mod
2761
)
{\displaystyle 331\cdot x\equiv 334{\pmod {2761}}}
>>> x
64530
>>> (30121*x - 30394) % 35893
0
>>> (331*x - 334) % 2761
0
Linear congruence
30121
⋅
x
≡
30394
(
mod
35893
)
{\displaystyle 30121\cdot x\equiv 30394{\pmod {35893}}}
has been reduced to
331
⋅
x
≡
334
(
mod
2761
)
.
{\displaystyle 331\cdot x\equiv 334{\pmod {2761}}.}
# 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
edit
Solution of congruence is a value of
x
{\displaystyle x}
that satisfies the congruence.
Solving the linear congruence means continuously simplifying the congruence
by reducing the value of
A
{\displaystyle A}
until
A
{\displaystyle A}
becomes
1
{\displaystyle 1}
at which point the congruence is solved.
For example:
1327
⋅
x
≡
−
4539
(
mod
29
)
{\displaystyle 1327\cdot x\equiv -4539{\pmod {29}}}
becomes in turn:
22
⋅
x
≡
14
(
mod
29
)
{\displaystyle 22\cdot x\equiv 14{\pmod {29}}}
11
⋅
x
≡
7
(
mod
29
)
{\displaystyle 11\cdot x\equiv 7{\pmod {29}}}
33
⋅
x
≡
21
(
mod
29
)
{\displaystyle 33\cdot x\equiv 21{\pmod {29}}}
4
⋅
x
≡
21
(
mod
29
)
{\displaystyle 4\cdot x\equiv 21{\pmod {29}}}
28
⋅
x
≡
147
(
mod
29
)
{\displaystyle 28\cdot x\equiv 147{\pmod {29}}}
−
1
⋅
x
≡
147
(
mod
29
)
{\displaystyle -1\cdot x\equiv 147{\pmod {29}}}
1
⋅
x
≡
−
147
(
mod
29
)
{\displaystyle 1\cdot x\equiv -147{\pmod {29}}}
1
⋅
x
≡
27
(
mod
29
)
{\displaystyle 1\cdot x\equiv 27{\pmod {29}}}
Yes:
(
1327
∗
27
−
(
−
4539
)
)
%
29
=
0.
{\displaystyle (1327*27-(-4539))\ \%\ 29=0.}
For example, solve
439
⋅
x
≡
2157
(
mod
2693
)
{\displaystyle 439\cdot x\equiv 2157{\pmod {2693}}}
quotient, remainder = divmod(2693, 439)
{\displaystyle {\text{quotient, remainder = divmod(2693, 439)}}}
quotient, remainder = 6, 59
{\displaystyle {\text{quotient, remainder = 6, 59}}}
remainder
<=
(
439
>>
1
)
,
{\displaystyle {\text{remainder}}\ <=\ (439\ >>\ 1),}
therefore:
A = remainder = 59
{\displaystyle {\text{A = remainder = 59}}}
B
=
(
−
B
∗
quotient
)
%
N
=
523
{\displaystyle {\text{B}}=(-{\text{B}}*{\text{quotient}})\%{\text{N}}=523}
59
⋅
x
≡
523
(
mod
2693
)
{\displaystyle 59\cdot x\equiv 523{\pmod {2693}}}
quotient, remainder = divmod(2693, 59)
{\displaystyle {\text{quotient, remainder = divmod(2693, 59)}}}
quotient, remainder = 45, 38
{\displaystyle {\text{quotient, remainder = 45, 38}}}
remainder
>
(
59
>>
1
)
,
{\displaystyle {\text{remainder}}>(59>>1),}
therefore:
A
=
A
−
remainder
=
21
{\displaystyle {\text{A}}={\text{A}}-{\text{remainder}}=21}
B
=
(
B
∗
(
quotient
+
1
)
)
%
N
=
2514
{\displaystyle {\text{B}}=({\text{B}}*({\text{quotient}}+1))\%{\text{N}}=2514}
New value of
A
{\displaystyle {\text{New value of}}\ A}
is always
<=
Old value of
A
2
.
{\displaystyle <=\ {\frac {{\text{Old value of}}\ A}{2}}.}
21
⋅
x
≡
2514
(
mod
2693
)
{\displaystyle 21\cdot x\equiv 2514{\pmod {2693}}}
7
⋅
x
≡
838
(
mod
2693
)
{\displaystyle 7\cdot x\equiv 838{\pmod {2693}}}
quotient, remainder = divmod(2693, 7)
{\displaystyle {\text{quotient, remainder = divmod(2693, 7)}}}
quotient, remainder = 384, 5
{\displaystyle {\text{quotient, remainder = 384, 5}}}
remainder
>
(
7
>>
1
)
,
{\displaystyle {\text{remainder}}>(7>>1),}
therefore:
A
=
A
−
remainder
=
2
{\displaystyle {\text{A}}={\text{A}}-{\text{remainder}}=2}
B
=
(
B
∗
(
quotient
+
1
)
)
%
N
=
2163
{\displaystyle {\text{B}}=({\text{B}}*({\text{quotient}}+1))\%{\text{N}}=2163}
2
⋅
x
≡
2163
(
mod
2693
)
{\displaystyle 2\cdot x\equiv 2163{\pmod {2693}}}
quotient, remainder = divmod(2693, 2)
{\displaystyle {\text{quotient, remainder = divmod(2693, 2)}}}
quotient, remainder = 1346, 1
{\displaystyle {\text{quotient, remainder = 1346, 1}}}
remainder
<=
(
2
>>
1
)
,
{\displaystyle {\text{remainder}}\ <=\ (2\ >>\ 1),}
therefore:
A = remainder = 1
{\displaystyle {\text{A = remainder = 1}}}
B
=
(
−
B
∗
quotient
)
%
N
=
2428
{\displaystyle {\text{B}}=(-{\text{B}}*{\text{quotient}})\%{\text{N}}=2428}
1
⋅
x
≡
2428
(
mod
2693
)
{\displaystyle 1\cdot x\equiv 2428{\pmod {2693}}}
Method described here is algorithm used in python code below.
For example, solve the linear congruence:
113
⋅
x
≡
263
(
mod
311
)
…
(
1
)
.
{\displaystyle 113\cdot x\equiv 263{\pmod {311}}\ \dots \ (1).}
113
⋅
x
=
263
+
311
⋅
p
…
(
2
)
{\displaystyle 113\cdot x=263+311\cdot p\ \dots \ (2)}
311
⋅
p
−
(
−
263
)
=
113
⋅
x
{\displaystyle 311\cdot p-(-263)=113\cdot x}
311
⋅
p
≡
−
263
(
mod
113
)
{\displaystyle 311\cdot p\equiv -263{\pmod {113}}}
85
⋅
p
≡
76
(
mod
113
)
{\displaystyle 85\cdot p\equiv 76{\pmod {113}}}
(
113
−
85
)
⋅
p
≡
(
113
−
76
)
(
mod
113
)
{\displaystyle (113-85)\cdot p\equiv (113-76){\pmod {113}}}
28
⋅
p
≡
37
(
mod
113
)
{\displaystyle 28\cdot p\equiv 37{\pmod {113}}}
28
⋅
p
=
37
+
113
⋅
q
…
(
3
)
{\displaystyle 28\cdot p=37+113\cdot q\ \dots \ (3)}
113
⋅
q
≡
−
37
(
mod
28
)
{\displaystyle 113\cdot q\equiv -37{\pmod {28}}}
1
⋅
q
≡
19
(
mod
28
)
{\displaystyle 1\cdot q\equiv 19{\pmod {28}}}
From
(
3
)
:
p
=
37
+
113
⋅
q
28
=
37
+
113
⋅
19
28
=
78
{\displaystyle (3):\ p={\frac {37+113\cdot q}{28}}={\frac {37+113\cdot 19}{28}}=78}
From
(
2
)
:
x
=
263
+
311
⋅
p
113
=
263
+
311
⋅
78
113
=
217
{\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
>>>
If you have to perform many calculations with constant
A
,
N
,
{\displaystyle A,N,}
it may be worthwhile to calculate
A
⋅
x
≡
1
(
mod
N
)
.
{\displaystyle A\cdot x\equiv 1{\pmod {N}}.}
Let
A
′
{\displaystyle A^{'}}
be a solution of this congruence. Then:
A
⋅
A
′
≡
1
(
mod
N
)
.
{\displaystyle A\cdot A^{'}\equiv 1{\pmod {N}}.}
A
{\displaystyle A}
and
A
′
{\displaystyle A^{'}}
are modular inverses because their product is
≡
1
(
mod
N
)
.
{\displaystyle \equiv 1{\pmod {N}}.}
For
A
⋅
x
≡
B
0
(
mod
N
)
.
{\displaystyle A\cdot x\equiv B_{0}{\pmod {N}}.}
A
⋅
A
′
⋅
x
≡
A
′
⋅
B
0
(
mod
N
)
.
{\displaystyle A\cdot A^{'}\cdot x\equiv A^{'}\cdot B_{0}{\pmod {N}}.}
1
⋅
x
≡
A
′
⋅
B
0
(
mod
N
)
,
{\displaystyle 1\cdot x\equiv A^{'}\cdot B_{0}{\pmod {N}},}
and likewise for
1
⋅
x
≡
A
′
⋅
B
1
(
mod
N
)
,
{\displaystyle 1\cdot x\equiv A^{'}\cdot B_{1}{\pmod {N}},}
1
⋅
x
≡
A
′
⋅
B
2
(
mod
N
)
,
{\displaystyle 1\cdot x\equiv A^{'}\cdot B_{2}{\pmod {N}},}
1
⋅
x
≡
A
′
⋅
B
3
(
mod
N
)
.
{\displaystyle 1\cdot x\equiv A^{'}\cdot B_{3}{\pmod {N}}.}
When
N
{\displaystyle N}
is composite, it may happen that the process of simplifying the congruence
A
⋅
x
≡
B
(
mod
N
)
…
(
1
)
{\displaystyle A\cdot x\equiv B{\pmod {N}}\ \dots \ (1)}
produces another congruence
a
⋅
x
≡
b
(
mod
n
)
{\displaystyle a\cdot x\equiv b{\pmod {n}}}
where division
N
n
{\displaystyle {\frac {N}{n}}}
is exact.
Let
x
1
{\displaystyle x_{1}}
be a solution of congruence
a
⋅
x
≡
b
(
mod
n
)
.
{\displaystyle a\cdot x\equiv b{\pmod {n}}.}
Then, every solution of this congruence has form
x
1
+
K
⋅
n
.
{\displaystyle x_{1}+K\cdot n.}
Solution
x
1
+
K
⋅
n
{\displaystyle x_{1}+K\cdot n}
is also a solution of congruence
(
1
)
:
{\displaystyle (1):}
A
⋅
(
x
1
+
K
⋅
n
)
≡
B
(
mod
N
)
.
{\displaystyle A\cdot (x_{1}+K\cdot n)\equiv B{\pmod {N}}.}
For example :
63
⋅
x
≡
56
(
mod
77
)
{\displaystyle 63\cdot x\equiv 56{\pmod {77}}}
9
⋅
x
≡
8
(
mod
11
)
{\displaystyle 9\cdot x\equiv 8{\pmod {11}}}
2
⋅
x
≡
3
(
mod
11
)
{\displaystyle 2\cdot x\equiv 3{\pmod {11}}}
2
⋅
x
≡
3
+
11
(
mod
11
)
{\displaystyle 2\cdot x\equiv 3+11{\pmod {11}}}
x
≡
7
(
mod
11
)
{\displaystyle x\equiv 7{\pmod {11}}}
x
1
=
7
+
11
⋅
K
.
{\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 )
>>>
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
N
{\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.
Solve linear Diophantine equation.
edit
Figure 1: Diagram illustrating linear Diophantine equation:
21613
x
+
31013
y
=
4095605616.
{\displaystyle 21613x+31013y=4095605616.}
In quadrant 1, both
x
,
y
{\displaystyle x,y}
are positive. In quadrant 1, there are 6 points for which both
x
,
y
{\displaystyle x,y}
are type int. In quadrants 2 and 4, there are an infinite number of points for which both
x
,
y
{\displaystyle x,y}
are type int. Line does not pass through quadrant 3.
Given:
21613
x
+
31013
y
=
4095605616
…
(
1
)
{\displaystyle 21613x+31013y=4095605616\ \dots \ (1)}
Calculate all values of
x
,
y
{\displaystyle x,y}
for which both
x
,
y
{\displaystyle x,y}
are positive integers.
Put equation
(
1
)
{\displaystyle (1)}
in form of congruence:
a
x
+
b
y
=
s
{\displaystyle ax+by=s}
−
b
y
+
s
=
a
x
{\displaystyle -by+s=ax}
−
b
y
−
(
−
s
)
=
a
x
{\displaystyle -by-(-s)=ax}
−
b
y
≡
−
s
(
mod
a
)
{\displaystyle -by\equiv -s{\pmod {a}}}
b
y
≡
s
(
mod
a
)
{\displaystyle by\equiv s{\pmod {a}}}
31013
y
≡
4095605616
(
mod
21613
)
{\displaystyle 31013y\equiv 4095605616{\pmod {21613}}}
9400
y
≡
6955
(
mod
21613
)
…
(
2
)
{\displaystyle 9400y\equiv 6955{\pmod {21613}}\ \dots \ (2)}
Solve congruence
(
2
)
:
{\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
(
1
)
{\displaystyle (1)}
in form of congruence:
a
x
+
b
y
=
s
{\displaystyle ax+by=s}
−
a
x
+
s
=
b
y
{\displaystyle -ax+s=by}
−
a
x
−
(
−
s
)
=
b
y
{\displaystyle -ax-(-s)=by}
−
a
x
≡
−
s
(
mod
b
)
{\displaystyle -ax\equiv -s{\pmod {b}}}
a
x
≡
s
(
mod
b
)
{\displaystyle ax\equiv s{\pmod {b}}}
21613
x
≡
4095605616
(
mod
31013
)
{\displaystyle 21613x\equiv 4095605616{\pmod {31013}}}
21613
x
≡
28836
(
mod
31013
)
…
(
3
)
{\displaystyle 21613x\equiv 28836{\pmod {31013}}\ \dots \ (3)}
Solve congruence
(
3
)
:
{\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
(
2
)
:
y
=
y
1
+
p
a
{\displaystyle (2):\ y=y_{1}+pa}
From congruence
(
3
)
:
x
=
x
1
+
q
b
{\displaystyle (3):\ x=x_{1}+qb}
Put these values of
x
,
y
{\displaystyle x,y}
in equation
(
1
)
:
{\displaystyle (1):}
a
(
x
1
+
q
b
)
+
b
(
y
1
+
p
a
)
=
s
{\displaystyle a(x_{1}+qb)+b(y_{1}+pa)=s}
a
(
x
1
)
+
a
q
b
+
b
(
y
1
)
+
b
p
a
=
s
{\displaystyle a(x_{1})+aqb+b(y_{1})+bpa=s}
a
q
b
+
b
p
a
=
s
−
(
a
(
x
1
)
+
b
(
y
1
)
)
{\displaystyle aqb+bpa=s-(a(x_{1})+b(y_{1}))}
a
b
(
q
+
p
)
=
s
−
(
a
(
x
1
)
+
b
(
y
1
)
)
{\displaystyle ab(q+p)=s-(a(x_{1})+b(y_{1}))}
p
+
q
=
s
−
(
a
(
x
1
)
+
b
(
y
1
)
)
a
b
{\displaystyle p+q={\frac {s-(a(x_{1})+b(y_{1}))}{ab}}}
p
+
q
=
4
{\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
x
,
y
{\displaystyle x,y}
highlighted with
****
{\displaystyle {\text{****}}}
are all positive, integer values of
x
,
y
.
{\displaystyle x,y.}
Figure 2. Intersection of 2 planes. All integer values of
x
,
y
,
z
{\displaystyle x,y,z}
calculated in this section are on line that is intersection of 2 planes:
π
1
:
2200013
x
+
1600033
y
+
2800033
z
=
33420571802161
{\displaystyle \pi _{1}:2200013x+1600033y+2800033z=33420571802161}
π
2
:
y
=
710184
{\displaystyle \pi _{2}:y=710184}
Given:
2200013
x
+
1600033
y
+
2800033
z
=
33420571802161
…
(
1
)
.
{\displaystyle 2200013x+1600033y+2800033z=33420571802161\ \dots \ (1).}
Solve
(
1
)
{\displaystyle (1)}
for integer values of
x
,
y
,
z
.
{\displaystyle x,y,z.}
Put equation
(
1
)
{\displaystyle (1)}
in form of congruence:
2200013
x
+
1600033
y
−
33420571802161
=
−
2800033
z
{\displaystyle 2200013x+1600033y-33420571802161=-2800033z}
2200013
x
+
1600033
y
≡
33420571802161
(
mod
2800033
)
{\displaystyle 2200013x+1600033y\equiv 33420571802161{\pmod {2800033}}}
2200013
x
+
1600033
y
≡
2321520
(
mod
2800033
)
{\displaystyle 2200013x+1600033y\equiv 2321520{\pmod {2800033}}}
Let
2200013
x
+
1600033
y
=
2321520
…
(
2
)
.
{\displaystyle 2200013x+1600033y=2321520\ \dots \ (2).}
Solve
(
2
)
{\displaystyle (2)}
for integer values of
x
,
y
.
{\displaystyle x,y.}
1600033
y
≡
2321520
(
mod
2200013
)
{\displaystyle 1600033y\equiv 2321520{\pmod {2200013}}}
y
1
=
710184
{\displaystyle y_{1}=710184}
y
=
710184
+
p
2200013
{\displaystyle y=710184+p2200013}
From
(
1
)
:
2200013
x
+
1600033
y
+
2800033
z
=
33420571802161
{\displaystyle (1):\ 2200013x+1600033y+2800033z=33420571802161}
2200013
x
+
2800033
z
=
33420571802161
−
1600033
y
{\displaystyle 2200013x+2800033z=33420571802161-1600033y}
Using
y
=
y
1
:
{\displaystyle y=y_{1}:}
A
⋅
x
+
C
⋅
z
=
D
_
{\displaystyle A\cdot x+C\cdot z=D\_}
or:
2200013
x
+
2800033
z
=
32284253966089
…
(
3
)
{\displaystyle 2200013x+2800033z=32284253966089\ \dots \ (3)}
Solve
(
3
)
{\displaystyle (3)}
for integer values of
x
,
z
.
{\displaystyle x,z.}
x
1
=
2283529
{\displaystyle x_{1}=2283529}
x
=
2283529
+
q
⋅
C
{\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 )]
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:
2200013
x
+
1600033
y
+
2800033
z
=
33420571802161
…
(
1
)
.
{\displaystyle 2200013x+1600033y+2800033z=33420571802161\ \dots \ (1).}
2800033
{\displaystyle 2800033}
is coefficient of
z
.
{\displaystyle z.}
2200013
{\displaystyle 2200013}
is coefficient of
x
.
{\displaystyle x.}
There is not only an infinite number of points for which
all of
x
,
y
,
z
{\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
y
=
710184.
{\displaystyle y=710184.}
However,
y
{\displaystyle y}
can be
710184
+
p
⋅
2200013
{\displaystyle 710184+p\cdot 2200013}
where
p
{\displaystyle p}
is any integer.
In this example:
Plane
π
1
{\displaystyle \pi _{1}}
is same as plane
π
1
{\displaystyle \pi _{1}}
above.
Plane
π
2
{\displaystyle \pi _{2}}
is defined as:
y
=
9510236
=
710184
+
4
⋅
2200013.
{\displaystyle y=9510236=710184+4\cdot 2200013.}
π
2
:
y
=
9510236
{\displaystyle \pi _{2}:y=9510236}
.
Intersection of
π
1
,
π
2
.
{\displaystyle {\text{Intersection of }}\pi _{1},\pi _{2}.}
In this example:
Plane
π
1
{\displaystyle \pi _{1}}
is same as plane
π
1
{\displaystyle \pi _{1}}
above.
Plane
π
2
{\displaystyle \pi _{2}}
is defined as:
z
=
−
3464314.
{\displaystyle z=-3464314.}
π
2
:
z
=
−
3464314.
{\displaystyle \pi _{2}:z=-3464314.}
Intersection of
π
1
,
π
2
.
{\displaystyle {\text{Intersection of }}\pi _{1},\pi _{2}.}
Solve simultaneous linear congruences.
edit
Given:
x
≡
7
(
mod
19
)
…
(
1
)
{\displaystyle x\equiv 7{\pmod {19}}\ \dots \ (1)}
x
≡
25
(
mod
31
)
…
(
2
)
{\displaystyle x\equiv 25{\pmod {31}}\ \dots \ (2)}
Calculate all values of
x
{\displaystyle x}
that satisfy both congruences
(
1
)
,
(
2
)
.
{\displaystyle (1),(2).}
From
(
1
)
:
x
=
7
+
19
⋅
p
…
(
3
)
{\displaystyle (1):\ x=7+19\cdot p\ \dots \ (3)}
From
(
2
)
:
x
=
25
+
31
⋅
q
…
(
4
)
{\displaystyle (2):\ x=25+31\cdot q\ \dots \ (4)}
Combine
(
3
)
,
(
4
)
:
{\displaystyle (3),(4):}
7
+
19
⋅
p
=
25
+
31
⋅
q
{\displaystyle 7+19\cdot p\ =25+31\cdot q}
19
⋅
p
+
7
−
25
=
31
⋅
q
{\displaystyle 19\cdot p\ +7-25=31\cdot q}
19
⋅
p
−
18
=
31
⋅
q
{\displaystyle 19\cdot p\ -18=31\cdot q}
19
⋅
p
≡
18
(
mod
31
)
{\displaystyle 19\cdot p\ \equiv 18{\pmod {31}}}
p
≡
14
(
mod
31
)
{\displaystyle p\ \equiv 14{\pmod {31}}}
p
=
14
+
31
⋅
r
{\displaystyle p=14+31\cdot r}
Substitute this value of
p
{\displaystyle p}
into
(
3
)
:
{\displaystyle (3):}
x
=
7
+
19
⋅
(
14
+
31
⋅
r
)
{\displaystyle x=7+19\cdot (14+31\cdot r)}
x
=
7
+
19
⋅
14
+
19
⋅
31
⋅
r
{\displaystyle x=7+19\cdot 14+19\cdot 31\cdot r}
x
=
273
+
589
⋅
r
{\displaystyle x=273+589\cdot r}
where
r
{\displaystyle r}
is type integer.
Check:
(
273
+
589
⋅
r
)
%
19
=
7
+
0
=
7.
{\displaystyle (273+589\cdot r)\ \%\ 19=7+0=7.}
(
273
+
589
⋅
r
)
%
31
=
25
+
0
=
25.
{\displaystyle (273+589\cdot r)\ \%\ 31=25+0=25.}
A quadratic congruence is a congruence that contains at least one exact square,
for example:
x
2
≡
y
(
mod
N
)
{\displaystyle x^{2}\equiv y{\pmod {N}}}
or
x
2
≡
y
2
(
mod
N
)
.
{\displaystyle x^{2}\equiv y^{2}{\pmod {N}}.}
Initially, let us consider the congruence:
x
2
≡
y
(
mod
N
)
.
{\displaystyle x^{2}\equiv y{\pmod {N}}.}
If
y
=
x
2
−
N
,
{\displaystyle y=x^{2}-N,}
then:
x
2
≡
y
(
mod
N
)
.
{\displaystyle x^{2}\equiv y{\pmod {N}}.}
Proof:
x
2
−
y
=
x
2
−
(
x
2
−
N
)
=
N
{\displaystyle x^{2}-y=x^{2}-(x^{2}-N)=N}
which is exactly divisible by
N
.
{\displaystyle N.}
Consider an example with real numbers.
Let
N
=
257
{\displaystyle N=257}
and
26
≥
x
≥
6.
{\displaystyle 26\geq x\geq 6.}
x
{\displaystyle x}
x
2
−
N
{\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
x
2
−
N
{\displaystyle x^{2}-N}
indicates that the value
x
2
−
N
{\displaystyle x^{2}-N}
is never divisible by
5.
{\displaystyle 5.}
Proof:
N
≡
2
(
mod
5
)
{\displaystyle N\equiv 2{\pmod {5}}}
therefore
N
−
2
=
k
5
{\displaystyle N-2=k5}
or
N
=
5
k
+
2.
{\displaystyle N=5k+2.}
The table shows all possible values of
x
%
5
{\displaystyle x\ \%\ 5}
and
y
%
5
:
{\displaystyle y\ \%\ 5:}
x
{\displaystyle x}
x
2
{\displaystyle x^{2}}
y
=
x
2
−
N
{\displaystyle y=x^{2}-N}
5
p
+
0
{\displaystyle 5p+0}
25
p
2
+
0
p
+
0
{\displaystyle 25p^{2}+\ \ 0p+\ \ 0}
25
p
2
+
0
p
+
0
−
(
5
k
+
2
)
=
25
p
2
+
0
p
−
5
k
−
2
{\displaystyle 25p^{2}+\ \ 0p+\ \ 0\ \ -\ \ (5k+2)\ \ =\ \ 25p^{2}+\ \ 0p\ \ -\ \ 5k-\ \ 2}
5
p
+
1
{\displaystyle 5p+1}
25
p
2
+
10
p
+
1
{\displaystyle 25p^{2}+10p+\ \ 1}
25
p
2
+
10
p
+
1
−
(
5
k
+
2
)
=
25
p
2
+
10
p
−
5
k
−
1
{\displaystyle 25p^{2}+10p+\ \ 1\ \ -\ \ (5k+2)\ \ =\ \ 25p^{2}+10p\ \ -\ \ 5k-\ \ 1}
5
p
+
2
{\displaystyle 5p+2}
25
p
2
+
20
p
+
4
{\displaystyle 25p^{2}+20p+\ \ 4}
25
p
2
+
20
p
+
4
−
(
5
k
+
2
)
=
25
p
2
+
20
p
−
5
k
+
2
{\displaystyle 25p^{2}+20p+\ \ 4\ \ -\ \ (5k+2)\ \ =\ \ 25p^{2}+20p\ \ -\ \ 5k+\ \ 2}
5
p
+
3
{\displaystyle 5p+3}
25
p
2
+
30
p
+
9
{\displaystyle 25p^{2}+30p+\ \ 9}
25
p
2
+
30
p
+
9
−
(
5
k
+
2
)
=
25
p
2
+
30
p
−
5
k
+
7
{\displaystyle 25p^{2}+30p+\ \ 9\ \ -\ \ (5k+2)\ \ =\ \ 25p^{2}+30p\ \ -\ \ 5k+\ \ 7}
5
p
+
4
{\displaystyle 5p+4}
25
p
2
+
40
p
+
16
{\displaystyle 25p^{2}+40p+16}
25
p
2
+
40
p
+
16
−
(
5
k
+
2
)
=
25
p
2
+
40
p
−
5
k
+
14
{\displaystyle 25p^{2}+40p+16\ \ -\ \ (5k+2)\ \ =\ \ 25p^{2}+40p\ \ -\ \ 5k+14}
As you can see, the value
y
=
x
2
−
N
{\displaystyle y=x^{2}-N}
is never exactly divisible by
5.
{\displaystyle 5.}
If you look closely, you will see also that it is never exactly divisible by
3
{\displaystyle 3}
or
7.
{\displaystyle 7.}
However, you can see at least one value of
y
{\displaystyle y}
exactly divisible by
11
{\displaystyle 11}
and
at least one value of
y
{\displaystyle y}
exactly divisible by
13.
{\displaystyle 13.}
The table shows all possible values of
x
%
11
{\displaystyle x\ \%\ 11}
and
y
%
11
:
{\displaystyle y\ \%\ 11:}
x
{\displaystyle x}
x
2
{\displaystyle x^{2}}
y
=
x
2
−
N
{\displaystyle y=x^{2}-N}
11
p
+
0
{\displaystyle 11p+\ \ 0}
121
p
2
+
{\displaystyle 121p^{2}+\ \ }
0
p
+
{\displaystyle \ \ 0p+\ \ }
0
{\displaystyle \ \ 0}
121
p
2
+
{\displaystyle 121p^{2}+\ \ }
0
p
−
11
k
−
4
=
121
p
2
+
{\displaystyle \ \ 0p-11k-\ \ 4\ \ =\ \ 121p^{2}+\ \ }
0
p
−
11
(
k
+
1
)
+
7
{\displaystyle \ \ 0p-11(k+1)+\ \ 7\ \ }
{\displaystyle \ \ }
11
p
+
1
{\displaystyle 11p+\ \ 1}
121
p
2
+
22
p
+
{\displaystyle 121p^{2}+\ \ 22p+\ \ }
1
{\displaystyle \ \ 1}
121
p
2
+
22
p
−
11
k
−
3
=
121
p
2
+
22
p
−
11
(
k
+
1
)
+
8
{\displaystyle 121p^{2}+\ \ 22p-11k-\ \ 3\ \ =\ \ 121p^{2}+\ \ 22p-11(k+1)+\ \ 8\ \ }
{\displaystyle \ \ }
11
p
+
2
{\displaystyle 11p+\ \ 2}
121
p
2
+
44
p
+
{\displaystyle 121p^{2}+\ \ 44p+\ \ }
4
{\displaystyle \ \ 4}
121
p
2
+
20
p
−
11
k
+
0
=
121
p
2
+
20
p
−
11
k
+
0
{\displaystyle 121p^{2}+\ \ 20p-11k+\ \ 0\ \ =\ \ 121p^{2}+\ \ 20p-11k+\ \ 0\ \ }
{\displaystyle \ \ }
{\displaystyle \ \ }
{\displaystyle \ \ }
∗
{\displaystyle \ \ *}
11
p
+
3
{\displaystyle 11p+\ \ 3}
121
p
2
+
66
p
+
{\displaystyle 121p^{2}+\ \ 66p+\ \ }
9
{\displaystyle \ \ 9}
121
p
2
+
66
p
−
11
k
+
5
=
121
p
2
+
66
p
−
11
k
+
5
{\displaystyle 121p^{2}+\ \ 66p-11k+\ \ 5\ \ =\ \ 121p^{2}+\ \ 66p-11k+\ \ 5\ \ }
{\displaystyle \ \ }
{\displaystyle \ \ }
{\displaystyle \ \ }
{\displaystyle \ \ }
{\displaystyle \ \ }
11
p
+
4
{\displaystyle 11p+\ \ 4}
121
p
2
+
88
p
+
16
{\displaystyle 121p^{2}+\ \ 88p+\ \ 16}
121
p
2
+
88
p
−
11
k
+
12
=
121
p
2
+
88
p
−
11
(
k
−
1
)
+
1
{\displaystyle 121p^{2}+\ \ 88p-11k+12\ \ =\ \ 121p^{2}+\ \ 88p-11(k-1)+\ \ 1\ \ }
{\displaystyle \ \ }
11
p
+
5
{\displaystyle 11p+\ \ 5}
121
p
2
+
110
p
+
25
{\displaystyle 121p^{2}+110p+\ \ 25}
121
p
2
+
110
p
−
11
k
+
21
=
121
p
2
+
110
p
−
11
(
k
−
1
)
+
10
{\displaystyle 121p^{2}+110p-11k+21\ \ =\ \ 121p^{2}+110p-11(k-1)+10\ \ }
{\displaystyle \ \ }
11
p
+
6
{\displaystyle 11p+\ \ 6}
121
p
2
+
132
p
+
36
{\displaystyle 121p^{2}+132p+\ \ 36}
121
p
2
+
132
p
−
11
k
+
32
=
121
p
2
+
132
p
−
11
(
k
−
2
)
+
10
{\displaystyle 121p^{2}+132p-11k+32\ \ =\ \ 121p^{2}+132p-11(k-2)+10\ \ }
{\displaystyle \ \ }
11
p
+
7
{\displaystyle 11p+\ \ 7}
121
p
2
+
154
p
+
49
{\displaystyle 121p^{2}+154p+\ \ 49}
121
p
2
+
154
p
−
11
k
+
45
=
121
p
2
+
154
p
−
11
(
k
−
4
)
+
1
{\displaystyle 121p^{2}+154p-11k+45\ \ =\ \ 121p^{2}+154p-11(k-4)+\ \ 1\ \ }
{\displaystyle \ \ }
11
p
+
8
{\displaystyle 11p+\ \ 8}
121
p
2
+
176
p
+
64
{\displaystyle 121p^{2}+176p+\ \ 64}
121
p
2
+
176
p
−
11
k
+
60
=
121
p
2
+
176
p
−
11
(
k
−
5
)
+
5
{\displaystyle 121p^{2}+176p-11k+60\ \ =\ \ 121p^{2}+176p-11(k-5)+\ \ 5\ \ }
{\displaystyle \ \ }
11
p
+
9
{\displaystyle 11p+\ \ 9}
121
p
2
+
198
p
+
81
{\displaystyle 121p^{2}+198p+\ \ 81}
121
p
2
+
198
p
−
11
k
+
77
=
121
p
2
+
198
p
−
11
(
k
−
7
)
+
0
∗
{\displaystyle 121p^{2}+198p-11k+77\ \ =\ \ 121p^{2}+198p-11(k-7)+\ \ 0\ \ *}
11
p
+
10
{\displaystyle 11p+10}
121
p
2
+
220
p
+
100
{\displaystyle 121p^{2}+220p+100}
121
p
2
+
220
p
−
11
k
+
96
=
121
p
2
+
220
p
−
11
(
k
−
8
)
+
8
{\displaystyle 121p^{2}+220p-11k+96\ \ =\ \ 121p^{2}+220p-11(k-8)+\ \ 8\ \ }
{\displaystyle \ \ }
The two lines marked by an
∗
{\displaystyle *}
show values of
y
{\displaystyle y}
exactly divisible by
11.
{\displaystyle 11.}
The two values of
x
,
{\displaystyle x,}
11
p
+
2
{\displaystyle 11p+2}
and
11
p
+
9
,
{\displaystyle 11p+9,}
or
11
p
±
2
{\displaystyle 11p\pm 2}
are
solutions of the congruence.
Why are values of
y
{\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
5
:
{\displaystyle 5:}
x
2
≡
y
(
mod
5
)
{\displaystyle x^{2}\equiv y{\pmod {5}}}
for
5
>
x
≥
0.
{\displaystyle 5>x\geq 0.}
x
{\displaystyle x}
x
2
{\displaystyle x^{2}}
(
x
2
)
%
5
{\displaystyle (x^{2})\ \%\ 5}
0
0
0
1
1
1
2
4
4
3
9
4
4
16
1
Quadratic residues of
5
{\displaystyle 5}
are
0
,
1
,
4.
{\displaystyle 0,1,4.}
Values
2
,
3
{\displaystyle 2,3}
are not quadratic residues of
5.
{\displaystyle 5.}
These values are quadratic non-residues.
To calculate the quadratic residues of a small prime
p
:
{\displaystyle p:}
# python code:
def quadResidues ( p ) :
L1 = []
for v in range ( p >> 1 , - 1 , - 1 ) :
L1 += [( v * v ) % p ]
return L1
print ( quadResidues ( 11 ))
Quadratic residues of
11
{\displaystyle 11}
are
0
,
1
,
3
,
4
,
5
,
9.
{\displaystyle 0,1,3,4,5,9.}
The method presented here answers the question, "What are the quadratic residues of p?"
If
p
{\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
N
=
257.
{\displaystyle N=257.}
N
%
5
=
2
,
{\displaystyle N\ \%\ 5=2,}
therefore
N
{\displaystyle N}
is not a quadratic residue of
5.
{\displaystyle 5.}
This is why
x
2
−
N
{\displaystyle x^{2}-N}
is never divisible by
5
{\displaystyle 5}
exactly.
N
%
11
=
4
,
{\displaystyle N\ \%\ 11=4,}
therefore
N
{\displaystyle N}
is a quadratic residue of
11
{\displaystyle 11}
and a value of
x
{\displaystyle x}
that satisfies the congruence
x
2
≡
4
(
mod
257
)
{\displaystyle x^{2}\equiv 4{\pmod {257}}}
has form
11
p
±
2.
{\displaystyle 11p\pm 2.}
From the table above:
x
{\displaystyle x}
x
2
−
N
{\displaystyle x^{2}\ -\ N}
9
-176
13
-88
20
143
24
319
These
4
{\displaystyle 4}
values of
x
2
−
N
{\displaystyle x^{2}-N}
are exactly divisible by
11.
{\displaystyle 11.}
x
=
9
{\displaystyle x=9}
is
11
⋅
1
−
2.
{\displaystyle 11\cdot 1-2.}
x
=
13
{\displaystyle x=13}
is
11
⋅
1
+
2.
{\displaystyle 11\cdot 1+2.}
x
=
20
{\displaystyle x=20}
is
11
⋅
2
−
2.
{\displaystyle 11\cdot 2-2.}
x
=
24
{\displaystyle x=24}
is
11
⋅
2
+
2.
{\displaystyle 11\cdot 2+2.}
This section uses prime number
41
{\displaystyle 41}
as an example.
Using quadResidues(p)
quadratic residues of
41
{\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
41
{\displaystyle 41}
are:
qnr41 = [3, 6, 7, 11, 12, 13, 14, 15, 17, 19, 22, 24, 26, 27, 28, 29, 30, 34, 35, 38]
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
41
,
{\displaystyle 41,}
the product of 2 residues is a residue. Advanced math proves that this is true for all primes.
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
41
,
{\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
edit
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
41
,
{\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
0
{\displaystyle 0}
as not a legitimate residue.
0
{\displaystyle 0}
is not included as a residue in the test above.
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
a
p
−
1
2
≡
{
1
(
mod
p
)
if there is an integer
x
such that
a
≡
x
2
(
mod
p
)
,
−
1
(
mod
p
)
if there is no such integer.
{\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:
(
a
p
)
≡
a
p
−
1
2
(
mod
p
)
.
{\displaystyle \left({\frac {a}{p}}\right)\equiv a^{\tfrac {p-1}{2}}{\pmod {p}}.}
(
a
p
)
=
{
1
if
a
is a quadratic residue modulo
p
and
a
≢
0
(
mod
p
)
,
−
1
if
a
is a non-quadratic residue modulo
p
,
0
if
a
≡
0
(
mod
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
3
{\displaystyle 3}
is a quadratic residue modulo
11.
{\displaystyle 11.}
Therefore
(
3
5
)
%
11
{\displaystyle (3^{5})\ \%\ 11}
should be
1.
{\displaystyle 1.}
# python code:
>>> ( 3 ** 5 ) % 11
1
It is known that
7
{\displaystyle 7}
is a quadratic non-residue modulo
11.
{\displaystyle 11.}
Therefore
(
7
5
)
%
11
{\displaystyle (7^{5})\ \%\ 11}
should be
−
1.
{\displaystyle -1.}
# python code:
>>> ( 7 ** 5 ) % 11
10
10
≡
−
1
(
mod
11
)
{\displaystyle 10\equiv -1{\pmod {11}}}
Python's decimal module provides a method for computing
(
a
x
)
%
p
{\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' )
761838257286
≡
−
1
(
mod
761838257287
)
{\displaystyle 761838257286\equiv -1{\pmod {761838257287}}}
Value
a
=
3456789
{\displaystyle a=3456789}
is not a quadratic residue modulo
p
=
761838257287.
{\displaystyle p=761838257287.}
An exact square such as
1
,
4
,
9
,
16
,
25
,
…
{\displaystyle 1,4,9,16,25,\dots }
is always a quadratic residue modulo an odd prime
p
.
{\displaystyle p.}
Product of 2 residues
edit
Let
a
,
b
{\displaystyle a,b}
be quadratic residues modulo odd prime
p
.
{\displaystyle p.}
Let
q
=
p
−
1
2
.
{\displaystyle q={\frac {p-1}{2}}.}
Then:
a
q
≡
1
(
mod
p
)
{\displaystyle a^{q}\equiv 1{\pmod {p}}}
b
q
≡
1
(
mod
p
)
{\displaystyle b^{q}\equiv 1{\pmod {p}}}
By law of multiplication:
(
a
q
)
(
b
q
)
≡
(
1
)
(
1
)
(
mod
p
)
{\displaystyle (a^{q})(b^{q})\equiv (1)(1){\pmod {p}}}
or
(
a
⋅
b
)
q
≡
1
(
mod
p
)
{\displaystyle (a\cdot b)^{q}\equiv 1{\pmod {p}}}
Product
(
a
⋅
b
)
{\displaystyle (a\cdot b)}
of 2 quadratic residues
a
,
b
{\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
edit
Several modern methods for determining the factors of a given integer attempt
to create two congruent squares modulo integer
N
.
{\displaystyle N.}
x
2
≡
y
2
(
mod
N
)
{\displaystyle x^{2}\equiv y^{2}{\pmod {N}}}
This means that the difference between the two squares is exactly divisible
by
N
{\displaystyle N}
:
N
∣
(
x
2
−
y
2
)
.
{\displaystyle N\mid (x^{2}-y^{2}).}
Integer
N
{\displaystyle N}
always contains the factors
N
,
1
,
{\displaystyle N,1,}
called trivial factors.
If
N
{\displaystyle N}
contains two non-trivial factors
p
,
q
,
{\displaystyle p,q,}
then:
(
x
+
y
)
(
x
−
y
)
p
⋅
q
.
{\displaystyle {\frac {(x+y)(x-y)}{p\cdot q}}.}
With a little luck
p
∣
(
x
+
y
)
{\displaystyle p\mid (x+y)}
and
q
∣
(
x
−
y
)
{\displaystyle q\mid (x-y)}
in which case:
p
=
igcd
(
x
+
y
,
N
)
{\displaystyle p={\text{igcd}}(x+y,N)}
and
q
=
igcd
(
x
−
y
,
N
)
{\displaystyle q={\text{igcd}}(x-y,N)}
where
"
igcd
{\displaystyle {\text{igcd}}}
" is function "
integer greatest common divisor.
{\displaystyle {\text{integer greatest common divisor.}}}
"
We will use quadratic congruences to calculate factors of
N
=
4171
{\displaystyle N=4171}
for
164
≥
x
≥
1.
{\displaystyle 164\geq x\geq 1.}
Right hand side exact square
edit
One congruence produced an exact square for y:
x
{\displaystyle x}
x
2
{\displaystyle x^{2}}
y
=
x
2
−
N
{\displaystyle y=x^{2}-N}
70
4900
729
4900
≡
729
(
mod
N
)
{\displaystyle 4900\equiv 729{\pmod {N}}}
70
2
≡
27
2
(
mod
N
)
{\displaystyle 70^{2}\equiv 27^{2}{\pmod {N}}}
p
=
igcd
(
70
−
27
,
4171
)
{\displaystyle p={\text{igcd}}(70-27,4171)}
=
igcd
(
43
,
4171
)
{\displaystyle ={\text{igcd}}(43,4171)}
=
43.
{\displaystyle =43.}
q
=
igcd
(
70
+
27
,
4171
)
{\displaystyle q={\text{igcd}}(70+27,4171)}
=
igcd
(
97
,
4171
)
{\displaystyle ={\text{igcd}}(97,4171)}
=
97.
{\displaystyle =97.}
Non-trivial factors of
4171
{\displaystyle 4171}
are
43
,
97.
{\displaystyle 43,97.}
Right hand side negative
edit
Table below contains a sample of values of
x
{\displaystyle x}
that produce negative
y
:
{\displaystyle y:}
x
{\displaystyle x}
x
2
{\displaystyle x^{2}}
y
=
x
2
−
N
{\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
edit
The congruences:
x
{\displaystyle x}
x
2
{\displaystyle x^{2}}
y
=
x
2
−
N
{\displaystyle y=x^{2}-N}
{\displaystyle \ \ }
8
{\displaystyle \ \ \ \ }
64
-4107
{\displaystyle \ \ }
**
64
4096
{\displaystyle \ \ \ \ }
-75
{\displaystyle \ \ }
**
64
≡
−
4107
(
mod
N
)
{\displaystyle 64\equiv -4107{\pmod {N}}}
4096
≡
−
75
(
mod
N
)
{\displaystyle 4096\equiv -75{\pmod {N}}}
64
⋅
4096
≡
−
4107
⋅
(
−
75
)
(
mod
N
)
{\displaystyle 64\cdot 4096\equiv -4107\cdot (-75){\pmod {N}}}
262144
≡
308025
(
mod
N
)
{\displaystyle 262144\equiv 308025{\pmod {N}}}
512
2
≡
555
2
(
mod
4171
)
{\displaystyle 512^{2}\equiv 555^{2}{\pmod {4171}}}
p
=
igcd
(
555
−
512
,
4171
)
{\displaystyle p={\text{igcd}}(555-512,4171)}
=
igcd
(
43
,
4171
)
{\displaystyle ={\text{igcd}}(43,4171)}
=
43.
{\displaystyle =43.}
q
=
igcd
(
555
+
512
,
4171
)
{\displaystyle q={\text{igcd}}(555+512,4171)}
=
igcd
(
1067
,
4171
)
{\displaystyle ={\text{igcd}}(1067,4171)}
=
97.
{\displaystyle =97.}
Non-trivial factors of
4171
{\displaystyle 4171}
are
43
,
97.
{\displaystyle 43,97.}
Non-trivial result 2
edit
The congruences:
x
{\displaystyle x}
x
2
{\displaystyle x^{2}}
y
=
x
2
−
N
{\displaystyle y=x^{2}-N}
11
121
-4050
!!
61
3721
-450
!!
121
≡
−
4050
(
mod
N
)
{\displaystyle 121\equiv -4050{\pmod {N}}}
3721
≡
−
450
(
mod
N
)
{\displaystyle 3721\equiv -450{\pmod {N}}}
121
⋅
3721
≡
−
4050
⋅
(
−
450
)
(
mod
N
)
{\displaystyle 121\cdot 3721\equiv -4050\cdot (-450){\pmod {N}}}
450241
≡
1822500
(
mod
N
)
{\displaystyle 450241\equiv 1822500{\pmod {N}}}
671
2
≡
1350
2
(
mod
4171
)
{\displaystyle 671^{2}\equiv 1350^{2}{\pmod {4171}}}
p
=
igcd
(
1350
−
671
,
4171
)
{\displaystyle p={\text{igcd}}(1350-671,4171)}
=
igcd
(
679
,
4171
)
{\displaystyle ={\text{igcd}}(679,4171)}
=
97.
{\displaystyle =97.}
q
=
igcd
(
1350
+
671
,
4171
)
{\displaystyle q={\text{igcd}}(1350+671,4171)}
=
igcd
(
2021
,
4171
)
{\displaystyle ={\text{igcd}}(2021,4171)}
=
43.
{\displaystyle =43.}
Non-trivial factors of
4171
{\displaystyle 4171}
are
43
,
97.
{\displaystyle 43,97.}
Right hand side positive
edit
Table below contains a sample of values of
x
{\displaystyle x}
that produce positive
y
:
{\displaystyle y:}
x
{\displaystyle x}
x
2
{\displaystyle x^{2}}
y
=
x
2
−
N
{\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 \ \ \ \ \ \ \ \ \ \ }
The congruences:
x
{\displaystyle x}
x
2
{\displaystyle x^{2}}
y
=
x
2
−
N
{\displaystyle y=x^{2}-N}
65
4225
{\displaystyle \ \ \ \ }
54
{\displaystyle \ \ }
**
{\displaystyle \ \ \ \ }
89
7921
3750
{\displaystyle \ \ }
**!!
4225
≡
54
(
mod
N
)
{\displaystyle 4225\equiv 54{\pmod {N}}}
7921
≡
3750
(
mod
N
)
{\displaystyle 7921\equiv 3750{\pmod {N}}}
4225
⋅
7921
≡
54
⋅
3750
(
mod
N
)
{\displaystyle 4225\cdot 7921\equiv 54\cdot 3750{\pmod {N}}}
33466225
≡
202500
(
mod
N
)
{\displaystyle 33466225\equiv 202500{\pmod {N}}}
5785
2
≡
450
2
(
mod
4171
)
{\displaystyle 5785^{2}\equiv 450^{2}{\pmod {4171}}}
p
=
igcd
(
5785
−
450
,
4171
)
{\displaystyle p={\text{igcd}}(5785-450,4171)}
=
igcd
(
5335
,
4171
)
{\displaystyle ={\text{igcd}}(5335,4171)}
=
97.
{\displaystyle =97.}
q
=
igcd
(
5785
+
450
,
4171
)
{\displaystyle q={\text{igcd}}(5785+450,4171)}
=
igcd
(
6235
,
4171
)
{\displaystyle ={\text{igcd}}(6235,4171)}
=
43.
{\displaystyle =43.}
Non-trivial factors of
4171
{\displaystyle 4171}
are
43
,
97.
{\displaystyle 43,97.}
The congruences:
x
{\displaystyle x}
x
2
{\displaystyle x^{2}}
y
=
x
2
−
N
{\displaystyle y=x^{2}-N}
{\displaystyle \ \ }
89
{\displaystyle \ \ }
7921
{\displaystyle \ \ }
3750
{\displaystyle \ \ }
**!!
145
21025
16854
{\displaystyle \ \ \ \ \ \ }
!!
7921
≡
3750
(
mod
N
)
{\displaystyle 7921\equiv 3750{\pmod {N}}}
21025
≡
16854
(
mod
N
)
{\displaystyle 21025\equiv 16854{\pmod {N}}}
7921
⋅
21025
≡
3750
⋅
16854
(
mod
N
)
{\displaystyle 7921\cdot 21025\equiv 3750\cdot 16854{\pmod {N}}}
166539025
≡
63202500
(
mod
N
)
{\displaystyle 166539025\equiv 63202500{\pmod {N}}}
12905
2
≡
7950
2
(
mod
4171
)
{\displaystyle 12905^{2}\equiv 7950^{2}{\pmod {4171}}}
p
=
igcd
(
12905
−
7950
,
4171
)
{\displaystyle p={\text{igcd}}(12905-7950,4171)}
=
igcd
(
4955
,
4171
)
{\displaystyle ={\text{igcd}}(4955,4171)}
=
1.
{\displaystyle =1.}
q
=
igcd
(
12905
+
7950
,
4171
)
{\displaystyle q={\text{igcd}}(12905+7950,4171)}
=
igcd
(
20855
,
4171
)
{\displaystyle ={\text{igcd}}(20855,4171)}
=
4171.
{\displaystyle =4171.}
This congruence produced the trivial factors of
4171.
{\displaystyle 4171.}
The congruences:
x
{\displaystyle x}
x
2
{\displaystyle x^{2}}
y
=
x
2
−
N
{\displaystyle y=x^{2}-N}
{\displaystyle \ \ }
56
{\displaystyle \ \ }
3136
-1035
{\displaystyle \ \ }
59
{\displaystyle \ \ }
3481
{\displaystyle \ \ }
-690
145
21025
16854
3136
≡
−
1035
(
mod
N
)
{\displaystyle 3136\equiv -1035{\pmod {N}}}
3481
≡
−
690
(
mod
N
)
{\displaystyle 3481\equiv -690{\pmod {N}}}
21025
≡
16854
(
mod
N
)
{\displaystyle 21025\equiv 16854{\pmod {N}}}
3136
⋅
3481
⋅
21025
≡
−
1035
⋅
−
690
⋅
16854
(
mod
N
)
{\displaystyle 3136\cdot 3481\cdot 21025\equiv -1035\cdot -690\cdot 16854{\pmod {N}}}
229517646400
≡
12036284100
(
mod
N
)
{\displaystyle 229517646400\equiv 12036284100{\pmod {N}}}
479080
2
≡
109710
2
(
mod
4171
)
{\displaystyle 479080^{2}\equiv 109710^{2}{\pmod {4171}}}
p
=
igcd
(
479080
−
109710
,
4171
)
{\displaystyle p={\text{igcd}}(479080-109710,4171)}
=
43.
{\displaystyle =43.}
q
=
igcd
(
479080
+
109710
,
4171
)
{\displaystyle q={\text{igcd}}(479080+109710,4171)}
=
97.
{\displaystyle =97.}
Non-trivial factors of
4171
{\displaystyle 4171}
are
43
,
97.
{\displaystyle 43,97.}