Interi coprimi
![Niente fonti!](http://upload.wikimedia.org/wikipedia/commons/thumb/6/64/Question_book-4.svg/45px-Question_book-4.svg.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/d/dc/Coprime_numbers_generation.png/220px-Coprime_numbers_generation.png)
In matematica, gli interi e si dicono coprìmi[1] (o primi tra loro o relativamente primi) se e solo se essi non hanno nessun divisore comune eccetto 1 e -1 o, in modo equivalente, 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 anche per 3. 1 è coprimo con ogni numero intero; 0 è coprimo solo a 1 e -1.
Un metodo efficiente per determinare se due numeri sono coprimi è fornito dall'algoritmo di Euclide.
Proprietà
![](http://upload.wikimedia.org/wikipedia/commons/thumb/8/87/Magnifying_glass_icon_mgx2.svg/18px-Magnifying_glass_icon_mgx2.svg.png)
I numeri a e b sono coprimi se e solo se esistono interi x e y tali che ax + by = 1. 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 è "visibile" dall'origine (0,0), nel senso che non esiste alcun punto di coordinate intere tra l'origine e il punto (a, b).
La probabilità che due interi scelti a caso siano primi tra loro è
Se due numeri naturali a e b sono coprimi i numeri 2a - 1 e 2b - 1 sono coprimi.
Generalizzazione
Due ideali A e B nell'anello commutativo R sono detti coprimi se A + B = R. Ciò consente di generalizzare l'identità di Bézout. 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.
Note
- ^ co-primi; l'accento non è sulla o ma sulla prima i: deriva dalla parola "primi" affiancata dal prefisso "co"
Voci correlate
- Algoritmo di Euclide
- Massimo comun divisore
- Numero primo
- Funzione phi di Eulero
- Nontotiente
Altri progetti
Altri progetti
- Wikimedia Commons
Wikimedia Commons contiene immagini o altri file sugli interi coprimi
Collegamenti esterni
- (EN) Eric W. Weisstein, Relatively Prime, su MathWorld, Wolfram Research.
- (EN) Denis Howe, relatively prime, in Free On-line Dictionary of Computing. Disponibile con licenza GFDL
V · D · M | ||
---|---|---|
Numeri più usati | Naturali · Interi · Pari e dispari | ![]() |
Principi generali | Principio d'induzione · Principio del buon ordinamento · Relazione di equivalenza | |
Successioni di interi | Fattoriale · Successione di Fibonacci · Numero di Catalan · Numero di Perrin · Numero di Eulero · Successione di Mian-Chowla · Successione di Thue-Morse | |
Caratteristiche dei numeri primi | Numero primo · Lemma di Euclide · Teorema dell'infinità dei numeri primi · Crivello di Eratostene · Test di primalità · Teorema fondamentale dell'aritmetica · Interi coprimi · Identità di Bézout · MCD · mcm · Algoritmo di Euclide · Algoritmo esteso di Euclide · Teorema dei numeri primi | |
Funzioni aritmetiche | Funzione moltiplicativa · Funzione additiva · Convoluzione di Dirichlet · Funzione φ di Eulero · Funzione di Möbius · Funzione tau sui positivi · Funzione sigma · Funzione di Liouville · Funzione di Mertens | |
Aritmetica modulare | Teorema cinese del resto · Piccolo teorema di Fermat · Teorema di Eulero · Criteri di divisibilità · Teorema di Fermat sulle somme di due quadrati · Teorema di Wilson · Legge di reciprocità quadratica | |
Congetture | Congettura di Goldbach · Congettura di Polignac · Congettura abc · Congettura dei numeri primi gemelli · Congettura di Legendre · Nuova congettura di Mersenne · Congettura di Collatz · Ipotesi di Riemann | |
Altro | Problema di Waring | |
Principali teorici | Fibonacci · Fermat · Gauss · Eulero · Legendre · Riemann · Dirichlet | |
Discipline connesse | Teoria algebrica dei numeri · Teoria analitica dei numeri · Crittografia · Teoria computazionale dei numeri |
![](http://upload.wikimedia.org/wikipedia/commons/thumb/a/af/Crystal128-kmplot.svg/25px-Crystal128-kmplot.svg.png)