Coefficienti di Bézout: interi x, y con a·x + b·y = MCD

L'identità di Bézout afferma che, per qualunque coppia di interi a e b non entrambi zero, esistono interi x e y tali che a per x più b per y è uguale al massimo comun divisore di a e b. Quei coefficienti sono il cuore costruttivo delle equazioni diofantee lineari, delle inverse modulari quando l'MCD vale uno e delle dimostrazioni scolastiche che due numeri sono coprimi.

Cosa afferma l'identità di Bézout e perché i coefficienti contano

Ogni coppia di interi non entrambi zero ha un massimo comun divisore non negativo ben definito g. L'identità di Bézout va oltre: garantisce interi x e y per cui a per x più b per y è uguale a quel g. La prova di esistenza è costruttiva e segue il processo dei resti euclidei.

La divisione ordinaria sostituisce ripetutamente una coppia con il resto successivo finché compare lo zero; l'ultimo resto non nullo è l'MCD. Seguendo come ogni resto si scrive come combinazione lineare intera degli ingressi originali si ottengono i coefficienti al termine. I testi scolastici spesso retro-sostituiscono i quozienti della tabella delle divisioni; il codice di produzione di solito aggiorna due coppie di coefficienti in un solo ciclo senza conservare la pila dei resti.

Entrambi gli approcci calcolano lo stesso oggetto matematico. I coefficienti non sono unici: se una coppia funziona, funziona anche ogni coppia traslata di multipli interi di b su g e di a su g con segni opposti. Questo strumento restituisce una soluzione particolare dell'algoritmo iterativo, sempre con MCD non negativo, così script e correttori possono confrontare una convenzione fissa senza ricalcolare l'insieme generale delle soluzioni.

Come invocare il calcolatore e leggere la risposta

Invii gli interi a e b. Anche la coppia zero e zero è rifiutata, perché l'MCD di zero e zero è indefinito e nessun coefficiente produce un'equazione di Bézout significativa. In caso di successo la risposta include a e b normalizzati, l'MCD, x, y, un oggetto bezout annidato con gli stessi coefficienti, un check numerico uguale ad a per x più b per y, una stringa di equazione del tipo duecentoquaranta per meno nove più quarantasei per quarantasette uguale due, e un campo identity con la relazione generale.

Controlli tipici: per duecentoquaranta e quarantasei l'MCD è due con una soluzione valida x uguale a meno nove e y uguale a quarantasette; per una coppia di primi con MCD uno i coefficienti danno l'inversa modulare di a modulo b dopo aver ridotto x. I casi con uno zero e un partner non nullo danno MCD pari al valore assoluto dell'ingresso non nullo e un pattern banale di coefficienti.

Dove i coefficienti di Bézout compaiono nella pratica

I programmatori di gare risolvono a per x più b per y uguale a c calcolando prima l'MCD e una coppia base di Bézout, poi scalando e parametrizzando la soluzione generale quando l'MCD divide c. Gli studenti di crittografia recuperano inverse modulari per esempi didattici RSA e cifrari affini quando l'MCD di a e m vale uno, leggendo il coefficiente di a dopo la riduzione modulo m.

I docenti assegnano prove costruttive che due interi sono coprimi e necessitano di un oracolo deterministico che mostri la combinazione lineare, non solo un bit di coprimalità. Ingegneri di dati e di sistemi a volte richiedono combinazioni lineari esplicite nel riconciliare calendari periodici o aritmetica a passi. Usi lo strumento del browser per controllare rapidamente i compiti, poi automatizzi lo stesso contratto quando il Suo servizio necessita di verifiche diofantee in blocco.

Se Le serve solo l'MCD senza coefficienti, questa pagina risponde comunque a tale esigenza e insegna il risultato costruttivo di Bézout che sostiene i curricula di teoria dei numeri e le domande di colloquio sul ragionamento di Euclide esteso.