Autor: Nicholas Onică, elev la “Colegiul Național de Informatică Tudor Vianu”

Introducere

Legenda spune că era un chinez în jurul secolelor 3-5 I.Hr. care și-a propus să rezolve o problemă care îi dădea bătăi de cap. Să spunem că așezăm un număr de boabe de orez în grămezi a câte 3, vom rămâne cu 2 boabe. Dacă le așezăm în grămezi a câte cinci, vom rămâne cu 3 boabe. Iar dacă le așezăm în grămezi a câte 7 vom rămâne cu 2 boabe. Cum ne putem da seama câte boabe de orez avem în total.

Se pare că această poveste dezvăluie rădăcinile teoremei chinezești a resturilor. Prima scriere responsabilă pentru abordarea acestui subiect îi revine lui Sun Tzu în cartea ”Sunzi Suanjing” (manualul matematic al maestrului Sun), autor cunoscut și pentru faimoasa carte ”Arta Războiului”. Ideile au urmat să fie prelucrate de mai mulți matematicieni de-a lungul anilor, ca mai apoi prin secolele 18-19 Carl Friedrich Gauss să ofere o demonstrație concretă a teoremei, urmată de utilizări în teoria numerelor.

În zilele noastre printre cele mai importante aplicații se numără criptografia, algoritmica și teoria numerelor.

Enunț

Fie sistemul:
x ≡ r1 mod m1
x ≡ r2 mod m2
x ≡ r3 mod m3
.
.
.
x ≡ rn mod mn


Unde m_{1},m_{2},…,m_{3} sunt numere întregi prime între ele, două câte două, iar r_{1},r_{2},…,r_{n} sunt numere întregi, există și este posibil de identificat un număr întreg x, soluție a sistemului.

Demonstrație

Mai întâi trebuie să definim câteva noțiuni:

• Vom nota y_{mi}^{-1} inversul modular al lui y în raport cu mi

• Notăm M = m_{1}* m_{2}* …* m_{3}

• Notăm M_{i} = \frac{M}{m_{i}}

• În final notăm (pentru simplitate) cu ci = Mi ∗ M^{-1}_{i_{m_{i}}

Acum haideți să ne gândim cum ajungem de la resturile r_{1}, r_{2}, …, r_{n} la numărul x. Știm că \forall i \in {1, 2, …, n}, c_{i} \equiv 1 \bmod m_{i}. Observăm că atât x cât și r_{i} * c_{i} sunt \equiv r_{i} \bmod m_{i}. De asemenea, pentru \forall i, j \in {1, 2, …, n}; j \ne i, c_{j} \equiv 0 \bmod m_{i}.

Astfel, putem să găsim o soluție pentru x(x_{1}) în funcție de resturile din enunț, însumând toate relațiile sub forma obținută mai sus:
x_{1} = \sum_{k=1}^{n} r_{k} * c_{k}

În plus, putem vedea că x poate avea o infinitate de soluții atât timp cât aparține mulțimii:
S = {x_{1} + k * M \mid k \in \mathbb{Z}}

Generalizare

Orice relație de tipul:
x \equiv y \pmod{m_{i}} \forall i \in \mathbb{N}
Este validă dacă și numai dacă: x \equiv y \pmod{M} Astfel, sistemul poate fi rezolvat și dacă modulele nu sunt prime între ele, cu condiția: m_{i} \equiv m_{j} \pmod{\text{cmmmc}(m_{i}, m_{j})} \forall i \in \mathbb{N}
Tot din această condiție rezultă că M va fi de forma M = \text{cmmmc}(m_{1}, m_{2}, …, m_{n})

Cod Sursă

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
//ne declaram variabilele
int n,c[1000],m[1000];
long long M=1,X[1000],X_inv[1000];
long long sol=0;

void invers_modular(long long a, long long b,int &x,int &y) //deoarece nu stim sigur ca toate modulele sunt prime, vom folosi algoritmul extins al lui euclid in complexitate O(log(min(a,b)))
{
    if(b==0)
    {
        x=1;
        y=1;
    }
    else
    {
        int cop_x,cop_y;
        invers_modular(b,a%b,cop_x,cop_y);
        x=cop_y;
        y=cop_x-a/b*cop_y;
    }
}
int main()
{
    //presupunem ca avem un sistem modular cu sol congruent cu c[i] mod m[i], unde 1<=i<=n si oricare 1<=i<j<=n, cmmdc(m[i],m[j])=1
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>c[i]>>m[i];//citim resturile si modulele
        M*=m[i];//ne calculam produsul modulelor
    }
    for(int i=1;i<=n;i++)
    {
        X[i]=M/m[i];
        int x,y;
        invers_modular(X[i],m[i],x,y);//X_inv este inversul modular al lui X in raport cu m[i]
        while(x<0)
        {
            x+=m[i];
        }
        X_inv[i]=x;
    }
    for(int i=1;i<=n;i++)
    {
        sol+=c[i]*X[i]*X_inv[i];//calculam sol
    }
    cout<<sol;// putem avea solutii de forma sol+k*M, unde k numar intreg

}

ARTICOLE SIMILAREDE LA ACELAȘI AUTOR