Home

Federica EU

1/13

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 → Z_m 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 b₁ e u numeri tali che d=au+mv e b=db₁
⇒ b=db₁= (au+mv)b₁ =aub₁ + mvb₁ ≡ aub₁ (mod m)
⇒ ub₁ è 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 b₁ e u numeri tali che d=au+mv e b=db₁ . Allora ub₁ è soluzione dell’equazione congruenziale ax ≡ b (mod m).
(2) Sia m₁ tale che m=dm₁ , 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=db₁= (au+mv)b₁ =aub₁ + mvb₁ ≡ aub₁ (mod m)
⇒ ub₁ è 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=dm₁ è un divisore di ac-an=a(c-n)
⇒ se a₁ è il numero intero tale che a=da₁ , allora m₁ è un divisore di a₁(c-n)
⇒ m₁ è un divisore di c-n (perché m₁ e a₁ 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+km₁
⇒ ar = a(c+km₁) = ac+akm₁ ≡ ac ≡ b (mod m)
⇒ r è soluzione dell’equazione congruenziale ax ≡ b (mod m).

Sistemi di equazioni congruenziali – prime definizioni

Definizione 4.5
Siano m₁ , … , m_t numeri interi maggiori di 1. Se a₁ , … , a_t , b₁ , … , b_t sono numeri interi, l’insieme
{ a₁x ≡ b₁ (mod m₁) , … , a_tx ≡ b_t (mod m_t) } 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 a_ix ≡ b_i (mod m_i).

Teorema Cinese del Resto

Teorema 4.6 (Teorema Cinese del Resto)
Siano m₁ , … , m_t numeri interi maggiori di 1 e siano b₁ , … , b_t numeri interi.
Si supponga che m₁ , … , m_t 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 c_i 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≡b_h (mod m_h).
Allora b_h m’_h c_h ≡ b_h (mod m_h) (perché m’_h c_h ≡1 (mod m_h); d’altra parte, per ciascun j≠h, b_j m’_j c_j ≡0 (mod m_h)
$\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≡b_h (mod m_h) .

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 m_i) e quindi m_i è un divisore di c-n
⇒ dunque m₁∙…∙m_t è 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 m₁∙…∙m_t) e quindi per ciascun i=1,…,t si ha che r ≡c (mod m_i)
⇒  per ciascun i=1,…,t si ha che r≡b_i (mod m_i)
⇒  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 n₁ ,n₂ numeri interi maggiori di 1. Se n₁ e n₂ sono coprimi, allora φ(n₁n₂)=φ(n₁)φ(n₂).
Dimostrazione
Siano X₁ ={ bє N | 1≤b≤n₁ , (b,n₁)=1}, e X₂ ={ bє N | 1≤b≤n₂ , (b,n₂)=1}.
Sia poi X= { bє N | 1≤b≤n₁n₂ , (b,n₁n₂)=1}.
Allora |X₁|=φ(n₁) , |X₂|=φ(n₂) , |X|=φ(n₁n₂).
Se b è un qualunque elemento di X, allora b è coprimo con n₁n₂ , sicché per ciascun i=1,2, il resto della divisione euclidea di b per n_i è coprimo con n_i , e quindi appartiene a X_i .

Funzione di Eulero del prodotto di due numeri coprimi

Si consideri la funzione f:X → X₁ x X₂ definita ponendo f(b)=(r₁ , r₂), dove r_i è il resto delle divisione euclidea di b per n_i .
Sia (b₁ , b₂) un qualunque elemento di X₁ x X₂, 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≤n₁n₂ .
Per ciascun i=1,2, (b_i ,n_i)=1 e quindi (b,n₁n₂)=1 ⇒ b appartiene a X.
D’altra parte, $[b]_{n_i}=[b_i]_{n_i}$ e 1≤b_i ≤n_i -1⇒ b_i è il resto delle divisione euclidea di b per n_i  f(b)=(b₁ , b₂). 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)=(r₁ , r₂)
⇒ 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≤n₁n₂-1 e 1≤b≤n₁n₂-1). Dunque f è iniettiva.
Dalla biettività di f segue che |X|=|X₁ x X₂|, 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)³).
Dimostrazione
(1) Calcolare φ(pq)= (p-1)(q-1) ha complessità O((log p)(log q)).
(2) Siano p₁ e p₂ i due primi da determinare
⇒ p₁p₂=n e p₁+p₂ = n-φ(n)+1.
Si ponga b=n-φ(n)+1
⇒ p₁ e p₂ sono le due soluzioni dell’equazione x²-bx+n=0
⇒ p₁ e p₂ 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)³).