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:

 

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   are integers and  

This means that:

  • A modulo N equals B modulo N,
  • the difference, A-B, is exactly divisible by N, or
  •  

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

For example:   because division   is exact without remainder, or  

Similarly,   because division   is not exact, or  

Law of addition

edit

Adding a constant

edit

If   then:  

Proof:

 , therefore  

  which is exactly divisible by N.

Adding 2 congruences

edit

If   and   then:  

Proof:

 , therefore   and  

      which is exactly divisible by N.

Law of Common Congruence

edit

If   and

  then:

 

Proof:

  and  

  which is exactly divisible by N.

Law of Multiplication

edit

by a constant

edit

If   then:

 

Proof:

  which is exactly divisible by N.

by another congruence

edit

If   and

  then:

 

Proof:

  and  

        which is exactly divisible by N.

Law of squares

edit

If   then:

 

Proof:

  which is exactly divisible by N.

Law of Division?

edit

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

 

However  

Because   is not exactly divisible by  

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

Factor common to (A, B)

edit

Let  

If   share a common factor   then:

 

Provided that factor   does not divide   then:

 

Proof: division   is exact.

Factor   does not divide   therefore division   must be exact.

For example :  

 

 

Factor common to (A, B, N)

edit

If operands   all share a common factor   then:

  in which case:

 

Proof: division   is exact.

Therefore, division   must be exact.

For example:  

Therefore:  

Linear congruences

edit

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

  where   are integers and  

Law of addition

edit

If   then  

Proof is similar to that offered above.

Note that the congruence   is not valid, except for  

Generally:  

Proof:  

 

  which is exactly divisible by  

A corollary of this proof is:

 

Law of multiplication

edit

If   then  

Proof:  

  which is exactly divisible by  

Simplify the congruence

edit

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

For example:  

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

Three values share a common prime factor  

Therefore:  

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

 

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

Two values share a common prime factor  

Therefore:  

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

 

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

Linear congruence   has been reduced to  

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

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

Example 1

edit

For example:   becomes in turn:

 

 

 

 

 

 

 

 

Yes:  

Example 2

edit

For example, solve  

 

 

  therefore:

 

 


 

 

 

  therefore:

 

 

  is always  

 

 

 

 

  therefore:

 

 


 

 

 

  therefore:

 

 


 

Example 3

edit

Method described here is algorithm used in python code below.

For example, solve the linear congruence:

 

 

 

 

 

 

 

 

 

 

From  

From  

Check:

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

Modular Inverses

edit

If you have to perform many calculations with constant   it may be worthwhile to calculate  

Let   be a solution of this congruence. Then:

 

  and   are modular inverses because their product is  

For  

 

  and likewise for

 

 

 

With N composite

edit

When   is composite, it may happen that the process of simplifying the congruence   produces another congruence   where division   is exact.


Let   be a solution of congruence   Then, every solution of this congruence has form  

Solution   is also a solution of congruence  

 

For example :

 

 

 

 

 

 

# 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   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:  
In quadrant 1, both   are positive.
In quadrant 1, there are 6 points for which both   are type int.
In quadrants 2 and 4, there are an infinite number of points for which both   are type int.
Line does not pass through quadrant 3.

Given:  

Calculate all values of   for which both   are positive integers.


Put equation   in form of congruence:

 

 

 

 

 

 

 


Solve congruence  

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   in form of congruence:

 

 

 

 

 

 

 

Solve congruence  

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  

From congruence  

Put these values of   in equation  

 

 

 

 

 

 

# 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   highlighted with   are all positive, integer values of  

With 3 unknowns

edit
 
Figure 2. Intersection of 2 planes.
All integer values of   calculated in this section are on line that is intersection of 2 planes:
 
 

Given:  

Solve   for integer values of  


Put equation   in form of congruence:

 

 

 


Let  

Solve   for integer values of  

 

 

 


From  

 

Using  

  or:

 

Solve   for integer values of  

 

 

# 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  
There are exactly 5 points for which all of   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   highlighted with   are all positive, integer values of  

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:

 

  is coefficient of  

  is coefficient of  

There is not only an infinite number of points for which all of   are of type integer.

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

This example used  

However,   can be   where   is any integer.

More examples
edit

In this example:

  • Plane   is same as plane   above.
  • Plane   is defined as:  

In this example:

  • Plane   is same as plane   above.
  • Plane   is defined as:  

Solve simultaneous linear congruences.

edit

Given:

 

 

Calculate all values of   that satisfy both congruences  


From  

From  

Combine  

 

 

 

 

 

 


Substitute this value of   into  

 

 

  where   is type integer.


Check:

 

 

Quadratic Congruences

edit

Introduction

edit

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

  or  

Initially, let us consider the congruence:  

If   then:

 

Proof:   which is exactly divisible by  

Consider an example with real numbers.

Let   and  

N = 257
   
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   indicates that the value   is never divisible by  

Proof:   therefore   or  

The table shows all possible values of   and  

     
     
     
     
     
     

As you can see, the value   is never exactly divisible by  

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

However, you can see at least one value of   exactly divisible by   and at least one value of   exactly divisible by  

The table shows all possible values of   and  

     
          
       
          
           
      
      
      
      
      
     
      

The two lines marked by an   show values of   exactly divisible by   The two values of     and   or   are solutions of the congruence.

Why are values of   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  

  for  

     
0 0 0
1 1 1
2 4 4
3 9 4
4 16 1

Quadratic residues of   are  

Values   are not quadratic residues of   These values are quadratic non-residues.

To calculate the quadratic residues of a small prime  

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

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

If   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  

  therefore   is not a quadratic residue of   This is why   is never divisible by   exactly.

  therefore   is a quadratic residue of   and a value of   that satisfies the congruence   has form  

From the table above:

N = 257
   
9 -176
13 -88
20 143
24 319

These   values of   are exactly divisible by  

  is  

  is  

  is  

  is  

Products

edit

This section uses prime number   as an example.

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

Some authors may consider   as not a legitimate residue.

  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

 

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

 
 


It is known that   is a quadratic residue modulo  

Therefore   should be  

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

It is known that   is a quadratic non-residue modulo  

Therefore   should be  

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

Python's decimal module provides a method for computing   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')
 

Value   is not a quadratic residue modulo  

An exact square such as   is always a quadratic residue modulo an odd prime  

Product of 2 residues

edit

Let   be quadratic residues modulo odd prime  

Let  

Then:

 

 

By law of multiplication:

  or

 


Product   of 2 quadratic residues   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  

 

This means that the difference between the two squares is exactly divisible by  :  

Integer   always contains the factors   called trivial factors.

If   contains two non-trivial factors   then:

 

With a little luck   and   in which case:

  and   where

" " is function " "

A simple example:

edit

We will use quadratic congruences to calculate factors of   for  

Right hand side exact square

edit

One congruence produced an exact square for y:

     
70 4900 729
 
 

     

     


Non-trivial factors of   are  

Right hand side negative

edit

Table below contains a sample of values of   that produce negative  

     
 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:

     
 8  64 -4107 **
64 4096  -75 **
 
 
 
 
 

     

     

Non-trivial factors of   are  

Non-trivial result 2
edit

The congruences:

     
11 121 -4050!!
61 3721 -450!!
 
 
 
 
 

     

     

Non-trivial factors of   are  

Right hand side positive

edit

Table below contains a sample of values of   that produce positive  

     
 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
edit

The congruences:

     
65 4225  54 ** 
89 7921 3750 **!!
 
 
 
 
 

     

     

Non-trivial factors of   are  

Trivial result
edit

The congruences:

     
 89  7921  3750 **!!
145 21025 16854 !!
 
 
 
 
 

     

     

This congruence produced the trivial factors of  

With 3 congruences

edit

The congruences:

     
 56  3136 -1035
 59  3481  -690
145 21025 16854
 
 
 
 
 
 

   

   


Non-trivial factors of   are  

Links to related topics

edit

Quadratic Residue

Modular Arithmetic

Leonhard Euler, Euler's Criterion

Adrien-Marie Legendre, Legendre Symbol

Carl Friedrich Gauss, Triple_bar or  , Quadratic reciprocity

Carl Pomerance, Quadratic sieve

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

Python's decimal Module