Teoria dei Numeri

Teoria dei Numeri

Lezione del 28/02/2011

Stage di Acireale Progetto Olimpiadi

Criteri di Divisibilità

• 2: ultima cifra pari

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

• 4: ultime due cifre divisibili per 4

• 2

: ultime 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 o differenti per

multipli di 11

Divisibilità

• Se p è primo p|ab implica che p|a o p|b

• Se m non è primo, m|ab non implica che m|a o m|b

• Th. Fondamentale: ogni numero intero

positivo è univocamente esprimibile come

prodotto dei suoi fattori primi

MCD e mcm

• Due numeri a e b sono detti primi fra loro o relativamente primi se MCD(a,b)=(a,b)=1

• a*b=MCD(a,b)*mcm(a,b)

• (a,b)=(a,b-a)=(a,b-m*a), e se b=m*a+r allora

(a,b)=(a,r)

Fattorizzazione

• Alcuni prodotti notevoli

• a ² -b ² =(a+b)(a-b)

• a ⁿ -b ⁿ =(a-b)(a ^n-1 +a ^n-2 b+…+b ^n-1 )

• Per n dispari, posso sostituire b->-b e ottengo

• a ⁿ +b ⁿ =(a+b)(a ^n-1 -a ^n-2 b+…+b ^n-1 )

• Esercizio: fattorizzare a ⁴ +4b ⁴

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

+r

allora a≡r

(m)

• Somma: se b=m*q

+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 (5)

• Prodotto:

• a*b=m(mq ₁ q ₂ +q ₁ r ₂ +q ₂ r ₁ )+(r ₁ r ₂ ) ≡r ₁ r ₂ (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) n

≡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 ³ +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

• 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

• Altri esercizi: n ³ +11n sempre multiplo di 6

• n ⁴ -n ² sempre multiplo di 12

• n ⁵ -n sempre multiplo di 30