Interi coprimi

Generazione di numeri coprimi mediante l'algoritmo

In matematica, gli interi $a$ e $b$ si dicono coprìmi (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à

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.

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

• 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