CAPITOLO 1: prerequisiti teorici
2
CAPITOLO 1
Fattorizzazione in numeri primi
1 I NUMERI PRIMI
Nella teoria dei numeri è di fondamentale importanza la classe dei numeri primi.
Definizione 1.1 Un numero primo è un numero intero, maggiore di 1, che
non ammette divisori diversi da sé stesso e da 1.
Definizione 1.2 Un numero che non sia né 1, né un primo è detto numero
composto.
Definizione 1.3 Un numero naturale d si dice divisore o fattore di un numero
naturale n, se esiste un numero naturale c tale che ndc ; in tal caso scrive-
remo d | n.
L’importanza della classe dei numeri primi è dovuta al fatto che
Proposizione 1.1 Ogni numero intero maggiore di 1 o è primo o è rappresen-
tabile come prodotto di primi.
Dimostrazione
Per dimostrare tale asserzione applichiamo il metodo di induzione. La posizione
è vera per n = 2, essendo 2 un primo.
Assumiamo che la proposizione sia vera per tutti i numeri fino a n – 1 e mostria-
mo che vale anche per n.
Se n è primo, non dobbiamo provare nulla.
Se n è composto, per definizione è rappresentabile come prodotto di due numeri,
d
1
e d
2
, entrambi maggiore di uno e minori di n e per l’ipotesi induttiva, ognuno
di essi o è primo o è rappresentabile come prodotto di primi.
Sostituendo a d
1
e d
2
le rispettive espressioni come prodotti di primi otteniamo
che anche n = d
1
* d
2
è un prodotto di primi, e quindi la proposizione è provata
anche per n.
CAPITOLO 1: prerequisiti teorici
3
Proposizione 1.2 I numeri primi sono infiniti.
Dimostrazione
Procediamo per assurdo. Neghiamo la tesi e supponiamo che esista soltanto un
numero finito di primi, diciamo 2,3,5,7,………,P.
Consideriamo poi il numero N così definito:
2 3 5....... 1.P
Per la proposizione precedente (1.1.) N o è primo o è un prodotto di primi.
Se N è primo giungiamo ad una contraddizione per il fatto che N > P.
Se N è invece è un prodotto di primi giungiamo in ogni caso ad una contraddi-
zione poiché se 2, 3, 5, …….., P dividessero N, dovrebbero dividere anche
l’unità.
Poiché l’ipotesi iniziale che esista solo un numero finito di primi ci conduce a
queste contraddizioni,essa è evidentemente assurda, e ciò prova che esistono in-
finiti numeri primi.
1.2 Il teorema fondamentale dell’aritmetica
Abbiamo visto nelle proposizioni precedenti che ogni numero composto è esprimi-
bile come prodotto di primi.
Tali fattori primi si possono disporre in un ordine qualsiasi, ma a parte quest’arbi-
trarietà nell’ordine è possibile dimostrare che la fattorizzazione è unica.
Ciò è quanto afferma il Teorema fondamentale dell’aritmetica.
Teorema 1.1 Ogni numero intero maggiore di 1 è esprimibile in modo unico
come prodotto di primi.
Osservazioni preliminari:
Se la fattorizzazione di un particolare numero m è
unica, ogni divisore primo di m deve essere presente
in tale fattorizzazione. Infatti se p è un divisore primo
di m si ha 'mpm , e fattorizzando m’, si ottiene da
questa uguaglianza una fattorizzazione per m. Se esi-
stesse una fattorizzazione di m in cui p non compare
si negherebbe quindi la unicità.
Se un numero è primo sarà considerato come prodotto di primi, dove il prodotto
ha un solo fattore.
CAPITOLO 1: prerequisiti teorici
4
Dimostrazione
Ragioniamo per induzione.
Il teorema è vero per n = 2, essendo 2 un primo.
Assumiamo,come ipotesi induttiva,l’unicità della fattorizzazione per tutti i nume-
ri fino a n – 1 e mostriamo che il teorema vale anche per n.
Se n è un numero primo, non c’ è nulla da mostrare.
Se n è un numero composto, procediamo per assurdo, supponendo che abbia due
rappresentazioni diverse:
123 123
........ ........
s
npp p p qqq q
dove p
1
, p
2
, p
3
, ......., p
r
e q
1
, q
2
, q
3
,……, q
S
sono primi.
Osserviamo innanzitutto che se queste due fattorizzazioni sono distinte lo stesso
primo non può comparire in entrambe; infatti se così fosse potremmo semplifica-
re tale fattore dall’uguaglianza, ottenendo contro l’ipotesi induttiva un intero mi-
nore di n con due fattorizzazioni distinte.
Senza ledere la generalità, supponiamo che p
1
sia il più piccolo primo presente
nella prima fattorizzazione; essendo n un numero composto, c’è almeno un altro
primo nella fattorizzazione e quindi si ha
11
.npp τ Analogamente, se conside-
riamo la seconda rappresentazione, si ha
11
nqq τ .
Essendo p
1
e q
1
diversi, una almeno delle disuguaglianze precedenti deve valere
con il segno di minore stretto e quindi è
11
pq n
.
Ma allora il numero
11
npq è un naturale minore di n e maggiore di 1 (infatti
111
|( )pnpq )e applicando l’ipotesi induttiva, possiamo affermare che esso
ha un’unica fattorizzazione.
Poiché p
1
e q
1
sono divisori di n, lo sono anche di
11
npq , che sarà quindi della
forma
11 11
....npq pqPQ
dove P,Q ,...sono primi.
Abbiamo dunque che:
12 1111
..... ....
r
npp p pq pqPQ
Dividendo ambo i membri per p
1
, otteniamo che q
1
è un fattore di
2
......
r
p p , il
che è impossibile per l’ osservazione preliminare: infatti
2
......
r
p p è un nume-
ro minore di n non contenente q
1
nella fattorizzazione, dato che i primi p
i
, con
i = 1,2,3,….,r sono diversi dai primi q
j
, con j = 1,2,3,….s.
Siamo quindi ad un assurdo che ci fornisce la dimostrazione del teorema.
CAPITOLO 1: prerequisiti teorici
5
2 L’ALGORITMO EUCLIDEO
Per il momento abbiamo considerato solo i divisori di un numero.
Consideriamo ora il caso di divisori comuni a due o più numeri.
Siano m e n due interi positivi. Ogni divisore comune di m e n deve essere compo-
sto esclusivamente di primi che compaiono sia nella fattorizzazione di m che in
quella di n.
Definizione 2.1 Due numeri m e n si dicono relativamente primi se non hanno
divisori comuni diversi dall’ unità.
Se invece m e n presentano fattori comuni è possibile dare la seguente:
Definizione 2.2 Dati due numeri interi m e n si definisce massimo comun diviso-
re di m e n, che scriveremo (m,n), il prodotto di tutti i primi comuni ad entrambe le
fattorizzazioni con il minimo esponente.
Osservazioni
Alla luce dell’unicità della fattorizzazione, è ovvio che tutti i divi-
sori comuni di m e n, sono esattamente i divisori del loro massimo
comun divisore.
Se m e n sono relativamente primi, allora ( m,n ) = 1.
Per calcolare il massimo comun divisore di due numeri, è possibile applicare diret-
tamente la definizione se sono note entrambe le fattorizzazioni, oppure usare
l’algoritmo di Euclide.
L’idea alla base dell’algoritmo è quella della divisione con resto, descritta dal se-
guente:
Teorema 2.1 Se a e b sono due interi, con a > b e b > 0, si può sempre trovare un
numero intero q tale che
abqR
dove R è un numero che soddisfa alla disuguaglianza 0 Rb δ .
L’algoritmo euclideo per il calcolo del massimo comun divisore di due interi a e b,
può essere descritto come segue:
11
abq R ( 0 < R
1
< b )
12 2
bRq R ( 0 < R
2
< R
1
)
1233
RRqR ( 0 < R
3
< R
2
)
CAPITOLO 1: prerequisiti teorici
6
2344
RRqR ( 0 < R
4
< R
3
)
……………… .…………..
finché non si giunge ad un resto nullo.
Infatti le disuguaglianze precedenti mostrano che i successivi resti formano una
successione decrescente di numeri positivi:
b > R
1
> R
2
> R
3
>……> 0
Quindi, dopo al più b operazioni ( spesso molto meno, poiché la differenza tra due r
successivi è, generalmente, maggiore di 1 ), deve apparire il resto 0:
21nnnn
RRqR
1
10
nnn
RRq
Quando ciò accade si ha
( a,b ) = R
n
cioè, in altre parole, ( a,b ) è l’ ultimo resto positivo delle divisioni successive.
Dall’algoritmo euclideo si può dedurre una proprietà molto importante del massimo
comun divisore ( a,b ) di due numeri
Corollario 2.1 Se d = ( a, b), si possono trovare due numeri interi, k e l, tali che
dkalb .
Si può inoltre dimostrare il seguente:
Teorema 2.2 Se un primo divide il prodotto di due numeri, esso deve dividere
(almeno) uno di essi.
3 CONGRUENZE
3.1 Definizione e prime proprietà
Il concetto e la notazione di congruenza, dovuti a Gauss, servono a chiarire e a sem-
plificare ogni ragionamento in cui si presenti il concetto di divisibilità dei numeri
interi per un numero intero fissato m.
Definizione 3.1 Siano a,b e m numeri interi con m > 0.
Si dice che a è congruo b modulo m se m divide la differenza a-b.
In tal caso scriveremo:
a ≡ b ( mod m )
CAPITOLO 1: prerequisiti teorici
7
Enunciamo alcune proprietà
Teorema 3.1 La congruenza su ] è una relazione di equivalenza, cioè valgono
le seguenti proprietà:
¾ proprietà riflessiva:
(mod )aa m { a ] ;
¾ proprietà simmetrica:
se (mod )ab m { (mod )ba m { ,ab ] ;
¾ proprietà transitiva:
se (mod )ab m { e (mod )bc m { (mod )ac m { .
Valgono anche i risultati seguenti, di cui omettiamo la dimostrazione:
Teorema 3.2 Supponiamo che a ≡ b ( mod m ) e α ≡ β ( mod m ). Allora:
¾ (mod ) ,ax y bx y m xy ∆ Ε { ] ;
¾ (mod )ab m ∆ Ε { ;
¾ (mod )
nn
ab m n{ ` .
Corollario 3.1 Se a ≡ b ( mod m ), per ogni polinomio a coefficienti interi P, si ha
che:
P (a) ≡ P (b) ( mod m )
Osserviamo che il precedente teorema ci dice che congruenze aventi lo stesso mo-
dulo possono essere sommate, sottratte o moltiplicate membro a membro, come fos-
sero normali equazioni.
Teorema 3.3 Sia a ≡ b ( mod m ). ||,|.Se d m e d a d b
Teorema 3.4 Se a ≡ b ( mod m ), ( a,m ) ≡ ( b,m ).
Teorema 3.5 Se a ≡ b ( mod m ) e 0 ba m δ , a = b.
Teorema 3.6 Se a ≡ b ( mod m ) e a ≡ b ( mod n ) con m ed n relativamente primi
tra loro, si ha a ≡ b ( mod nm ).
Teorema 3.7 Due numeri interi a e b sono congrui modulo m se e solo se, divisi
per m, danno luogo allo stesso resto.
CAPITOLO 1: prerequisiti teorici
8
Dimostrazione
Se dividiamo a e b per m otteniamo:
0 .amqrcon rm δ
0.bmQRcon Rm δ
Sottraendo membro a membro abbiamo
() 0||ab m qQ rRcon rR m δ
ossia
a – b ≡ r – R ( mod m ).
Ma ciò implica che a ≡ b ( mod m ) se e solo se r ≡ R ( mod m ), ed essendo
0| |rRm δ , per il teorema 3.5, possiamo concludere che r = R.
Vale inoltre il seguente:
Teorema 3.8 (Legge di cancellazione) Supponiamo che:
(mod ) ( , )acbc mechemc d { . Sotto queste ipotesi risulta:
(mod ).
m
ab
d
{
In altri termini, un fattore comune c si può cancellare da ambo i membri di una con-
gruenza a patto di dividere il modulo per il massimo comun divisore d fra m e c.
In particolare se m e c sono primi fra loro, il fattore comune c può essere cancellato.
4 CLASSI DI RESTI E SISTEMI COMPLETI DI RESTI
Definizione 4.1 Siano a e m due interi con m > 0. Si dice classe di resti di a mo-
dulo m, e si indica con â, l’insieme degli interi x tali che x ≡ a ( mod m ).
In simboli
a = { x ] tali che x ≡ a ( mod m ) }
Vediamo ora, senza dimostrarle, alcune proprietà delle classi di resti:
Teorema 4.1 Dato un numero intero m > 0, sono equivalenti le seguenti proprie-
tà:
¾ (mod );ab m {
CAPITOLO 1: prerequisiti teorici
9
¾
ab
;
¾
;ab ζ
Osservazione: le classi di resti modulo m determinano una partizione di ] .
Definizione 4.1 Si dice sistema completo di resti modulo m, un insieme di m in-
teri { a
1
, a
2
, a
3
, ……, a
m
} a due a due incongrui modulo m.
In altri termini un sistema completo di resti modulo m è un insieme composto da m
rappresentanti, uno per ciascuna classe di resti
l
1,2,......,m
.
Una semplice proprietà dei sistemi completi di resti è la seguente:
Teorema 4.2 Sia m ] , m > 0 e sia a un intero tale che ( a,m ) = 1. Allora se x
descrive un sistema completo di resti modulo m, anche ax lo descrive.
Osservazione:
Se ci si riduce al minimo resto positivo modulo m, si trova che il sistema completo
di resti
⊥
123
......,,,
m
ax axaxax ax è una permutazione di ⊥
123
......,,,
m
x xx x .
5 CONGRUENZE LINEARI
Definizione 5.1 Siano a, b, m numeri interi con m > 0. Ogni espressione della
forma:
(mod )axb m {
si dice congruenza lineare.
Definizione 5.2 Ogni intero x
0
tale che sia:
0
(mod )ax b m {
si dice soluzione della congruenza lineare (mod )axb m { .
CAPITOLO 1: prerequisiti teorici
10
Osservazioni:
1. Se una congruenza lineare ammette una soluzione, allora ne ammette infini-
te, tutte congrue fra loro modulo m.
Sia x
0
una soluzione della congruenza lineare (mod )axb m { ; osserviamo
che per ogni n Z , anche
0n
x xmn è soluzione. Infatti:
00
() .
n
ax a x mn ax amn
Ma x
0
è soluzione della congruenza lineare e quindi per qualche intero k si ha
0
ax bmk , da cui
()
n
ax bmk amn bm k an
cioè
(mod ).
n
ax b m {
2. Tutte le soluzioni tra di loro congrue modulo m, si considerano come
un’unica soluzione.
Vediamo alcuni teoremi sulla risolubilità di una congruenza lineare.
Teorema 5.1 Se ( a,m ) = 1, la congruenza lineare
(mod )axb m {
ha un’ unica soluzione modulo m.
Dimostrazione
Ricordiamo che se x descrive un sistema completo di resti modulo m e a è un intero
tale che ( a,m ) = 1, anche ax descrive un sistema completo di resti modulo m,
che riducendosi al minimo resto positivo modulo m risulta essere una permutazione
del primo.
Ma allora esiste un unico valore di x tale che (mod )axb m { e tale valore rappre-
senta l’unica soluzione cercata.
Definizione 5.3 Se ( a,m ) = 1, l’ unica soluzione della congruenza lineare
1(mod )ax m {
è detta reciproco di a modulo m o inverso moltiplicativo di a modulo m.
CAPITOLO 1: prerequisiti teorici
11
Teorema 5.2 Supponiamo che ( a,m ) = d. Allora la condizione necessaria e suffi-
ciente affinché la congruenza lineare
(mod )axb m {
abbia soluzione è che d | b. Se ciò accade la congruenza ha esattamente d soluzioni
distinte, cioè tra loro incongrue modulo m.
Osservazione:
Se d | b, risolvere la congruenza lineare (mod )axb m { equivale a risolvere la
congruenza lineare (mod )
ab m
x
dd
{ , nel senso che l’insieme dei numeri che
soddisfano la prima congruenza coincide con l’insieme dei numeri che soddisfano la
seconda.
Infatti, se x
0
risolve la prima congruenza, per qualche intero k si ha che
0
ax bmk e dividendo ambo i membri per d troviamo che
0
abm
x k
ddd
ovvero x
0
risolve la seconda congruenza.
Viceversa, se x
0
risolve la seconda congruenza, per qualche intero h si ha che
0
abm
x h
ddd
e moltiplicando ambo i membri per d troviamo che
0
x bmh
ovvero x
0
risolve la prima congruenza.
Dimostrazione
Proviamo che se la congruenza lineare (mod )axb m { ha soluzione, allora d | b.
Sia x
0
una soluzione della congruenza lineare; allora per qualche intero k si ha che:
0
ax bmk
da cui
0
bax mk
Ora essendo d = ( a,m ), d | a e d | m, ossia adz e mdw con ,zw Z .
Possiamo allora raccogliere il fattore d a secondo membro, ottenendo che
0
()bd zx wk
Ma ciò vale ad affermare che d | b.
Supponiamo ora che d | b. Per l’osservazione fatta preliminarmente sappiamo che
risolvere la congruenza lineare (mod )axb m { equivale a risolvere la congruenza
lineare (mod )
ab m
x
dd
{ .Consideriamo allora la seconda congruenza.
Ricevi informazioni sui nostri servizi, sulle offerte e non perdere news e consigli su università e lavoro.
