Euclide esteso: MCD e coefficienti di Bézout x, y

L'algoritmo di Euclide esteso non si limita a riportare il massimo comune divisore di due interi: produce anche coefficienti di Bézout x e y tali che a per x più b per y uguaglia quel MCD. Quei coefficienti compaiono negli inversi modulari quando il MCD è uno, nelle dimostrazioni costruttive di equazioni diofantee lineari e nei compiti di crittografia che richiedono una combinazione esplicita anziché un resto nudo.

Dai resti ai coefficienti di Bézout

La divisione euclidea ordinaria sostituisce ripetutamente una coppia (a, b) con (b, a mod b) finché il resto è zero; l'ultimo resto non nullo è MCD(a, b). La forma estesa tiene traccia di come ogni resto si scrive come combinazione lineare intera degli input originali. A ogni passo il resto corrente uguaglia a per un coefficiente più b per un altro, e quando l'algoritmo si ferma quei coefficienti sono esattamente i numeri di Bézout del MCD.

Le presentazioni in aula usano spesso la sostituzione all'indietro dalla sequenza dei quozienti; il codice di produzione aggiorna in modo iterativo due coppie di coefficienti senza salvare una pila di resti. Entrambi gli approcci calcolano lo stesso oggetto matematico: interi x e y che soddisfano a*x + b*y = MCD(a, b). Il MCD è sempre restituito come intero non negativo, secondo la convenzione standard di librerie e testi di gara.

Cosa invia e cosa riceve

Anche la coppia zero e zero è rifiutata, perché MCD(0, 0) è indefinito e nessun coefficiente produce un'equazione significativa. In caso di successo la risposta include a e b normalizzati, MCD, x, y, un oggetto bezout annidato con gli stessi coefficienti, un controllo numerico uguale a a*x + b*y e una stringa di equazione come 240*(-9) + 46*(47) = 2.

Controlli tipici: per 240 e 46 il MCD è 2 e una soluzione valida è x uguale a meno nove con y uguale a quarantasette; per una coppia prima con MCD uno i coefficienti danno un inverso modulare di a modulo b dopo aver ridotto x. Casi limite con uno zero e un partner non nullo producono MCD uguale al valore assoluto dell'input non nullo e un pattern di coefficienti banale.

Dove i coefficienti di Bézout compaiono nel lavoro reale

I programmatori di gara risolvono ax + by = c calcolando prima il MCD e i coefficienti base, poi scalando e parametrizzando la soluzione generale quando il MCD divide c. Gli studenti di crittografia recuperano inversi modulari per esempi RSA giocattolo e cifrari affini quando MCD(a, m) è uno leggendo il coefficiente di a dopo la riduzione modulo m. I docenti assegnano dimostrazioni costruttive che due interi sono coprimi e necessitano di un oracolo deterministico che mostri la combinazione, non solo un bit di coprimalità.

Ingegneri di dati e sistemi a volte necessitano di combinazioni lineari esplicite riconciliando orari periodici o aritmetica di passo. Usi lo strumento del browser per controllare i compiti in fretta, poi automatizzi lo stesso contratto quando il Suo servizio necessita di controlli diofantei massivi. Se Le serve solo il MCD senza coefficienti, questa pagina risponde comunque a quell'esigenza insegnando il risultato costruttivo più forte.