######################################################################
# FONCTIONS DISPONIBLES - RAPPEL DE SYNTAXE (BASIQUES, MATH, SYMPY)
######################################################################

# --- Fonctions de base ---
pow(a, n, m)        # calcul optimisé de a^n mod m
m // n              # quotient de la division euclidienne de m par n
m % n               # reste de la division euclidienne de m par n
(m % n == 0)        # teste si m est multiple de n

# --- Module math ---
from math import *
gcd(m, n)           # PGCD de m et n
lcm(m, n)           # PPCM de m et n
(gcd(m, n) == 1)    # teste si m et n sont premiers entre eux

# --- Module sympy ---
from sympy import *
binomial(n, k)      # coefficient binomial
divisors(n)         # liste de tous les diviseurs de n
factorint(n)        # décomposition en facteurs premiers
factorial(n)        # factorielle
mod_inverse(a, m)   # inverse modulaire
isprime(n)          # teste si n est premier
prime(n)            # n-ième nombre premier
nextprime(n)        # premier nombre premier supérieur à n
prevprime(n)        # premier nombre premier inférieur à n
totient(n)          # indicatrice d'Euler


######################################################################
# PETIT THÉORÈME DE FERMAT - CONTRE-EXEMPLES À LA RÉCIPROQUE (NOMBRES DE CARMICHAEL)
######################################################################

from sympy import *

C = [] # liste de nombres composés

for n in range(301, 3001, 2):
    if(not isprime(n)):
        C.append(n)

for n in C:
    contre_ex = True
    for a in range(1, n):
        if(pow(a, n, n) != a):
            contre_ex = False
            break
    if(contre_ex):
        print(n)


######################################################################
# ALGORITHME D'EUCLIDE - CALCUL DÉTAILLÉ DU PGCD DE 364 ET 63
######################################################################

a, b = 364, 63

while(a%b!=0):
    print(f"{a} = {a//b}*{b} + {a%b}")
    a, b = b, a%b

print(f"Le PGCD vaut {b}.")


######################################################################
# ALGORITHME D'EUCLIDE - VERSION HISTORIQUE (DIFFÉRENCES SUCCESSIVES)
######################################################################

a, b = 364, 63       # a > 0, b > 0

while(a!=b):
    if(a>b):
        a = a-b
    else:
        b = b-a

print(a)


######################################################################
# ALGORITHME D'EUCLIDE - VERSION RÉCURSIVE
######################################################################

def pgcd(a, b): return a if b == 0 else pgcd(b, a%b)

print(pgcd(364, 63))


######################################################################
# COEFFICIENTS DE BÉZOUT - CALCUL DIRECT, CODE ITÉRATIF
######################################################################

a, b = 141, 34
R = [a, b]
Q, U, V = ["", ""], [1, 0], [0, 1]

while (b!=0):
    q = a // b
    Q.append(q)
    R.append(a%b)
    U.append(U[-2] - q*U[-1])
    V.append(V[-2] - q*V[-1])
    print(f"{a} = {q}*{b} + {a%b}")
    a, b = b, a%b

print("\nn", "q", "r_n", "u_n", "v_n", sep='\t|\t')

for n in range(len(Q)-1):
    print(n, Q[n], R[n], U[n], V[n], sep='\t|\t')

print(f"\nD'où : {R[0]}*{U[-2]} + {R[1]}*{V[-2]} = {R[-2]}")


######################################################################
# COEFFICIENTS DE BÉZOUT - CODE RÉCURSIF
######################################################################

def bezout(a, b):
    if(b==0):
        return a, 1, 0
    d, u, v = bezout(b, a%b)
    return d, v, u-(a//b)*v

print(bezout(141, 34))


######################################################################
# RESTES CHINOIS - RÉSOLUTION D'UN SYSTÈME DE CONGRUENCES
######################################################################

import numpy as np

def bezout(a,b):
    if(b==0):
        return a, 1, 0
    d, u, v = bezout(b,a%b)
    return (d, v, u-(a//b)*v)

A, N = [3, 1, 4], [5, 7, 11]
k, n = len(A), np.prod(N)

Q = [n//N[i] for i in range(k)]
Y = [bezout(Q[i],N[i])[1] for i in range(k)]  #2e argumt

x = 0
sol = "x = "    # expression d'une solution

for i in range(k):
    x += (Q[i]*Y[i]*A[i])
    sol += f"{Q[i]}*{Y[i]}*{A[i]} + "

print(f"{sol[0:-3]} = {x%n} [{n}]")


######################################################################
# SOLUTIONS - BIDONS DE 17 ET 26 LITRES
######################################################################

for k in range(100):
    if(1000-17*k>0 and 26*k-1500>0):
        print(k, 1000-17*k, 26*k-1500)

# Renvoie -> 58 14 8


######################################################################
# SOLUTIONS - COEFFICIENTS DE BÉZOUT : CALCUL EN DEUX TEMPS, VERSION ITÉRATIVE
######################################################################

a, b = 141, 34
A, B, Q = [a], [b], []

while (b != 0):
    Q.append(a // b)
    print(f"{a} = {a//b}*{b} + {a%b}")
    a, b = b, a % b
    A.append(a)
    B.append(b)

d, u, v = a, 1, 0
N = len(Q)
print(" ")

for n in range(N):
    u, v = v, u-Q[N-1-n]*v
    print(f"{d} = {A[N-1-n]}*{u} + {B[N-1-n]}*{v}")


######################################################################
# SOLUTIONS - RESTES CHINOIS : VÉRIFICATION (À AJOUTER À LA FIN DU CODE PRÉCÉDENT)
######################################################################

for i in range(k):
    print(f"{x%n} = {x%N[i]} [{N[i]}]")