Théorie des nombres

Algorithme d'Euclide pour le PGCD

Soient deux entiers positisf \(m,n\) avec \(m > n\). Le plus grand commun diviseur \(\gcd(m,n)\) satisfait la propriété \(\gcd(m,n) = \gcd(n, m \mod n)\).

Cette propriété permet de calculer le PGCD par réduction successive jusqu'à obtenir un reste nul.

def pgcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

Algorithme d'Euclide étendu

Le lemme de Bézout stipule que l'équation \(ax + by = c\) admet des solutions entières si et seulement si \(\gcd(a,b)\) divise \(c\). L'algorithme étendu fournit une solution particulière pour le cas \(ax + by = \gcd(a,b)\).

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

Inverse modulaire

L'inverse modulo \(p\) d'un entier \(x\) vérifie \(x \cdot y \equiv 1 \pmod{p}\). Il peut être déterminé via l'algorithme d'Euclide étendu lorsque \(\gcd(x,p) = 1\).

Crible d'Ératosthène

Le crible classique marque les multiples de chaque nombre premier trouvé. Sa complexité est \(O(n \log \log n)\).

def crible(n):
    est_premier = [True] * (n + 1)
    for i in range(2, int(n**0.5) + 1):
        if est_premier[i]:
            for j in range(i*i, n + 1, i):
                est_premier[j] = False
    return [i for i in range(2, n + 1) if est_premier[i]]

Crible linéaire (d'Euler)

Cette méthode garantit que chaque composé est marqué une seule fois par son plus petit facteur premier, assurant une complexité \(O(n)\).

def crible_euler(n):
    premiers = []
    plus_petit_facteur = [0] * (n + 1)
    for i in range(2, n + 1):
        if plus_petit_facteur[i] == 0:
            plus_petit_facteur[i] = i
            premiers.append(i)
        for p in premiers:
            if p > plus_petit_facteur[i] or p * i > n:
                break
            plus_petit_facteur[p * i] = p
    return premiers

Mathématiques

Exponentiation rapide

Le calcul de \(a^b\) modulo \(m\) s'effectue en décomposant l'exposant en binaire, réduisant la complexité à \(O(\log b)\).

def puissance_mod(base, exp, mod):
    resultat = 1
    base %= mod
    while exp > 0:
        if exp % 2 == 1:
            resultat = (resultat * base) % mod
        exp = exp >> 1
        base = (base * base) % mod
    return resultat

Espérance mathématique

L'espérance d'une variable aléatoire discrète est la somme des produits de chaque valeur par sa probabilité.

Algèbre linéaire

Matrice et déterminant

Le déterminent d'une matrice triangulaire supérieure est le produit des éléments diagonaux. Il peut être obtenu par élimination de Gauss.

Élimination de Gauss

La méthode de Gauss résout des systèmes linéaires en transformatn la matrice augmentée en forme échelonnée réduite.

import numpy as np

def gauss_jordan(A, b):
    n = len(b)
    M = np.hstack([A.astype(float), b.reshape(n, 1)])
    
    for col in range(n):
        # Pivot partiel
        max_row = np.argmax(np.abs(M[col:, col])) + col
        M[[col, max_row]] = M[[max_row, col]]
        
        # Élimination
        pivot = M[col, col]
        M[col] = M[col] / pivot
        for ligne in range(n):
            if ligne != col:
                facteur = M[ligne, col]
                M[ligne] -= facteur * M[col]
    
    return M[:, -1]

Mathématiques combinatoires

Théorème binomial

Le développement de \((x + y)^n\) correspond au nombre de façons de choisir \(k\) termes \(x\) parmi \(n\) facteurs.

Nombres de Stirling

Les nombres de Stirling de première espèce comptent les permutations de \(n\) éléments avec \(m\) cycles. Les nombres de deuxième espèce comptent les partitions d'un ensemble de \(n\) éléments en \(m\) sous-ensembles non vides.

Analyse

Sujet à compléter ultérieurement.