Équations de congruence linéaires

L'équation de congruence de base s'exprime sous la forme \(ax \equiv c \pmod b\). Cette expression est mathématiquement équivalente à l'existence d'un entier \(y\) tel que :

\[ax + by = c\]

Cette forme est une équation diophantienne linéaire, laquelle peut être résolue efficacement en utilisant l'algorithme d'Euclide étendu (Etxended GCD).

long long extended_gcd(long long a, long long b, long long &x, long long &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    long long g = extended_gcd(b, a % b, y, x);
    y -= (a / b) * x;
    return g;
}

L'inverse modulaire

Si \(ax \equiv 1 \pmod p\) et que \(a\) et \(p\) sont premiers entre eux (\(\text{pgcd}(a, p) = 1\)), on dit que \(x\) est l'inverse modulaire de \(a\) modulo \(p\), souvent noté \(a^{-1}\) ou \(\text{inv}(a)\).

Méthodes de calcul :

1. Algorithme d'Euclide étendu : Utilisé pour résoudre \(ax + py = 1\). C'est la méthode la plus générique pour un seul nombre.
2. Petit théorème de Fermat : Si \(p\) est un nombre premier, alors \(a^{p-2} \equiv a^{-1} \pmod p\).
3. Approche par récurrence linéaire : Idéal pour calculer tous les inverses de \(1\) à \(n\) en \(O(n)\).

Pour la méthode linéaire, on utilise la relation suivante basée sur la division euclidienne de \(p\) par \(i\) (\(p = ki + r\)) :

\[ \text{inv}[i] = (p - \lfloor p/i \rfloor) \cdot \text{inv}[p \bmod i] \pmod p \]

Théorème des restes chinois (Version étendue)

Le théorème des restes chinois traite des systèmes d'équations de congruences linéaires. Dans sa version étendue (EXCRT), les modules \(m_i\) ne sont pas nécessairement premiers entre eux deux à deux.

Le système se présente ainsi :

\[\begin{cases} x \equiv a_1 \pmod{m_1} \\ x \equiv a_2 \pmod{m_2} \\ \vdots \\ x \equiv a_n \pmod{m_n} \end{cases}\]

Algorithme de résolution

On procède par induction :

1. Soit \(x_{k-1}\) une solution pour les \(k-1\) premières équations. La solution générale est \(x_{k-1} + t \cdot M\), où \(M = \text{ppcm}(m_1, \dots, m_{k-1})\).
2. On cherche \(t\) tel que \(x_{k-1} + t \cdot M \equiv a_k \pmod{m_k}\).
3. On résout cette congruence pour \(t\) via l'algorithme d'Euclide étendu. Si aucune solution n'existe, le système est insoluble.

#include <iostream>

typedef __int128_t int128;

int128 compute_gcd(int128 a, int128 b) {
    return b == 0 ? a : compute_gcd(b, a % b);
}

int128 extended_euclidean(int128 a, int128 b, int128 &u, int128 &v) {
    if (b == 0) { u = 1; v = 0; return a; }
    int128 d = extended_euclidean(b, a % b, v, u);
    u -= (a / b) * v;
    return d;
}

void solve_excrt() {
    int n;
    if (!(std::cin >> n)) return;
    
    long long m_in, a_in;
    std::cin >> m_in >> a_in;
    int128 M = m_in, ans = a_in;

    for (int i = 1; i < n; ++i) {
        std::cin >> m_in >> a_in;
        int128 mi = m_in, ai = a_in;
        int128 x, y;
        int128 c = (ai - ans % mi + mi) % mi;
        int128 gcd_val = extended_euclidean(M, mi, x, y);

        if (c % gcd_val != 0) {
            // Pas de solution
            return;
        }

        int128 mod_val = mi / gcd_val;
        x = (x * (c / gcd_val)) % mod_val;
        ans += x * M;
        M *= mod_val;
        ans = (ans % M + M) % M;
    }
    std::cout << (long long)ans << std::endl;
}

Fonction Indicatrice d'Euler

La fonction \(\varphi(n)\) définit le nombre d'entiers positifs inférieurs à \(n\) qui sont premiers avec \(n\).

• Propriété 1 : Si \(p\) est premier, \(\varphi(p^k) = p^k - p^{k-1} = p^k(1 - 1/p)\).
• Propriété 2 : La fonction est multiplicative : si \(\text{pgcd}(a, b) = 1\), alors \(\varphi(ab) = \varphi(a)\varphi(b)\).
• Formule générale : Pour \(n = \prod p_i^{\alpha_i}\), on a \(\varphi(n) = n \prod_{i=1}^k (1 - \frac{1}{p_i})\).

Théorème d'Euler

Si \(a\) et \(m\) sont premiers entre eux (\(\text{pgcd}(a, m) = 1\)), alors :

\[a^{\varphi(m)} \equiv 1 \pmod m\]

Ce théorème permet de réduire les puissances importantes. Pour tout \(b \geq \varphi(m)\), on peut utiliser la généralisation :

\[a^b \equiv a^{b \pmod{\varphi(m)} + \varphi(m)} \pmod m\]