Massimo comun divisore - Greatest common divisor

In matematica , il massimo comun divisore ( MCD ) di due o più interi , che non sono tutti zero, è il più grande intero positivo che divide ciascuno degli interi. Per due interi x , y , il massimo comun divisore di x ed y è indicata . Ad esempio, il MCD di 8 e 12 è 4, ovvero . ${\displaystyle \gcd(x,y)}$${\displaystyle \gcd(8,12)=4}$

Nel nome "più grande comun divisore", l'aggettivo "più grande" può essere sostituito da "più alto", e la parola "divisore" può essere sostituita da "fattore", in modo che altri nomi includano il massimo comun divisore ( hcf ), ecc. Storicamente, altri nomi per lo stesso concetto hanno incluso la massima misura comune .

Questa nozione può essere estesa ai polinomi (vedi Massimo comun divisore polinomiale ) e ad altri anelli commutativi (vedi § In anelli commutativi sotto).

Panoramica

Definizione

Il massimo comun divisore (MCD) di due nulli interi a e b è il massimo intero positivo d tale che d è un divisore di entrambi un e b ; cioè, ci sono interi e e f tali che a = de e b = df , e d è il più grande di questi interi. Il MCD di un e b è generalmente indicata con gcd ( a , b ) .

Questa definizione si applica anche quando uno di un e b è zero. In questo caso, il MCD è il valore assoluto dell'intero diverso da zero: gcd( a , 0) = gcd(0, a ) = | a | . Questo caso è importante come passo finale dell'algoritmo euclideo .

La definizione di cui sopra non può essere utilizzata per definire gcd(0, 0) , poiché 0 × n = 0 , e quindi zero non ha divisore massimo. Tuttavia, zero è il suo stesso massimo divisore se il massimo è inteso nel contesto della relazione di divisibilità, quindi gcd(0, 0) è comunemente definito come 0. Ciò conserva le solite identità per MCD, e in particolare l'identità di Bézout , cioè quella mcd ( a , b ) genera lo stesso ideale di { a , b } . Questa convenzione è seguita da molti sistemi di computer algebra . Tuttavia, alcuni autori lasciano gcd(0, 0) indefinito.

Il GCD di un e B è il loro massimo comun divisore positivo nella relazione preordine di divisibilità . Ciò significa che i divisori comuni di un e b sono esattamente i divisori di loro GCD. Ciò è comunemente dimostrato utilizzando il lemma di Euclide , il teorema fondamentale dell'aritmetica o l' algoritmo euclideo . Questo è il significato di "più grande" che viene utilizzato per le generalizzazioni del concetto di GCD.

Esempio

Il numero 54 può essere espresso come prodotto di due interi in diversi modi:

${\displaystyle 54\times 1=27\times 2=18\times 3=9\times 6.}$

Quindi l'elenco completo dei divisori di 54 è . Allo stesso modo, i divisori di 24 sono . I numeri che accomunano queste due liste sono i divisori comuni di 54 e 24, cioè, ${\displaystyle 1,2,3,6,9,18,27,54}$${\displaystyle 1,2,3,4,6,8,12,24}$

${\displaystyle 1,2,3,6.}$

Di questi, il massimo è 6, quindi è il massimo comun divisore :

${\displaystyle \gcd(54,24)=6.}$

Il calcolo di tutti i divisori dei due numeri in questo modo di solito non è efficiente, specialmente per i grandi numeri che hanno molti divisori. Metodi molto più efficienti sono descritti nel § Calcolo .

Numeri del coprima

Due numeri sono chiamati relativamente primi, o coprimi , se il loro massimo comun divisore è uguale a 1. Ad esempio, 9 e 28 sono primi tra loro.

Una vista geometrica

Un rettangolo 24x60 è coperto con dieci tessere quadrate 12x12, dove 12 è il MCD di 24 e 60. Più in generale, un rettangolo a -by- b può essere ricoperto con tessere quadrate di lunghezza solo c se c è un divisore comune di a e b .

Ad esempio, un'area rettangolare di 24 per 60 può essere divisa in una griglia di: quadrati 1 per 1, quadrati 2 per 2, quadrati 3 per 3, quadrati 4 per 4, quadrati 6 per -6 quadrati o 12 per 12 quadrati. Pertanto, 12 è il massimo comun divisore di 24 e 60. Un'area rettangolare di 24 per 60 può quindi essere divisa in una griglia di quadrati 12 per 12, con due quadrati lungo un bordo (24/12 = 2) e cinque quadrati uno sull'altro (60/12 = 5).

Applicazioni

Ridurre le frazioni

Il massimo comun divisore è utile per ridurre le frazioni ai minimi termini . Ad esempio, mcd(42, 56) = 14, quindi,

${\displaystyle {\frac {42}{56}}={\frac {3\cdot 14}{4\cdot 14}}={\frac {3}{4}}.}$

Minimo comune multiplo

Il massimo comun divisore può essere utilizzato per trovare il minimo comune multiplo di due numeri quando è noto il massimo comun divisore, utilizzando la relazione,

${\displaystyle \operatorname {lcm} (a,b)={\frac {|a\cdot b|}{\operatorname {gcd} (a,b)}}.}$

Calcolo

Usando fattorizzazioni prime

I massimi comuni divisori possono essere calcolati determinando la scomposizione in fattori primi dei due numeri e confrontando i fattori. Ad esempio, per calcolare mcd(48, 180), troviamo le fattorizzazioni prime 48 = 2 ⁴  · 3 ¹ e 180 = 2 ²  · 3 ²  · 5 ¹ ; il MCD è quindi 2 ^min(4,2)  · 3 ^min(1,2)  · 5 ^min(0,1) = 2 ²  · 3 ¹  · 5 ⁰ = 12, come mostrato nel diagramma di Venn . Il LCM corrispondente è quindi 2 ^max(4,2)  · 3 ^max(1,2)  · 5 ^max(0,1) = 2 ⁴  · 3 ²  · 5 ¹ = 720.

In pratica, questo metodo è fattibile solo per numeri piccoli, poiché il calcolo della scomposizione in fattori primi richiede troppo tempo.

Algoritmo di Euclide

Il metodo introdotto da Euclide per il calcolo dei massimi comun divisori si basa sul fatto che, dati due interi positivi a e b tali che a > b , i comuni divisori di a e b sono uguali ai comuni divisori di a – b e b .

Quindi, il metodo di Euclide per calcolare il massimo comun divisore di due interi positivi consiste nel sostituire il numero maggiore con la differenza dei numeri, e ripetere questo fino a quando i due numeri sono uguali: questo è il loro massimo comun divisore.

Ad esempio, per calcolare gcd(48,18) , si procede come segue:

${\displaystyle {\begin{allineato}(48,18)\quad &\to \quad (48-18,18)=(30,18)&&\to \quad (30-18,18)=(12, 18)\\&\a \quad (12,18-12)=(12,6)&&\a \quad (12-6,6)=(6,6).\end{allineato}}}$

Quindi mcd(48, 18) = 6 .

Questo metodo può essere molto lento se un numero è molto più grande dell'altro. Quindi, la variante che segue è generalmente preferita.

Algoritmo euclideo

Riproduci contenuti multimediali

Animazione che mostra un'applicazione dell'algoritmo euclideo per trovare il massimo comun divisore di 62 e 36, che è 2.

Un metodo più efficiente è l' algoritmo di Euclide , una variante in cui la differenza dei due numeri a e b è sostituito dal resto della divisione euclidea (chiamato anche divisione con resto ) di una da b .

Denotando questo resto come un mod b , l'algoritmo sostituisce ( a , b ) con ( b , a mod b ) ripetutamente finché la coppia è ( d , 0) , dove d è il massimo comun divisore.

Ad esempio, per calcolare gcd(48,18), il calcolo è il seguente:

${\displaystyle {\begin{allineato}(48,18)\quad &\to \quad (18,48{\bmod {1}}8)=(18,12)\\&\to \quad (12, 18{\bmod {1}}2)=(12,6)\\&\to \quad (6,12{\bmod {6}})=(6,0).\end{allineato}}}$

Questo dà di nuovo gcd(48, 18) = 6 .

Algoritmo GCD di Lehmer

L'algoritmo di Lehmer si basa sull'osservazione che i quozienti iniziali prodotti dall'algoritmo di Euclide possono essere determinati basandosi solo sulle prime cifre; questo è utile per i numeri più grandi di una parola di computer . In sostanza, si estrae le cifre iniziali, formando tipicamente una o due parole di computer, e si eseguono gli algoritmi di Euclide su questi numeri più piccoli, purché sia ​​garantito che i quozienti siano gli stessi con quelli che si otterrebbero con i numeri originari. Questi quozienti sono raccolti in una piccola matrice di trasformazione 2 per 2 (cioè una matrice di interi di una sola parola), per usarli tutti in una volta per ridurre i numeri originali . Questo processo viene ripetuto fino a quando i numeri sono abbastanza piccoli da rendere più efficiente l'algoritmo binario (vedi sotto).

Questo algoritmo migliora la velocità, perché riduce il numero di operazioni su numeri molto grandi e può utilizzare l'aritmetica hardware per la maggior parte delle operazioni. In effetti, la maggior parte dei quozienti sono molto piccoli, quindi un discreto numero di passaggi dell'algoritmo euclideo può essere raccolto in una matrice 2 per 2 di interi a parola singola. Quando l'algoritmo di Lehmer incontra un quoziente troppo grande, deve ricorrere a un'iterazione dell'algoritmo euclideo, con una divisione euclidea di grandi numeri.

Algoritmo binario GCD

I binari usi algoritmo GCD solo sottrazione e la divisione per 2. Il metodo è il seguente: Che un e b siano due interi non negativi. Lascia che l'intero d sia 0. Ci sono cinque possibilità:

• a = b .

Poiché mcd( a , a ) = a , il MCD desiderato è a × 2 ^d (poiché a e b vengono modificati negli altri casi e d registra il numero di volte in cui a e b sono stati entrambi divisi per 2 nel successivo passo, il MCD della coppia iniziale è il prodotto di a e 2 ^d ).

• Sia a che b sono pari.

Allora 2 è un divisore comune. Dividi sia a che b per 2, incrementa d per 1 per registrare il numero di volte in cui 2 è un divisore comune e continua.

• a è pari e b è dispari.

Allora 2 non è un divisore comune. Dividere a per 2 e continuare.

• a è dispari e b è pari.

Allora 2 non è un divisore comune. Dividi b per 2 e continua.

• Sia a che b sono dispari.

Come mcd( a , b ) = mcd( b , a ), se a < b allora scambia a e b . Il numero c = a − b è positivo e minore di a . Qualsiasi numero che divide a e b deve dividere anche c, quindi ogni divisore comune di a e b è anche divisore comune di b e c . Allo stesso modo, a = b + c e ogni divisore comune di b e c è anche divisore comune di a e b . Quindi le due coppie ( a , b ) e ( b , c ) hanno gli stessi divisori comuni, e quindi mcd( a , b ) = mcd( b , c ). Inoltre, poiché a e b sono entrambi dispari, c è pari, il processo può essere continuato con la coppia ( a , b ) sostituita dai numeri più piccoli ( c /2, b ) senza modificare il MCD.

Ciascuno dei passaggi sopra riduce almeno uno di un e b lasciando loro non negativo e così può essere ripetuto un numero finito di volte. Quindi alla fine il processo risulta in a = b , il caso di arresto. Allora il MCD è a × 2 ^d .

Esempio: ( a , b , d ) = (48, 18, 0) → (24, 9, 1) → (12, 9, 1) → (6, 9, 1) → (3, 9, 1) → (3, 3, 1) ; il MCD originale è quindi il prodotto 6 di 2 ^d = 2 ¹ e a = b = 3.

L'algoritmo binario GCD è particolarmente facile da implementare su computer binari. La sua complessità computazionale è

${\displaystyle O((\log a+\log b)^{2})}$

La complessità computazionale è solitamente data in termini di lunghezza n dell'input. Ecco, questa lunghezza è e la complessità è così ${\displaystyle n=\log a+\log b,}$

${\displaystyle O(n^{2})}$.

Altri metodi

${\displaystyle \gcd(1,x)=y,}$o la funzione di Thomae. Il tratteggio in basso indica le ellissi (ovvero l'omissione di punti a causa della densità estremamente elevata).

Se a e b sono entrambi diversi da zero, il massimo comun divisore di a e b può essere calcolato utilizzando il minimo comune multiplo (LCM) di a e  b :

${\displaystyle \gcd(a,b)={\frac {|a\cdot b|}{\operatorname {lcm} (a,b)}}}$,

ma più comunemente l'LCM viene calcolato dal GCD.

Usando la funzione di Thomae f ,

${\displaystyle \gcd(a,b)=af\left({\frac {b}{a}}\right),}$

che generalizza ad un e b numeri razionali o commensurabili numeri reali.

Keith Slavin ha dimostrato che per dispari a  ≥ 1:

${\displaystyle \gcd(a,b)=\log _{2}\prod _{k=0}^{a-1}(1+e^{-2i\pi kb/a})}$

che è una funzione che può essere valutata per il complesso b . Wolfgang Schramm lo ha dimostrato

${\displaystyle \gcd(a,b)=\sum \limits _{k=1}^{a}\exp(2\pi ikb/a)\cdot \sum \limits _{d\left|a\right .}{\frac {c_{d}(k)}{d}}}$

è un'intera funzione nella variabile b per tutti gli interi positivi a dove c _d ( k ) è la somma di Ramanujan .

Complessità

La complessità computazionale del calcolo dei massimi comuni divisori è stata ampiamente studiata. Se si utilizzano l' algoritmo euclideo e gli algoritmi elementari di moltiplicazione e divisione, il calcolo del massimo comun divisore di due interi di al massimo n bit è Ciò significa che il calcolo del massimo comun divisore ha, fino ad un fattore costante, lo stesso complessità come la moltiplicazione. ${\displaystyle O(n^{2}).}$

Tuttavia, se viene utilizzato un algoritmo di moltiplicazione veloce , si può modificare l'algoritmo euclideo per migliorare la complessità, ma il calcolo di un massimo comun divisore diventa più lento della moltiplicazione. Più precisamente, se la moltiplicazione di due interi di n bit richiede un tempo di T ( n ) , allora l'algoritmo noto più veloce per il massimo comun divisore ha una complessità Ciò implica che l'algoritmo noto più veloce ha una complessità di${\displaystyle O\left(T(n)\log n\right).}$${\displaystyle O\left(n\,(\log n)^{2}\right).}$

Le complessità precedenti sono valide per i soliti modelli di calcolo , in particolare le macchine di Turing multitape e le macchine ad accesso casuale .

Il calcolo dei massimi comun divisori appartiene quindi alla classe dei problemi risolvibili in tempo quasilineare . A fortiori , il corrispondente problema decisionale appartiene alla classe P dei problemi risolvibili in tempo polinomiale. Il problema GCD non è noto per essere in NC , e quindi non esiste un modo noto per parallelizzarlo in modo efficiente; né è noto che sia P-completo , il che implicherebbe che è improbabile che sia possibile parallelizzare in modo efficiente il calcolo del GCD. Shallcross et al. ha mostrato che un problema correlato (EUGCD, che determina la sequenza del resto che sorge durante l'algoritmo euclideo) è NC-equivalente al problema della programmazione lineare intera con due variabili; se uno dei due problemi è in NC o è P-completo , anche l'altro lo è. Poiché NC contiene NL , non è noto se esista un algoritmo efficiente in termini di spazio per il calcolo del GCD, anche per macchine di Turing non deterministiche.

Sebbene non sia noto che il problema sia in NC , esistono algoritmi paralleli asintoticamente più veloci dell'algoritmo euclideo; l'algoritmo deterministico più veloce conosciuto è quello di Chor e Goldreich, che (nel modello CRCW-PRAM ) può risolvere il problema in tempo O ( n /log n ) con n ^1+ε processori. Gli algoritmi randomizzati possono risolvere il problema in tempo O ((log n ) ² ) sui processori (questo è superpolinomiale ). ${\displaystyle \exp \left(O\left({\sqrt {n\log n}}\right)\right)}$

Proprietà

• Ogni comune divisore di un e b è un divisore di MCD ( a , b ) .
• gcd( a , b ) , dove a e b non sono entrambi zero, può essere definito alternativamente ed equivalentemente come il più piccolo intero positivo d che può essere scritto nella forma d = a ⋅ p + b ⋅ q , dove p e q sono interi. Questa espressione è chiamata identità di Bézout . Numeri p e q simili possono essere calcolati con l' algoritmo di Euclide esteso .
• mcd( a , 0) = | a | , per a ≠ 0 , poiché ogni numero è un divisore di 0 e il massimo divisore di a è | un |. Questo è solitamente usato come caso base nell'algoritmo euclideo.
• Se a divide il prodotto b ⋅ c e mcd( a , b ) = d , allora a / d divide c .
• Se m è un intero non negativo, allora mcd( m ⋅ a , m ⋅ b ) = m ⋅gcd( a , b ) .
• Se m è un numero intero, allora mcd( a + m ⋅ b , b ) = mcd( a , b ) .
• Se m è un divisore comune positivo di a e b , allora mcd( a / m , b / m ) = mcd( a , b )/ m .
• Il MCD è una funzione moltiplicativa nel seguente senso: se a ₁ e a ₂ sono primi tra loro, allora mcd( a ₁ ⋅ a ₂ , b ) = mcd( a ₁ , b )⋅gcd( a ₂ , b ) . In particolare, ricordando che MCD è una funzione a valori interi positivi, si ottiene che mcd( a , b ⋅ c ) = 1 se e solo se mcd( a , b ) = 1 e mcd( a , c ) = 1 .
• Il MCD è una funzione commutativa : mcd( a , b ) = mcd( b , a ) .
• Il MCD è una funzione associativa : gcd( a , gcd( b , c )) = gcd(gcd( a , b ), c ) . Quindi gcd( a , b , c , ...) può essere usato per denotare il MCD di più argomenti.
• gcd( a , b ) è strettamente correlato al minimo comune multiplo lcm( a , b ) : abbiamo

  mcd( a , b )⋅lcm( a , b ) = | a ⋅ b | .

Questa formula viene spesso utilizzata per calcolare i minimi comuni multipli: si calcola prima il MCD con l'algoritmo di Euclide e poi si divide il prodotto dei numeri dati per il loro MCD.

• Le seguenti versioni di distributività sono vere:

  mcd( a , lcm( b , c )) = lcm(gcd( a , b ), mcd( a , c ))

  lcm( a , gcd( b , c )) = mcd(lcm( a , b ), lcm( a , c )) .

• Se abbiamo le uniche fattorizzazioni prime di a = p ₁ ^{e ₁} p ₂ ^{e ₂} ⋅⋅⋅ p _m ^{e _m} e b = p ₁ ^{f ₁} p ₂ ^{f ₂} ⋅⋅⋅ p _m ^{f _m} dove e _i ≥ 0 e f _i ≥ 0 , allora il MCD di a e b è

  mcd( a , b ) = p ₁ ^{min( e ₁ , f ₁ )} p ₂ ^{min ( e ₂ , f ₂ )} ⋅⋅⋅ p _m ^{min ( e _m , f _m )} .

• A volte è utile definire gcd(0, 0) = 0 e lcm(0, 0) = 0 perché allora i numeri naturali diventano un reticolo distributivo completo con MCD come meet e LCM come operazione di join. Questa estensione della definizione è compatibile anche con la generalizzazione per gli anelli commutativi data sotto.
• In un sistema di coordinate cartesiane , mcd( a , b ) può essere interpretato come il numero di segmenti tra punti con coordinate integrali sul segmento di retta che unisce i punti (0, 0) e ( a , b ) .
• Per interi non negativi a e b , dove a e b non sono entrambi zero, dimostrabili considerando l'algoritmo euclideo in base  n :

  mcd( n ^a − 1, n ^b − 1) = n ^{mcd( a , b )} − 1 .

• Un'identità che coinvolge la funzione totient di Eulero :

  ${\displaystyle \gcd(a,b)=\sum _{k|a{\text{ e }}k|b}\varphi (k).}$

Probabilità e valore atteso

Nel 1972, James E. Nymann dimostrò che k interi, scelti indipendentemente e uniformemente da {1, ...,  n }, sono coprimi con probabilità 1/ ζ ( k ) quando n va all'infinito, dove ζ si riferisce alla zeta di Riemann funzione . (Vedi coprimo per una derivazione.) Questo risultato è stato esteso nel 1987 per mostrare che la probabilità che k interi casuali abbiano il massimo comun divisore d è d ^−k /ζ( k ).

Usando queste informazioni, si può vedere (informalmente) che il valore atteso della funzione del massimo comun divisore non esiste quando k  = 2. In questo caso la probabilità che il MCD sia uguale a d è d ⁻² /ζ(2), e poiché ζ (2) = π ² /6 abbiamo

${\displaystyle \mathrm {E} (\mathrm {2} )=\sum _{d=1}^{\infty }d{\frac {6}{\pi ^{2}d^{2}}} ={\frac {6}{\pi ^{2}}}\sum _{d=1}^{\infty }{\frac {1}{d}}.}$

Quest'ultima sommatoria è la serie armonica , che diverge. Tuttavia, quando k  ≥ 3, il valore atteso è ben definito e, per l'argomento precedente, è

${\displaystyle \mathrm {E} (k)=\sum _{d=1}^{\infty}d^{1-k}\zeta (k)^{-1}={\frac {\zeta ( k-1)}{\zeta (k)}}.}$

Per k  = 3, questo è approssimativamente uguale a 1,3684. Per k  = 4, è circa 1,1106.

Se un argomento del MCD è fissato a un valore , diventerà una funzione moltiplicativa nell'altra variabile e si può dimostrare che ${\displaystyle m}$

${\displaystyle {\frac {1}{N}}\lim _{N\to \infty}\sum _{n=1}^{N}\gcd(n,m)=\prod _{p^{ \alpha }||n}\left(1+\alpha -{\frac {\alpha }{p}}\right)}$

Qui, indica il prodotto su tutte le potenze prime tale che ma${\displaystyle \prod _{p^{\alpha }||n}}$${\displaystyle p^{\alpha }}$${\displaystyle p^{\alpha }|n}$${\displaystyle p^{\alpha +1}\non |n}$

Negli anelli commutativi

La nozione di massimo comun divisore può essere definita più in generale per elementi di un anello commutativo arbitrario , anche se in generale non è necessario che ne esista uno per ogni coppia di elementi.

Se R è un anello commutativo, e un e b sono in R , allora un elemento d di R è chiamato un comune divisore di un e b se divide sia un e b (cioè, se ci sono elementi x e y in R tale che d · x  =  a e d · y  =  b ). Se d è un comune divisore di un e B , ed ogni comune divisore di un e B divide D , allora d è chiamato un massimo comun divisore di un e b .

Con questa definizione, due elementi a e b può benissimo avere diversi massimi comuni divisori, o nessuno affatto. Se R è un dominio integrale allora due MCD qualsiasi di a e b devono essere elementi associati , poiché per definizione uno deve dividere l'altro; infatti se esiste un GCD, anche uno dei suoi associati è un GCD. L'esistenza di un GCD non è assicurata in domini integrali arbitrari. Tuttavia, se R è un dominio di fattorizzazione univoco , allora due elementi qualsiasi hanno un GCD, e più in generale questo è vero nei domini GCD . Se R è un dominio euclideo in cui la divisione euclidea è data algoritmicamente (come nel caso, ad esempio, quando R = F [ X ] dove F è un campo , o quando R è l'anello degli interi gaussiani ), allora i massimi comuni divisori possono essere calcolato utilizzando una forma dell'algoritmo euclideo basato sulla procedura di divisione.

Quello che segue è un esempio di un dominio integrale con due elementi che non hanno un GCD:

${\displaystyle R=\mathbb {Z} \left[{\sqrt {-3}}\,\,\right],\quad a=4=2\cdot 2=\left(1+{\sqrt {- 3}}\,\,\right)\left(1-{\sqrt {-3}}\,\,\right),\quad b=\left(1+{\sqrt {-3}}\, \,\destra)\cdot 2.}$

Gli elementi 2 e 1 +  √ −3 sono due massimo comun divisori (ovvero, ogni comun divisore multiplo di 2 è associato a 2, lo stesso vale per 1 +  √ −3 , ma non sono associati, quindi non non è il massimo comun divisore di a e  b .

In corrispondenza della proprietà di Bézout possiamo, in qualsiasi anello commutativo, considerare l'insieme di elementi della forma pa  +  qb , dove p e q spaziano sull'anello. Questo è l' ideale generato da a e b , ed è indicato semplicemente ( a ,  b ). In un anello i cui ideali sono tutti principali (un dominio ideale principale o PID), questo ideale sarà identico all'insieme dei multipli di qualche elemento dell'anello d ; allora questo d è un massimo comun divisore di a e b . Ma l'ideale ( a ,  b ) può essere utile anche quando non esiste il massimo comun divisore di a e b . (In effetti, Ernst Kummer usò questo ideale come sostituto di un GCD nel suo trattamento dell'Ultimo Teorema di Fermat , sebbene lo immaginasse come l'insieme di multipli di qualche ipotetico, o ideale , elemento d' anello d , da cui il termine teorico dell'anello.)

Guarda anche

• Dominio di Bézout
• Minimo comun denominatore
• divisore unitario

Appunti

Riferimenti

• Andrews, George E. (1994) [1971], Teoria dei numeri , Dover, ISBN 9780486682525
• Hardy, GH ; Wright, EM (1979), Introduzione alla teoria dei numeri (quinta ed.), Oxford: Oxford University Press , ISBN 978-0-19-853171-5
• Long, Calvin T. (1972), Introduzione elementare alla teoria dei numeri (2a ed.), Lexington: DC Heath and Company , LCCN  77171950
• Pettofrezzo, Anthony J.; Byrkit, Donald R. (1970), Elementi di teoria dei numeri , Englewood Cliffs: Prentice Hall , LCCN  71081766

Ulteriori letture

• Donald Knut . L'arte della programmazione dei computer , Volume 2: Algoritmi seminumerici , Terza edizione. Addison-Wesley, 1997. ISBN  0-201-89684-2 . Sezione 4.5.2: Il massimo comun divisore, pp. 333-356.
• Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest e Clifford Stein . Introduzione agli algoritmi , seconda edizione. MIT Press e McGraw-Hill, 2001. ISBN  0-262-03293-7 . Sezione 31.2: Massimo comun divisore, pp. 856-862.
• Saunders Mac Lane e Garrett Birkhoff . Un'indagine sull'algebra moderna , quarta edizione. MacMillan Publishing Co., 1977. ISBN  0-02-310070-2 . 1-7: "L'algoritmo euclideo".