import numpy as np
from fractions import Fraction as frac
import sympy as sy

#matrix= [[3,-3,1,2,0,3],
 #       [0,-2,3,-2,2,1],
  #      [-2,2,3,0,-2,3],
   #     [2,3,-3,1,-2,3],
    #    [2,0,-2,-3,2,0]]

matrix= [[1,-2,-2,-2,-1,2],
        [0,3,-2,-3,1,3],
        [3,0,0,1,-1,2],
        [3,-3,-2,0,1,1],
        [0,-3,3,-3,-3,2]]

#n = 2497969412496091
n=2497969412496091


#computes EEA
def EEA(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		gcd, u, v = EEA(b % a, a)
		return (gcd, v - (b//a) * u, u)

#Method that takes an element pos and number n and multiply them togheter mod m
def generateElement(pos,n,m):
    return (pos * n) % m

#Method that takes a matrix A, and computes its row echelon form
def row_echelon(A):
    counter=0
    #loop through every row and make that one row, row reduced
    for row in A:
        tempCounter = 0
        gcd, u, v = EEA(n, row[counter])
        if gcd != 1:
            print(gcd, "Is a factor :)")
            break

        #If leading coefficient already is not 1, then make it into one by using EEA to calculate the number in which the  (coefficient*v)%n=1
        ##the rest of the elements in the same row will also need to be adjusted, depending on the v
        if (row[counter] != 1):
            newRow=[]
            for g in range(0, len(row)):
                newRow.append(0)

            for element in row:
                newLeader = generateElement(element, v, n)
                newRow[tempCounter] = newLeader
                tempCounter += 1
            A[counter] = newRow

        ##after making the leading coefficient 1, make every element under it 0
        ##this is done by multiplying the row belonging to the current leading coefficient by the leading coefficient in the row you want to reduce to 0
        ##then
        for bellowCoefficient in range(counter + 1, len(A)):
            tempCounter2 = 1 + counter
            row = A[bellowCoefficient]
            if (row[counter] == 0):
                continue
            else:
                minusRow = []
                minusRowLeadingCoefficient = row[counter]
                for leadingCoeffcientRowElement in A[counter]:
                    minusRow.append((leadingCoeffcientRowElement * minusRowLeadingCoefficient) % n)
                tempRow = []
                for iterateCounter in range(0, len(minusRow)):
                    tempRow.append((minusRow[iterateCounter] - row[iterateCounter]) % n)
            A[bellowCoefficient] = tempRow
            tempCounter2 += 1

        counter+=1

    print("Row reduced ")
    printMatrix(A)
    return A


##support method that prints a matrix, in a nice readable way
def printMatrix(M):
    for row in M:
        print(row)
    print("\n")

##dont mind this method too mutch, it was an atempt to check the general solution and then use it too double check if my answer was correct.
##Not sure if either my original reduction is wrong or if my coded check is wrong :)
def generalSolution(modulaResult):
    x5 = 0
    x4 = 0
    x3 = 0
    x2 = 0
    x1 = 0

    matrix = [[1, -2, -2, -2, -1, 2],
              [0, 3, -2, -3, 1, 3],
              [3, 0, 0, 1, -1, 2],
              [3, -3, -2, 0, 1, 1],
              [0, -3, 3, -3, -3, 2]]
    #matrix = [[3, -3, 1, 2, 0, 3],
     #         [0, -2, 3, -2, 2, 1],
      #        [-2, 2, 3, 0, -2, 3],
       #       [2, 3, -3, 1, -2, 3],
        #      [2, 0, -2, -3, 2, 0]]

    counterX = 0
    print("Starting general solution: ")
    for i in range(0, 5):
        # print(modulaResult[4-counterX])
        # lmao=modulaResult[4-counterX][5-counterX]
        if (i == 0):
            x5 = modulaResult[4 - counterX][5 - counterX]
            #print(x5)
        if (i == 1):
            x4 = (modulaResult[4 - counterX][5] - (modulaResult[4 - counterX][5 - counterX] * x5) % n) % n
            #print(x4)
        if (i == 2):
            # x3=(modulaResult[4-counterX][5-counterX]-(x4*modulaResult[4-counterX][4])%n-(x5*modulaResult[4-counterX][5])%n)%n
            x3 = (modulaResult[4 - counterX][5] - (x4 * modulaResult[4 - counterX][5 - counterX]) % n - (
                        x5 * modulaResult[4 - counterX][4]) % n) % n
            #print(x3)
        if (i == 3):
            # x2=(modulaResult[4-counterX][5-counterX]-(x3*modulaResult[4-counterX][3])%n-(x4*modulaResult[4-counterX][4])%n-(x5*modulaResult[4-counterX][5])%n)%n
            x2 = (modulaResult[4 - counterX][5] - (x3 * modulaResult[4 - counterX][5 - counterX]) % n - (
                        x4 * modulaResult[4 - counterX][3]) % n - (x5 * modulaResult[4 - counterX][4]) % n) % n
            #print(x2)
        if (i == 4):
            # x1=modulaResult[4-counterX][5-counterX]-
            x1 = (modulaResult[4 - counterX][5] - (x2 * modulaResult[4 - counterX][5 - counterX]) % n - (
                        x3 * modulaResult[4 - counterX][2]) % n - (x4 * modulaResult[4 - counterX][3]) % n - (
                              x5 * modulaResult[4 - counterX][4]) % n) % n
           # print(x1)
            #print(n/x1)
        counterX += 1

    #tempX1=0
    #tempTestMatrix=[]
    #for i in range(0, len(matrix)):
    #    tempTestMatrix.append(0)

    #counterX = 0
    #for i in range(0, len(matrix)):
     #   tempX1= (modulaResult[4 - counterX][5] - (x2 * modulaResult[4 - counterX][5 - counterX]) % n - (
      #                  x3 * modulaResult[4 - counterX][2]) % n - (x4 * modulaResult[4 - counterX][3]) % n - (
       #                       x5 * modulaResult[4 - counterX][4]) % n) % n


    xMatrix=[]
    print("\n")
    print("x1", x1)
    print("x2", x2)
    print("x3", x3)
    print("x4", x4)
    print("x5", x5)
    xMatrix.append(x1)
    xMatrix.append(x2)
    xMatrix.append(x3)
    xMatrix.append(x4)
    xMatrix.append(x5)

    check=[]

    print("\nTesting the X values found to double check: \n")
    counter = 1
    for row in matrix:
        z = 0
        result = 0
        for element in row:
            if z == len(row)-1:
                break
            result+=(element*xMatrix[z])%n
            result=result%n
            z+=1
        print("Result for row", counter,":" , result)
        counter+=1

##driver method everything starts from here
def main():
    print("Original matrix")
    printMatrix(matrix)
    matrix3 = row_echelon(matrix)
    generalSolution(matrix3)

main()