Congruences

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:

$A\equiv B(\mathrm{mod}N)$

read as: A is congruent with B modulo N. Template:RoundBoxTop Programming language python, for example, accepts the following modular arithmetic:

>>> 14%(1)
0
>>> 14%(-3)
-1

On this page we'll say that $A,B,N$ are integers and $N>1.$ Template:RoundBoxBottom This means that:

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

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

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

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

Law of addition

Adding a constant

Template:RoundBoxTop If $A\equiv B(\mathrm{mod}N),$ then: $A+q\equiv B+q(\mathrm{mod}N).$

Proof:

$A-B=K\cdot N$, therefore $A=B+K\cdot N.$

$(A+q)-(B+q)=B+K\cdot N+q-B-q=K\cdot N$ which is exactly divisible by N. Template:RoundBoxBottom

Adding 2 congruences

Template:RoundBoxTop If $A\equiv B(\mathrm{mod}N),$ and $C\equiv D(\mathrm{mod}N),$ then: $A+C\equiv B+D(\mathrm{mod}N).$

Proof:

$A-B=K_1\cdot N$, therefore $A=B+K_1\cdot N$ and $C=D+K_2\cdot N$

$(A+C)-(B+D)$ $=B+K_1\cdot N+D+K_2\cdot N-B-D$ $=N(K_1+K_2)$ which is exactly divisible by N. Template:RoundBoxBottom

Law of Common Congruence

Template:RoundBoxTop If $A\equiv B(\mathrm{mod}N)$ and

$C\equiv B(\mathrm{mod}N),$ then:

$A\equiv C(\mathrm{mod}N).$

Proof:

$A=B+K_1\cdot N$ and $C=B+K_2\cdot N.$

$A-C=B+K_1\cdot N-B-K_2\cdot N=(K_1-K_2)N$ which is exactly divisible by N. Template:RoundBoxBottom

Law of Multiplication

by a constant

Template:RoundBoxTop If $A\equiv B(\mathrm{mod}N)$ then:

$A\cdot p\equiv B\cdot p(\mathrm{mod}N).$

Proof:

$A\cdot p-B\cdot p=p(A-B)$ which is exactly divisible by N. Template:RoundBoxBottom

by another congruence

Template:RoundBoxTop If $A\equiv B(\mathrm{mod}N)$ and

$C\equiv D(\mathrm{mod}N),$ then:

$A\cdot C\equiv B\cdot D(\mathrm{mod}N).$

Proof:

$A=B+K_1\cdot N$ and $C=D+K_2\cdot N.$

$A\cdot C-B\cdot D$ $=(B+K_1\cdot N)(D+K_2\cdot N)-B\cdot D$ $=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$ $=N(B\cdot K_2+K_1\cdot D+K_1\cdot K_2\cdot N)$ which is exactly divisible by N. Template:RoundBoxBottom

Law of squares

Template:RoundBoxTop If $A\equiv B(\mathrm{mod}N)$ then:

$A^2\equiv B^2(\mathrm{mod}N).$

Proof:

$A^2-B^2=(A+B)(A-B)$ which is exactly divisible by N. Template:RoundBoxBottom

Law of Division?

Template:RoundBoxTop A simple example shows that a "law of division" does not exist.

$24\equiv 14(\mathrm{mod}10).$

However $\frac{24}{2}\equiv ̸\frac{14}{2}(\mathrm{mod}10)$

Because $12-7=5$ is not exactly divisible by $10$ Template:RoundBoxBottom If division of operators is performed carefully, division can be very useful.

Factor common to (A, B)

Let $A\equiv B(\mathrm{mod}N)$

If $A,B$ share a common factor $p$ then:

$p\cdot a\equiv p\cdot b(\mathrm{mod}N).$

Provided that factor $p$ does not divide $N,$ then:

$a\equiv b(\mathrm{mod}N).$

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

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

For example : $42\equiv 207(\mathrm{mod}55)$

$3\cdot 14\equiv 3\cdot 69(\mathrm{mod}55)$

$14\equiv 69(\mathrm{mod}55)$

Factor common to (A, B, N)

If operands $A,B,N$ all share a common factor $p$ then:

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

$a\equiv b(\mathrm{mod}n).$

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

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

For example: $22\equiv 77(\mathrm{mod}55).$

Therefore: $2\equiv 7(\mathrm{mod}5).$

Linear congruences

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

$A\cdot x\equiv B(\mathrm{mod}N)$ where $A,B,N$ are integers and $N>1.$

Law of addition

If $A\cdot x\equiv B(\mathrm{mod}N),$ then $A\cdot x+C\equiv B+C(\mathrm{mod}N)$

Proof is similar to that offered above.

Template:RoundBoxTop Note that the congruence $(A+C)\cdot x\equiv B+C(\mathrm{mod}N)$ is not valid, except for $C=p\cdot N.$

Generally: $(A+p\cdot N)\cdot (x+q\cdot N)\equiv (B+r\cdot N)(\mathrm{mod}N).$

Proof: $(A+p\cdot N)\cdot (x+q\cdot N)-(B+r\cdot N)$

$=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\cdot x-B+N\cdot (A\cdot q+p\cdot x+p\cdot N\cdot q-r)$ which is exactly divisible by $N.$

A corollary of this proof is:

$(A\mathrm{\%}N)\cdot (x\mathrm{\%}N)\equiv (B\mathrm{\%}N)(\mathrm{mod}N).$ Template:RoundBoxBottom

Law of multiplication

If $A\cdot x\equiv B(\mathrm{mod}N),$ then $C\cdot A\cdot x\equiv C\cdot B(\mathrm{mod}N),$

Proof: $C\cdot A\cdot x-C\cdot B$

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

Simplify the congruence

Simplifying the congruence means reducing the value of $A$ as much as possible.

For example: $30121\cdot x\equiv 30394(\mathrm{mod}35893)$

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

Three values share a common prime factor $13.$

Therefore: $\frac{30121}{13}\cdot x\equiv \frac{30394}{13}(\mathrm{mod}\frac{35893}{13})$

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

$2317\cdot x\equiv 2338(\mathrm{mod}2761)$

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

Two values share a common prime factor $7.$

Therefore: $\frac{2317}{7}\cdot x\equiv \frac{2338}{7}(\mathrm{mod}2761)$

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

$331\cdot x\equiv 334(\mathrm{mod}2761)$

>>> x
64530
>>> (30121*x - 30394) % 35893
0
>>> (331*x - 334) % 2761
0

Template:RoundBoxTop Linear congruence $30121\cdot x\equiv 30394(\mathrm{mod}35893)$ has been reduced to $331\cdot x\equiv 334(\mathrm{mod}2761).$ Template:RoundBoxBottom

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 $x$ that satisfies the congruence.

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

Example 1

For example: $1327\cdot x\equiv -4539(\mathrm{mod}29)$ becomes in turn:

$22\cdot x\equiv 14(\mathrm{mod}29)$

$11\cdot x\equiv 7(\mathrm{mod}29)$

$33\cdot x\equiv 21(\mathrm{mod}29)$

$4\cdot x\equiv 21(\mathrm{mod}29)$

$28\cdot x\equiv 147(\mathrm{mod}29)$

$-1\cdot x\equiv 147(\mathrm{mod}29)$

$1\cdot x\equiv -147(\mathrm{mod}29)$

$1\cdot x\equiv 27(\mathrm{mod}29)$

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

Example 2

For example, solve $439\cdot x\equiv 2157(\mathrm{mod}2693)$

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

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

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

$\text{A = remainder = 59}$

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

$59\cdot x\equiv 523(\mathrm{mod}2693)$

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

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

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

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

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

Template:RoundBoxTop $\text{New value of}A$ is always $<=\frac{\text{Old value of}A}{2}.$ Template:RoundBoxBottom

$21\cdot x\equiv 2514(\mathrm{mod}2693)$

$7\cdot x\equiv 838(\mathrm{mod}2693)$

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

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

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

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

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

$2\cdot x\equiv 2163(\mathrm{mod}2693)$

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

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

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

$\text{A = remainder = 1}$

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

$1\cdot x\equiv 2428(\mathrm{mod}2693)$

Example 3

Method described here is algorithm used in python code below.

For example, solve the linear congruence:

$113\cdot x\equiv 263(\mathrm{mod}311)\dots (1).$

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

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

$311\cdot p\equiv -263(\mathrm{mod}113)$

$85\cdot p\equiv 76(\mathrm{mod}113)$

$(113-85)\cdot p\equiv (113-76)(\mathrm{mod}113)$

$28\cdot p\equiv 37(\mathrm{mod}113)$

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

$113\cdot q\equiv -37(\mathrm{mod}28)$

$1\cdot q\equiv 19(\mathrm{mod}28)$

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

From $(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 $A,N,$ it may be worthwhile to calculate $A\cdot x\equiv 1(\mathrm{mod}N).$

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

$A\cdot A^{\text{'}}\equiv 1(\mathrm{mod}N).$

$A$ and $A^{\text{'}}$ are modular inverses because their product is $\equiv 1(\mathrm{mod}N).$

For $A\cdot x\equiv B_0(\mathrm{mod}N).$

$A\cdot A^{\text{'}}\cdot x\equiv A^{\text{'}}\cdot B_0(\mathrm{mod}N).$

$1\cdot x\equiv A^{\text{'}}\cdot B_0(\mathrm{mod}N),$ and likewise for

$1\cdot x\equiv A^{\text{'}}\cdot B_1(\mathrm{mod}N),$

$1\cdot x\equiv A^{\text{'}}\cdot B_2(\mathrm{mod}N),$

$1\cdot x\equiv A^{\text{'}}\cdot B_3(\mathrm{mod}N).$

With N composite

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

Let $x_1$ be a solution of congruence $a\cdot x\equiv b(\mathrm{mod}n).$ Then, every solution of this congruence has form $x_1+K\cdot n.$

Solution $x_1+K\cdot n$ is also a solution of congruence $(1):$

$A\cdot (x_1+K\cdot n)\equiv B(\mathrm{mod}N).$

For example :

$63\cdot x\equiv 56(\mathrm{mod}77)$

$9\cdot x\equiv 8(\mathrm{mod}11)$

$2\cdot x\equiv 3(\mathrm{mod}11)$

$2\cdot x\equiv 3+11(\mathrm{mod}11)$

$x\equiv 7(\mathrm{mod}11)$

$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

Template:RoundBoxTop During testing on my computer with $N$ a random integer containing 10,077 decimal digits, length of stack was 13,514 and time to produce solution was about 13 seconds. Template:RoundBoxBottom

Exercises

Solve linear Diophantine equation.

With 2 unknowns

File:1008line01.png

Figure 1: Diagram illustrating linear Diophantine equation: $21613x+31013y=4095605616.$
In quadrant 1, both $x,y$ are positive.
In quadrant 1, there are 6 points for which both $x,y$ are type int.
In quadrants 2 and 4, there are an infinite number of points for which both $x,y$ are type int.
Line does not pass through quadrant 3.

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

Calculate all values of $x,y$ for which both $x,y$ are positive integers.

Put equation $(1)$ in form of congruence:

$ax+by=s$

$-by+s=ax$

$-by-(-s)=ax$

$-by\equiv -s(\mathrm{mod}a)$

$by\equiv s(\mathrm{mod}a)$

$31013y\equiv 4095605616(\mathrm{mod}21613)$

$9400y\equiv 6955(\mathrm{mod}21613)\dots (2)$

Solve congruence $(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)$ in form of congruence:

$ax+by=s$

$-ax+s=by$

$-ax-(-s)=by$

$-ax\equiv -s(\mathrm{mod}b)$

$ax\equiv s(\mathrm{mod}b)$

$21613x\equiv 4095605616(\mathrm{mod}31013)$

$21613x\equiv 28836(\mathrm{mod}31013)\dots (3)$

Solve congruence $(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+pa$

From congruence $(3):x=x_1+qb$

Put these values of $x,y$ in equation $(1):$

$a(x_1+qb)+b(y_1+pa)=s$

$a(x_1)+aqb+b(y_1)+bpa=s$

$aqb+bpa=s-(a(x_1)+b(y_1))$

$ab(q+p)=s-(a(x_1)+b(y_1))$

$p+q=\frac{s-(a(x_1)+b(y_1))}{ab}$

$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$ highlighted with $\text{****}$ are all positive, integer values of $x,y.$

With 3 unknowns

File:1012 2planes01.png

Figure 2. Intersection of 2 planes.
All integer values of $x,y,z$ calculated in this section are on line that is intersection of 2 planes:
${\pi }_1:2200013x+1600033y+2800033z=33420571802161$
${\pi }_2:y=710184$

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

Solve $(1)$ for integer values of $x,y,z.$

Put equation $(1)$ in form of congruence:

$2200013x+1600033y-33420571802161=-2800033z$

$2200013x+1600033y\equiv 33420571802161(\mathrm{mod}2800033)$

$2200013x+1600033y\equiv 2321520(\mathrm{mod}2800033)$

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

Solve $(2)$ for integer values of $x,y.$

$1600033y\equiv 2321520(\mathrm{mod}2200013)$

$y_1=710184$

$y=710184+p2200013$

From $(1):2200013x+1600033y+2800033z=33420571802161$

$2200013x+2800033z=33420571802161-1600033y$

Using $y=y_1:$

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

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

Solve $(3)$ for integer values of $x,z.$

$x_1=2283529$

$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)]

File:1011lineXZ01.png

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 $y=710184.$
There are exactly 5 points for which all of $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 $x,z$ highlighted with $\text{****}$ are all positive, integer values of $x,z.$ Template:RoundBoxBottom

Template:RoundBoxTop 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:

$2200013x+1600033y+2800033z=33420571802161\dots (1).$

$2800033$ is coefficient of $z.$

$2200013$ is coefficient of $x.$ Template:RoundBoxBottom There is not only an infinite number of points for which all of $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.$

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

#2

In this example:

• Plane ${\pi }_1$ is same as plane ${\pi }_1$ above.

• Plane ${\pi }_2$ is defined as: $y=9510236=710184+4\cdot 2200013.$

• π2:y=9510236.
  ${\pi }_2:y=9510236$.
• Intersection of π1,π2.
  $\text{Intersection of }{\pi }_1,{\pi }_2.$

#3

In this example:

• Plane ${\pi }_1$ is same as plane ${\pi }_1$ above.

• Plane ${\pi }_2$ is defined as: $z=-3464314.$

• π2:z=−3464314.
  ${\pi }_2:z=-3464314.$
• Intersection of π1,π2.
  $\text{Intersection of }{\pi }_1,{\pi }_2.$

Solve simultaneous linear congruences.

Given:

$x\equiv 7(\mathrm{mod}19)\dots (1)$

$x\equiv 25(\mathrm{mod}31)\dots (2)$

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

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

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

Combine $(3),(4):$

$7+19\cdot p=25+31\cdot q$

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

$19\cdot p-18=31\cdot q$

$19\cdot p\equiv 18(\mathrm{mod}31)$

$p\equiv 14(\mathrm{mod}31)$

$p=14+31\cdot r$

Substitute this value of $p$ into $(3):$

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

$x=7+19\cdot 14+19\cdot 31\cdot r$

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

Check:

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

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

Quadratic Congruences

Introduction

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

$x^2\equiv y(\mathrm{mod}N)$ or $x^2\equiv y^2(\mathrm{mod}N).$

Initially, let us consider the congruence: $x^2\equiv y(\mathrm{mod}N).$

If $y=x^2-N,$ then:

$x^2\equiv y(\mathrm{mod}N).$

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

Consider an example with real numbers.

Let $N=257$ and $26\ge x\ge 6.$

N = 257

$x$	$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$ indicates that the value $x^2-N$ is never divisible by $5.$

Proof: $N\equiv 2(\mathrm{mod}5)$ therefore $N-2=k5$ or $N=5k+2.$

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

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

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

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

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

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

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

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

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

Quadratic Residues

Consider all the congruences for prime number $5:$

$x^2\equiv y(\mathrm{mod}5)$ for $5>x\ge 0.$

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

Quadratic residues of $5$ are $0,1,4.$

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

To calculate the quadratic residues of a small prime $p:$

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

print (quadResidues(11))

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

Quadratic residues of $11$ are $0,1,3,4,5,9.$

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

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

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

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

From the table above:

N = 257

$x$	$x^2-N$
9	-176
13	-88
20	143
24	319

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

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

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

$x=20$ is $11\cdot 2-2.$

$x=24$ is $11\cdot 2+2.$

Products

This section uses prime number $41$ as an example.

Using quadResidues(p) quadratic residues of $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$ 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 $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 $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 $41,$ the product of residue and non-residue is non-residue. Advanced math proves that this is true for all primes.

Template:RoundBoxTop Some authors may consider $0$ as not a legitimate residue.

$0$ is not included as a residue in the test above. Template:RoundBoxBottom

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

$a^{\frac{p-1}{2}}\equiv \{\begin{array}{cc}1(\mathrm{mod}p)& \text{ if there is an integer }x\text{ such that }a\equiv x^2(\mathrm{mod}p),\\ -1(\mathrm{mod}p)& \text{ if there is no such integer.}\end{array}$

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

$\left(\frac{a}{p}\right)\equiv a^{\frac{p-1}{2}}(\mathrm{mod}p).$

$\left(\frac{a}{p}\right)=\{\begin{array}{cc}1& \text{if }a\text{ is a quadratic residue modulo }p\text{ and }a\equiv ̸0(\mathrm{mod}p),\\ -1& \text{if }a\text{ is a non-quadratic residue modulo }p,\\ 0& \text{if }a\equiv 0(\mathrm{mod}p).\end{array}$

It is known that $3$ is a quadratic residue modulo $11.$

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

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

It is known that $7$ is a quadratic non-residue modulo $11.$

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

# python code:
>>> (7**5) % 11
10

$10\equiv -1(\mathrm{mod}11)$

Python's decimal module provides a method for computing $(a^x)\mathrm{\%}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\equiv -1(\mathrm{mod}761838257287)$

Value $a=3456789$ is not a quadratic residue modulo $p=761838257287.$ Template:RoundBoxTop An exact square such as $1,4,9,16,25,\dots$ is always a quadratic residue modulo an odd prime $p.$ Template:RoundBoxBottom

Product of 2 residues

Let $a,b$ be quadratic residues modulo odd prime $p.$

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

Then:

$a^q\equiv 1(\mathrm{mod}p)$

$b^q\equiv 1(\mathrm{mod}p)$

By law of multiplication:

$(a^q)(b^q)\equiv (1)(1)(\mathrm{mod}p)$ or

$(a\cdot b{)}^q\equiv 1(\mathrm{mod}p)$

Product $(a\cdot b)$ of 2 quadratic residues $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 $N.$

$x^2\equiv y^2(\mathrm{mod}N)$

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

Integer $N$ always contains the factors $N,1,$ called trivial factors.

If $N$ contains two non-trivial factors $p,q,$ then:

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

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

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

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

A simple example:

We will use quadratic congruences to calculate factors of $N=4171$ for $164\ge x\ge 1.$

Right hand side exact square

One congruence produced an exact square for y:

$x$	$x^2$	$y=x^2-N$
70	4900	729

$4900\equiv 729(\mathrm{mod}N)$

$70^2\equiv 27^2(\mathrm{mod}N)$

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

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

Non-trivial factors of $4171$ are $43,97.$

Right hand side negative

Table below contains a sample of values of $x$ that produce negative $y:$

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

Non-trivial result 1

The congruences:

$x$	$x^2$	$y=x^2-N$
$$8	$$64	-4107$$**
64	4096	$$-75$$**

$64\equiv -4107(\mathrm{mod}N)$

$4096\equiv -75(\mathrm{mod}N)$

$64\cdot 4096\equiv -4107\cdot (-75)(\mathrm{mod}N)$

$262144\equiv 308025(\mathrm{mod}N)$

$512^2\equiv 555^2(\mathrm{mod}4171)$

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

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

Non-trivial factors of $4171$ are $43,97.$

Non-trivial result 2

The congruences:

$x$	$x^2$	$y=x^2-N$
11	121	-4050!!
61	3721	-450!!

$121\equiv -4050(\mathrm{mod}N)$

$3721\equiv -450(\mathrm{mod}N)$

$121\cdot 3721\equiv -4050\cdot (-450)(\mathrm{mod}N)$

$450241\equiv 1822500(\mathrm{mod}N)$

$671^2\equiv 1350^2(\mathrm{mod}4171)$

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

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

Non-trivial factors of $4171$ are $43,97.$

Right hand side positive

Table below contains a sample of values of $x$ that produce positive $y:$

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

Non-trivial result

The congruences:

$x$	$x^2$	$y=x^2-N$
65	4225	$$54$$**$$
89	7921	3750$$**!!

$4225\equiv 54(\mathrm{mod}N)$

$7921\equiv 3750(\mathrm{mod}N)$

$4225\cdot 7921\equiv 54\cdot 3750(\mathrm{mod}N)$

$33466225\equiv 202500(\mathrm{mod}N)$

$5785^2\equiv 450^2(\mathrm{mod}4171)$

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

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

Non-trivial factors of $4171$ are $43,97.$

Trivial result

The congruences:

$x$	$x^2$	$y=x^2-N$
$$89	$$7921	$$3750$$**!!
145	21025	16854$$!!

$7921\equiv 3750(\mathrm{mod}N)$

$21025\equiv 16854(\mathrm{mod}N)$

$7921\cdot 21025\equiv 3750\cdot 16854(\mathrm{mod}N)$

$166539025\equiv 63202500(\mathrm{mod}N)$

$12905^2\equiv 7950^2(\mathrm{mod}4171)$

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

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

This congruence produced the trivial factors of $4171.$

With 3 congruences

The congruences:

$x$	$x^2$	$y=x^2-N$
$$56	$$3136	-1035
$$59	$$3481	$$-690
145	21025	16854

$3136\equiv -1035(\mathrm{mod}N)$

$3481\equiv -690(\mathrm{mod}N)$

$21025\equiv 16854(\mathrm{mod}N)$

$3136\cdot 3481\cdot 21025\equiv -1035\cdot -690\cdot 16854(\mathrm{mod}N)$

$229517646400\equiv 12036284100(\mathrm{mod}N)$

$479080^2\equiv 109710^2(\mathrm{mod}4171)$

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

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

Non-trivial factors of $4171$ are $43,97.$

Links to related topics

Quadratic Residue

Modular Arithmetic

Leonhard Euler, Euler's Criterion

Adrien-Marie Legendre, Legendre Symbol

Carl Friedrich Gauss, Triple_bar or $\equiv$, Quadratic reciprocity

Carl Pomerance, Quadratic sieve

Greatest common divisor, Greatest common divisor (Example of Recursion)

Python's decimal Module