Interi coprimi
Da Wikipedia, l'enciclopedia libera.
In matematica, gli interi a e b si dicono coprimi o primi tra loro se e solo se essi non hanno nessun divisore comune eccetto 1 e -1, o, equivalentemente, se il loro massimo comune divisore è 1.
Per esempio, 6 e 35 sono coprimi, ma 6 e 27 non lo sono perché entrambi sono divisibili per 3. 1 è coprimo con ogni numero intero; 0 è coprimo solo ad 1 e −1.
Un metodo efficiente per determinare se due numeri sono coprimi è fornito dall'algoritmo di Euclide.
[modifica] Proprietà
I numeri a e b sono coprimi se e solo se esistono interi x e y tali che ax + by = 1 (vedi identità di Bézout). Equivalentemente, b ha un inverso moltiplicativo modulo a: esiste un intero y tale che by ≡ 1 (mod a).
Se a e b sono coprimi e a divide un prodotto bc, allora a divide c.
Se a e b sono coprimi e bx ≡ by (mod a), allora x ≡ y (mod a). In altre parole: b produce un'unità nell'anello Za degli interi modulo a.
I due interi a e b sono coprimi se e solo se il punto con coordinate (a, b) in un sistema di assi cartesiani è "visible" dall'origine (0,0), nel senso che non esiste alcun punto di coordinate intere tra l'origine ed il punto (a, b).
La probabilità che due interi scelti a caso siano primi tra loro è 6/π2 (vedi π).
Due numeri naturali a e b sono coprimi i numeri 2a − 1 e 2b − 1 sono coprimi.
[modifica] Generalizzazione
Due ideali A e B nell'anello commutativo R sono detti coprimi se A + B = R. Ciò consente di generalizzare l'identità di Bezout. Se A e B sono coprimi, allora AB = A∩B; inoltre, se C è un terzo ideale tale che A contiene BC, allora A contiene C.
Con questa definizione, due ideali principali (a) e (b) nell'anello degli interi Z sono coprimi se e solo se a e b sono coprimi.