Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Maria De Falco » 4.Equazioni congruenziali lineari e Teorema Cinese del Resto


Equazioni congruenziali – prime definizioni

Definizione 4.1
Sia m un numero intero tale che m>1, e siano a,b numeri interi.
La funzione

f: Z → Zm definita ponendo f(c)=[ac-b]m

si chiama equazione congruenziale lineare di termini a e b e modulo m e si denota con il simbolo

ax ≡ b (mod m).

Definizione 4.2
Sia m un numero intero tale che m>1, e siano a,b numeri interi.
Si dice che un numero intero c è soluzione dell’equazione congruenziale ax b (mod m) se ac ≡ b (mod m).

Esistenza delle soluzioni di un’equazione congruenziale

Proposizione 4.3
Sia m un numero intero tale che m>1, e siano a,b numeri interi.
L’equazione ax ≡ b (mod m) ha soluzioni se e solo se b è multiplo dei massimi comun divisori di a e m.
Dimostrazione
Si supponga in primo luogo che l’equazione ax ≡ b (mod m) abbia una soluzione c
⇒ ac ≡ b (mod m)
⇒ esiste un numero intero k tale che b=ac+km
⇒ b è multiplo di ogni divisore comune di a e m.
Viceversa, si supponga che b sia multiplo dei massimi comun divisori di a e m; sia d un massimo comun divisore di a e m e siano b1 e u numeri tali che d=au+mv e b=db1
⇒ b=db1= (au+mv)b1 =aub1 + mvb1 ≡ aub1 (mod m)
⇒ ub1 è soluzione dell’equazione congruenziale ax ≡ b (mod m).

Caratterizzazione delle soluzioni

Teorema 4.4
Sia m un numero intero tale che m>1, e siano a,b numeri interi tali che b è multiplo dei massimi comun divisori di a e m. Allora:
(1) Sia d un massimo comun divisore di a e m e siano b1 e u numeri tali che d=au+mv e b=db1 . Allora ub1 è soluzione dell’equazione congruenziale ax ≡ b (mod m).
(2) Sia m1 tale che m=dm1 , e sia c una soluzione dell’equazione congruenziale ax ≡ b (mod m). Allora l’insieme delle soluzioni di tale equazione congruenziale coincide con [c]_{m_1} .

Caratterizzazione delle soluzioni

Dimostrazione
(1) Dalle ipotesi segue che b=db1= (au+mv)b1 =aub1 + mvb1 ≡ aub1 (mod m)
⇒ ub1 è soluzione dell’equazione congruenziale ax ≡ b (mod m).
(2) Sia n una qualunque soluzione dell’equazione congruenziale ax ≡ b (mod m)
⇒ an ≡ b ≡ an (mod m)
⇒ m=dm1 è un divisore di ac-an=a(c-n)
⇒ se a1 è il numero intero tale che a=da1 , allora m1 è un divisore di a1(c-n)
⇒ m1 è un divisore di c-n (perché m1 e a1 sono coprimi)
⇒ n appartiene a [c]_{m_1} .
Viceversa, sia r un elemento di [c]_{m_1}
⇒ esiste un numero intero k tale che r=c+km1
⇒ ar = a(c+km1) = ac+akm1 ≡ ac ≡ b (mod m)
⇒ r è soluzione dell’equazione congruenziale ax ≡ b (mod m).

Sistemi di equazioni congruenziali – prime definizioni

Definizione 4.5
Siano m1 , … , mt numeri interi maggiori di 1. Se a1 , … , at , b1 , …  , bt sono numeri interi, l’insieme
{ a1x ≡ b1 (mod m1) , … , atx ≡ bt (mod mt) } si chiama sistema di equazioni congruenziali lineari e si indica con il simbolo
\left\{\begin{array}{ll}a_1x\equiv b_1(mod\;m_1) \\  ........................ \\ ........................ \\ a_tx\equiv b_t(mod\; m_t)\end{array}
Definizione 4.6
Si dice che un numero intero c  è soluzione del sistema di equazioni congruenziali
\left\{\begin{array}{ll}a_1x\equiv b_1(mod\;m_1) \\  ........................ \\ ........................ \\ a_tx\equiv b_t(mod\; m_t)\end{array}
se c è soluzione di ciascuna equazione congruenziale aix ≡ bi (mod mi).

Teorema Cinese del Resto

Teorema 4.6 (Teorema Cinese del Resto)
Siano m1 , … , mt numeri interi maggiori di 1 e siano b1 , … , bt numeri interi.
Si supponga che m1 , … , mt siano a due a due coprimi. Allora
(1) si ponga per ciascun i=1,…,t , m'_i =\prod _{j\not= i}m_j, e sia ci un numero intero tale che [c_i]_{m_i}=[m'_i]_{m_i}^{-1}; ne segue che \sum _{i=1, \dots t} b_im'_ic_i è soluzione del sistema
\left\{\begin{array}{ll}a_1x\equiv b_1(mod\;m_1) \\  ........................ \\ ........................ \\ a_tx\equiv b_t(mod\; m_t)\end{array}
(2) Se c è soluzione di tale sistema, allora l’insieme delle soluzioni del sistema coincide con [c]_{m_1 \dots m_t}.

Teorema Cinese del Resto

Dimostrazione 
(1) Sia h un qualunque elemento dell’insieme {1,…,t}, e si consideri l’equazione x≡bh (mod mh).
Allora bh m’h ch ≡ bh (mod mh) (perché m’h ch ≡1 (mod mh); d’altra parte, per ciascun j≠h, bj m’j cj ≡0 (mod mh)
\sum _{i=1, \dots t} b_i m'_i c_i \; = \; b_h m'_h c_h + \sum _{j \not=h} b_j m'_j c_j
è soluzione dell’equazione x≡bh (mod mh) .

Teorema Cinese del Resto

(2) Sia n una qualunque soluzione del sistema di equazioni congruenziali
⇒ per ciascun i=1,…,t si ha che c≡n (mod mi ) e quindi mi è un divisore di c-n
⇒ dunque m1∙…∙mt è un divisore di c-n e quindi n appartiene a [c]_{m_1 \dots m_t}.
Viceversa, sia r un qualunque elemento di [c]_{m_1 \dots m_t}
⇒  r≡c (mod m1∙…∙mt) e quindi per ciascun i=1,…,t si ha che r ≡c (mod mi )
⇒  per ciascun i=1,…,t si ha che r≡bi (mod mi )
⇒  r è soluzione del sistema di equazioni congruenziali.

Teorema Cinese del Resto

La prima formulazione originale del teorema è contenuta in un libro, scritto nel III secolo, del matematico cinese Sun Zi; il teorema è stato successivamente inserito in un libro scritto da Qin Jiushao nel 1247.
Il Teorema Cinese del Resto verrà applicato diverse volte nel seguito.

Nella prossima slide verrà presentata una prima applicazione del Teorema Cinese del Resto: utilizzando tale teorema si fornirà una caratterizzazione, che risulterà molto utile in seguito, del valore che la funzione di Eulero assume per un numero che sia prodotto di due interi coprimi.

Funzione di Eulero del prodotto di due numeri coprimi

Teorema 4.7
Siano n1 ,n2 numeri interi maggiori di 1. Se n1 e n2 sono coprimi, allora φ(n1n2)=φ(n1)φ(n2).
Dimostrazione
Siano X1 ={ bє N  | 1≤b≤n1 , (b,n1)=1}, e X2 ={ bє N  | 1≤b≤n2 , (b,n2)=1}.
Sia poi X= { bє N  | 1≤b≤n1n2 , (b,n1n2)=1}.
Allora |X1|=φ(n1) , |X2|=φ(n2) , |X|=φ(n1n2).
Se b è un qualunque elemento di X, allora b è coprimo con n1n2 , sicché per ciascun i=1,2, il resto della divisione euclidea di b per ni è coprimo con ni , e quindi appartiene a Xi .

Funzione di Eulero del prodotto di due numeri coprimi

Si consideri la funzione f:X → X1 x X2 definita ponendo f(b)=(r1 , r2), dove ri è il resto delle divisione euclidea di b per ni .
Sia (b1 , b2) un qualunque elemento di X1 x X2 , e si consideri  il sistema di equazioni congruenziali
\left\{\begin{array}{ll} x\equiv b_1(mod\;n_1) \\ x\equiv b_2(mod\; n_2)\end{array}
Per il Teorema Cinese del Resto, esiste una soluzione b di tale sistema tale che 0≤b≤n1n2 .
Per ciascun i=1,2, (bi ,ni)=1 e quindi (b,n1n2)=1  ⇒  b appartiene a X.
D’altra parte, [b]_{n_i}=[b_i]_{n_i} e 1≤bi ≤ni -1⇒   bi è il resto delle divisione euclidea di b per ni  f(b)=(b1 , b2). Dunque f è suriettiva.

Funzione di Eulero del prodotto di due numeri coprimi

Siano ora b,c elementi di X tali che f(b)=f(c)=(r1 , r2)
⇒ b e c sono soluzioni del sistema di equazioni congruenziali
\left\{\begin{array}{ll} x\equiv r_1(mod\;n_1) \\ x\equiv r_2(mod\; n_2)\end{array}
⇒ per il Teorema Cinese del Resto, b=c (perché 1≤b≤n1n2-1 e 1≤b≤n1n2-1). Dunque f è iniettiva.
Dalla biettività di f segue che |X|=|X1 x X2|, e quindi l’asserto.

Funzione di Eulero del prodotto di due primi distinti

Prposizione 4.8 
(1) Se p e q sono primi positivi distinti, è possibile determinare φ(pq), partendo da p e q, con complessità

O((log p)(log q)).

(2) Se n è un numero naturale prodotto di due primi distinti, è possibile determinare i primi, partendo da n e φ(n), con complessità O((log n)3).
Dimostrazione
(1) Calcolare φ(pq)= (p-1)(q-1) ha complessità O((log p)(log q)).
(2) Siano p1 e p2  i due primi da determinare
⇒ p1 p2=n e  p1+p2 = n-φ(n)+1.
Si ponga b=n-φ(n)+1
⇒ p1 e  p2 sono le due soluzioni dell’equazione x2-bx+n=0
⇒ p1 e  p2 si calcolano con la formula \frac{-b \pm \sqrt{b^2-4n}}{2}, e tale calcolo (partendo da n e φ(n) ) ha complessità O((log n)3).

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion