Interi coprimi

In matematica, gli interi $a$ e $b$ 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.

Generazione di numeri coprimi mediante l'algoritmo

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à

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 Z_a 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 è ${\frac {6}{\pi ^{2}}}$

Se due numeri naturali a e b sono coprimi i numeri 2^a - 1 e 2^b - 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

Altri progetti

Wikimedia Commons contiene immagini o altri file sugli interi coprimi

Collegamenti esterni

Numeri primi tra loro, in Enciclopedia della Matematica, Istituto dell'Enciclopedia Italiana, 2013.
(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

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica

[1] -primi; l'accento non è sulla o ma sulla prima i: deriva dalla parola "primi" affiancata dal prefisso "co"

[1]