Congruences edit

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{\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 $A,B,N$ are integers and $N>1.$

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{\pmod {5}}$ because division ${\frac {23-8}{5}}$ is exact without remainder, or $5\mid (23-8).$

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

Law of addition edit

Adding a constant edit

If $A\equiv B{\pmod {N}},$ then: $A+q\equiv B+q{\pmod {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.

Adding 2 congruences edit

If $A\equiv B{\pmod {N}},$ and $C\equiv D{\pmod {N}},$ then: $A+C\equiv B+D{\pmod {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.

Law of Common Congruence edit

If $A\equiv B{\pmod {N}}$ and

$C\equiv B{\pmod {N}},$ then:

$A\equiv C{\pmod {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.

Law of Multiplication edit

by a constant edit

If $A\equiv B{\pmod {N}}$ then:

$A\cdot p\equiv B\cdot p{\pmod {N}}.$

Proof:

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

by another congruence edit

If $A\equiv B{\pmod {N}}$ and

$C\equiv D{\pmod {N}},$ then:

$A\cdot C\equiv B\cdot D{\pmod {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.

Law of squares edit

If $A\equiv B{\pmod {N}}$ then:

$A^{2}\equiv B^{2}{\pmod {N}}.$

Proof:

$A^{2}-B^{2}=(A+B)(A-B)$ which is exactly divisible by N.

Law of Division? edit

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

$24\equiv 14{\pmod {10}}.$

However ${\frac {24}{2}}\not \equiv {\frac {14}{2}}{\pmod {10}}$

Because $12-7=5$ is not exactly divisible by $10$

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

Factor common to (A, B) edit

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

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

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

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

$a\equiv b{\pmod {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{\pmod {55}}$

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

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

Factor common to (A, B, N) edit

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

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

$a\equiv b{\pmod {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{\pmod {55}}.$

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

Linear congruences edit

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

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

Law of addition edit

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

Proof is similar to that offered above.

Note that the congruence $(A+C)\cdot x\equiv B+C{\pmod {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){\pmod {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\%N)\cdot (x\%N)\equiv (B\%N){\pmod {N}}.$

Law of multiplication edit

If $A\cdot x\equiv B{\pmod {N}},$ then $C\cdot A\cdot x\equiv C\cdot B{\pmod {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 edit

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

For example: $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.$

Therefore: ${\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\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.$

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

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

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

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

Linear congruence $30121\cdot x\equiv 30394{\pmod {35893}}$ has been reduced to $331\cdot x\equiv 334{\pmod {2761}}.$

Python code edit

# 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$ 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 edit

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

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

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

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

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

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

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

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

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

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

Example 2 edit

For example, solve $439\cdot x\equiv 2157{\pmod {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}})\%{\text{N}}=523$

$59\cdot x\equiv 523{\pmod {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))\%{\text{N}}=2514$

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

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

$7\cdot x\equiv 838{\pmod {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))\%{\text{N}}=2163$

$2\cdot x\equiv 2163{\pmod {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}})\%{\text{N}}=2428$

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

Example 3 edit

Method described here is algorithm used in python code below.

For example, solve the linear congruence:

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

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

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

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

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

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

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

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

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

$1\cdot q\equiv 19{\pmod {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 edit

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

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

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

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

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

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

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

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

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

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

With N composite edit

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

Let $x_{1}$ be a solution of congruence $a\cdot x\equiv b{\pmod {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{\pmod {N}}.$

For example :

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

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

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

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

$x\equiv 7{\pmod {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 edit

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$ a random integer containing 10,077 decimal digits, length of stack was 13,514 and time to produce solution was about 13 seconds.

Exercises edit

Solve linear Diophantine equation. edit

With 2 unknowns edit

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{\pmod {a}}$

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

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

$9400y\equiv 6955{\pmod {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{\pmod {b}}$

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

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

$21613x\equiv 28836{\pmod {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 edit

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{\pmod {2800033}}$

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

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

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

$1600033y\equiv 2321520{\pmod {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\_$ 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)]

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

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

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.

More examples edit

#2 edit

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

$\pi _{2}:y=9510236$ .
${\text{Intersection of }}\pi _{1},\pi _{2}.$

#3 edit

In this example:

Plane $\pi _{1}$ is same as plane $\pi _{1}$ above.

Plane $\pi _{2}$ is defined as: $z=-3464314.$

$\pi _{2}:z=-3464314.$
${\text{Intersection of }}\pi _{1},\pi _{2}.$

Solve simultaneous linear congruences. edit

Given:

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

$x\equiv 25{\pmod {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{\pmod {31}}$

$p\ \equiv 14{\pmod {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)\ \%\ 19=7+0=7.$

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

Quadratic Congruences edit

Introduction edit

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

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

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

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

$x^{2}\equiv y{\pmod {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\geq x\geq 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{\pmod {5}}$ therefore $N-2=k5$ or $N=5k+2.$

The table shows all possible values of $x\ \%\ 5$ and $y\ \%\ 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\ \%\ 11$ and $y\ \%\ 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 edit

Consider all the congruences for prime number $5:$

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

$x$	$x^{2}$	$(x^{2})\ \%\ 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\ \%\ 5=2,$ therefore $N$ is not a quadratic residue of $5.$ This is why $x^{2}-N$ is never divisible by $5$ exactly.

$N\ \%\ 11=4,$ therefore $N$ is a quadratic residue of $11$ and a value of $x$ that satisfies the congruence $x^{2}\equiv 4{\pmod {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 edit

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 edit

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 edit

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 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,$ 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$ as not a legitimate residue.

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

Euler's criterion edit

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^{\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:

\left({\frac {a}{p}}\right)\equiv a^{\tfrac {p-1}{2}}{\pmod {p}}.

\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$ is a quadratic residue modulo $11.$

Therefore $(3^{5})\ \%\ 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})\ \%\ 11$ should be $-1.$

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

10\equiv -1{\pmod {11}}

Python's decimal module provides a method for computing $(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\equiv -1{\pmod {761838257287}}

Value $a=3456789$ is not a quadratic residue modulo $p=761838257287.$

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

Product of 2 residues edit

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

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

Then:

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

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

By law of multiplication:

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

$(a\cdot b)^{q}\equiv 1{\pmod {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 edit

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}{\pmod {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: edit

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

Right hand side exact square edit

One congruence produced an exact square for y:

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

4900\equiv 729{\pmod {N}}

70^{2}\equiv 27^{2}{\pmod {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 edit

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 edit

The congruences:

$x$	$x^{2}$	$y=x^{2}-N$
$\ \$ `8`	$\ \ \ \$ `64`	`-4107` $\ \$ `**`
`64`	`4096`	$\ \ \ \$ `-75` $\ \$ `**`

64\equiv -4107{\pmod {N}}

4096\equiv -75{\pmod {N}}

64\cdot 4096\equiv -4107\cdot (-75){\pmod {N}}

262144\equiv 308025{\pmod {N}}

512^{2}\equiv 555^{2}{\pmod {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 edit

The congruences:

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

121\equiv -4050{\pmod {N}}

3721\equiv -450{\pmod {N}}

121\cdot 3721\equiv -4050\cdot (-450){\pmod {N}}

450241\equiv 1822500{\pmod {N}}

671^{2}\equiv 1350^{2}{\pmod {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 edit

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` $\ \ \ \ \ \ \ \ \ \$