Teoria dei Numeri

(1)

Teoria dei Numeri

Lezione del 15/12/2009

Stage di Treviso Progetto Olimpiadi

(2)

Criteri di Divisibilità

• 2: ultima cifra pari

• 3: somma (o somma della somma) delle cifre divisibile per 3

• 4: ultima due cifre divisibili per 4

• 2 ⁿ : ultima n cifre divisibili per 2 ⁿ

• 5: ultima cifra divisibile per 5

• 9: somma (o somma delle somma) delle cifre divisibile per 9

• 11: somma delle cifre in posizione pari uguale alla

somma delle cifre in posizione dispari

(3)

Congruenze

• Dati due numeri naturali n ed m, sono

univocamente identificati altri due numeri

detti quoziente e resto delle divisione intera di n per m: n=q*m+r con 0≤r<m

• Una relazione è detta di equivalenza se valgono le proprietà:

• Riflessiva

• Simmetrica

• Transitiva

(4)

• La relazione “ha lo stesso resto di..nella divisione per m” con m naturale è di

equivalenza perché

• a ha lo stesso di a nella divisione per m

• Se a ha lo stesso resto di b, b ha lo stesso resto di a (sempre nella divisione per m)

• Se a ha lo stesso resto di b e b ha lo stesso

resto di c allora a ha lo stesso resto di c (nella

divisione per m)

(5)

• I numeri naturali vengono così ad essere suddivisi in “classi di equivalenza”. Per

esempio per congruenza modulo 4 le classi saranno

• 0,4,8,12,16,…

• 1,5,9,13,17,…

• 2,6,10,14,18,…

• 3,7,11,15,19,…

(6)

Proprietà delle congruenze

• Se a=m*q ₁ +r ₁ allora a≡r ₁ (m)

• Somma: se b=mq ₂ +r ₂ e quindi b≡r ₂ (m) allora a+b=m(q ₁ +q ₂ )+(r ₁ +r ₂ ) ≡r ₁ +r ₂ (m)

• Si comportano bene rispetto alla somma

• Differenza: come la somma solo che poiché la sottrazione non è un’operazione interna ad N è necessario “estendere” le congruenze in Z

• Ricordiamoci che in questo caso il resto deve essere sempre positivo, quindi per esempio:

• -3:5=-1 con resto +2 quindi -3≡2

(7)

• Prodotto:

• a*b=m(mq ₁ q ₂ +q ₁ r ₂ +q ₂ r ₁ )+(r ₁ r ₂ ) ≡r ₁ r ₂ (m)

• Si comportano bene rispetto al prodotto

(8)

Residui quadratici

• Nello studiare la divisibilità per qualche numero di una certa quantità funzione di alcuni numeri naturali

dovremo andare a provare tutte le possibili classi di resto per ognuno dei naturali

• Una semplificazione può nascere se compaiono dei quadrati o altre potenze di numeri naturali. Infatti per alcuni moduli (per esempio modulo 3) i quadrati non possono appartenere a qualsiasi classe di resto

• Infatti se n≡0 (3) n2≡0 (3)

• Se n≡1 (3) n

²

≡1*1=1 (3)

• Se n≡2 (3) n

²

≡2*2=4≡1 (3)

• Quindi un quadrato non è mai congruo a 2 modulo 3!

(9)

• Altri residui quadratici sono:

• 0 e 1 per modulo 4 (0 per i numeri pari e 1 per i numeri dispari)

• 0,1,-1 per modulo 5

• 0,1,4 per modulo 8

(10)

• Esercizio di esempio

• Dimostrate che n ³ +11n è divisibile per 3 qualsiasi sia n Naturale

• Soluzione:

• Calcoliamo la congruenza modulo 3 di tale quantità nei 3 casi possibili per n:

• n≡0 (3) n ³ +11n≡0 (3) è divisibile

• n≡1 (3) n ³ +11n≡1+11=12≡0 (3) è divisibile

• n≡2 (3) n ³ +11n≡8+22=30≡0 (3) è divisibile

(11)

• Altro svolgimento possibile (uso i residui quadratici)

• n ³ +11n=n(n ² +11)

• Se n≡0 (3) n(n ² +11) ≡0*11=0 (3)

• Sennò n ² ≡1 (3) e quindi n(n ² +11) ≡n*12≡0 (3)

• Altro metodo di risoluzione possibile: per

induzione

(12)

Inverso modulo m

• Possiamo chiederci di risolvere il seguente problema: quando esistono soluzioni di

• a*b≡c (m)

• Conoscendo a, c ed m sapere se esiste b che rende vera l’identità o no

• NOTA: se ne esiste uno l’equazione ha infinite

soluzioni. Perché?

(13)

• Cominciamo dal caso più facile c=1

• In questo caso:

• Se MCD(a,m)=1 allora esiste sempre b che risolve l’equazione

• Se MCD(a,m)>1 in generale non è sempre possibile che esista b

• b è detto l’inverso di a modulo m

• DOMANDA: Se c>1 che ipotesi è sufficiente

richiedere perché esista b?

(14)

Altri esercizi

• Dimostrare che n ³ +11n è sempre divisibile per 6

• HINT: invece di usare le classi di resto modulo 6 ricordiamoci che 6=3*2

• Dimostrare che n(n+1)/2 è intero

• Dimostrare che n(n+1)(2n+1)/6 è intero

• Determina se 2004 ²⁰⁰⁵ è somma di due

quadrati perfetti

(15)

Piccolo Teorema di Fermat

• Se mi interessano congruenze con un modulo p primo, MCD(a,p)=1 vale il piccolo teorema di fermat:

• A ^p-1 ≡1 (p)

• Corollario a ^p ≡a (p)

(16)

Teorema di Bezout

• Data l’equazione in due variabili na+mb=c con a e b interi.

• Questa equazione ha infinite soluzioni intere (n,m) se e solo se MCD(a,b)|c.

• Consideriamo il caso MCD(a,b)=c

• Dividendo tutto per ci si ottiene una nuova equazione:

• nc+md=1 con MCD(c,d)=1

• A questo punto cosa posso applicare, per

dimostrare l’esistenza di una coppia (n,m)?

(17)

• Come si trovano in pratica gli n,m?

• Si usa il metodo delle divisioni euclidee successive:

• Esempio c=44 d=17

• 44=17*2+10

• 17=10*1+7

• 10=7*1+3

• 7=3*2+1

• Il resto dell’ultima riga è l’MCD

• Ora si prosegue dal basso verso l’alto ricavando i

resti da ogni riga:

(18)

• 1=7-3*2

• 3=10-7 => 1=7-(10-7)2=73-10*2

• 7=17-10=> 1=(17-10)3-102=173-105

• 10=44-172 =>173-(44-172)5=1713-445

• n=-5 m=13

Teoria dei Numeri

Teoria dei Numeri

Lezione del 15/12/2009

Stage di Treviso Progetto Olimpiadi

Criteri di Divisibilità

• 2: ultima cifra pari

• 3: somma (o somma della somma) delle cifre divisibile per 3

• 4: ultima due cifre divisibili per 4

• 2 n : ultima n cifre divisibili per 2 n

• 5: ultima cifra divisibile per 5

• 9: somma (o somma delle somma) delle cifre divisibile per 9

• 11: somma delle cifre in posizione pari uguale alla

somma delle cifre in posizione dispari

Congruenze

• Dati due numeri naturali n ed m, sono

univocamente identificati altri due numeri

detti quoziente e resto delle divisione intera di n per m: n=q*m+r con 0≤r<m

• Una relazione è detta di equivalenza se valgono le proprietà:

• Riflessiva

• Simmetrica

• Transitiva

• La relazione “ha lo stesso resto di..nella divisione per m” con m naturale è di

equivalenza perché

• a ha lo stesso di a nella divisione per m

• Se a ha lo stesso resto di b, b ha lo stesso resto di a (sempre nella divisione per m)

• Se a ha lo stesso resto di b e b ha lo stesso

resto di c allora a ha lo stesso resto di c (nella

divisione per m)

• I numeri naturali vengono così ad essere suddivisi in “classi di equivalenza”. Per

esempio per congruenza modulo 4 le classi saranno

• 0,4,8,12,16,…

• 1,5,9,13,17,…

• 2,6,10,14,18,…

• 3,7,11,15,19,…

Proprietà delle congruenze

• Se a=m*q 1 +r 1 allora a≡r 1 (m)

• Somma: se b=m*q 2 +r 2 e quindi b≡r 2 (m) allora a+b=m*(q 1 +q 2 )+(r 1 +r 2 ) ≡r 1 +r 2 (m)

• Si comportano bene rispetto alla somma

• Differenza: come la somma solo che poiché la sottrazione non è un’operazione interna ad N è necessario “estendere” le congruenze in Z

• Ricordiamoci che in questo caso il resto deve essere sempre positivo, quindi per esempio:

• -3:5=-1 con resto +2 quindi -3≡2

• Prodotto:

• a*b=m(mq 1 q 2 +q 1 r 2 +q 2 r 1 )+(r 1 r 2 ) ≡r 1 r 2 (m)

• Si comportano bene rispetto al prodotto

Residui quadratici

• Nello studiare la divisibilità per qualche numero di una certa quantità funzione di alcuni numeri naturali

dovremo andare a provare tutte le possibili classi di resto per ognuno dei naturali

• Una semplificazione può nascere se compaiono dei quadrati o altre potenze di numeri naturali. Infatti per alcuni moduli (per esempio modulo 3) i quadrati non possono appartenere a qualsiasi classe di resto

• Infatti se n≡0 (3) n2≡0 (3)

• Se n≡1 (3) n

≡1*1=1 (3)

• Se n≡2 (3) n

≡2*2=4≡1 (3)

• Quindi un quadrato non è mai congruo a 2 modulo 3!

• Altri residui quadratici sono:

• 0 e 1 per modulo 4 (0 per i numeri pari e 1 per i numeri dispari)

• 0,1,-1 per modulo 5

• 0,1,4 per modulo 8

• Esercizio di esempio

• Dimostrate che n 3 +11n è divisibile per 3 qualsiasi sia n Naturale

• Soluzione:

• Calcoliamo la congruenza modulo 3 di tale quantità nei 3 casi possibili per n:

• n≡0 (3) n 3 +11n≡0 (3) è divisibile

• n≡1 (3) n 3 +11n≡1+11=12≡0 (3) è divisibile

• n≡2 (3) n 3 +11n≡8+22=30≡0 (3) è divisibile

• Altro svolgimento possibile (uso i residui quadratici)

• n 3 +11n=n(n 2 +11)

• Se n≡0 (3) n(n 2 +11) ≡0*11=0 (3)

• Sennò n 2 ≡1 (3) e quindi n(n 2 +11) ≡n*12≡0 (3)

• Altro metodo di risoluzione possibile: per

induzione

Inverso modulo m

• Possiamo chiederci di risolvere il seguente problema: quando esistono soluzioni di

• a*b≡c (m)

• Conoscendo a, c ed m sapere se esiste b che rende vera l’identità o no

• NOTA: se ne esiste uno l’equazione ha infinite

soluzioni. Perché?

• Cominciamo dal caso più facile c=1

• In questo caso:

• Se MCD(a,m)=1 allora esiste sempre b che risolve l’equazione

• 2 ⁿ : ultima n cifre divisibili per 2 ⁿ

• Se a=m*q ₁ +r ₁ allora a≡r ₁ (m)

• Somma: se b=mq ₂ +r ₂ e quindi b≡r ₂ (m) allora a+b=m(q ₁ +q ₂ )+(r ₁ +r ₂ ) ≡r ₁ +r ₂ (m)

• a*b=m(mq ₁ q ₂ +q ₁ r ₂ +q ₂ r ₁ )+(r ₁ r ₂ ) ≡r ₁ r ₂ (m)

• Dimostrate che n ³ +11n è divisibile per 3 qualsiasi sia n Naturale

• n≡0 (3) n ³ +11n≡0 (3) è divisibile

• n≡1 (3) n ³ +11n≡1+11=12≡0 (3) è divisibile

• n≡2 (3) n ³ +11n≡8+22=30≡0 (3) è divisibile

• n ³ +11n=n(n ² +11)

• Se n≡0 (3) n(n ² +11) ≡0*11=0 (3)

• Sennò n ² ≡1 (3) e quindi n(n ² +11) ≡n*12≡0 (3)

• Dimostrare che n ³ +11n è sempre divisibile per 6

• Determina se 2004 ²⁰⁰⁵ è somma di due

• A ^p-1 ≡1 (p)

• Corollario a ^p ≡a (p)

• 3=10-7 => 1=7-(10-7)2=73-10*2

• 7=17-10=> 1=(17-10)3-102=173-105

• 10=44-172 =>173-(44-172)5=1713-445