2014-2015TORINO

Teoria dei numeri

4

0,xxx…xxxxxxxxx

2013-esima cifra

Suggerimento: prova con 1/3, 1/11, 1/7, poi con 1/2013

TEORIA DEI NUMERI

La teoria dei numeri si occupa di:• studio delle proprietà dei numeri interi,

divisibilità, primalità (MCD, mcm, CONGRUENZE)

• equazioni a valori interi (EQUAZIONI DIOFANTEE)

Affronteremo:• Dividere e essere multiplo: divisione con resto• Moduli• Primalità: due definizioni. Fattorizzazione.• MCD e mcm: algoritmo di Euclide • Teorema di Bezout: dati (a, b), h *a +k *B sono

tutti e soli i multipli dell’MCD. Segue: se (a, b) multipli di d…

Inoltre:

• Criteri di congruenza: 2^n, 5^n, 3, 9, 11• Congruenze modulo n• Somma e prodotto di moduli • Inversi• Semplificazione SSE MCD=1. Altrimenti,

semplifico anche i moduli.• Sistemi

Esempio

Alberto, Beppe e Carlo vogliono trovarsi dopo il capodanno una sera per rievocare i bei vecchi tempi. Alberto ha una serata libera ogni 6 giorni a partire dal 2 di Gennaio, Beppe ha invece una sola serata libera ogni 15 giorni a partire dall’11, e Carlo ne ha una libera ogni 8 giorni a partire dal 5. Quando riusciranno a incontrarsi tutti e tre? E se invece Alberto e Beppe vogliono incontrarsi da soli?

Soluzione di un sistema

Si può:• Ridurlo (moduli coprimi tra loro) e andare per

tentativi;• Usare: n1*k + a1 = n2*h + a2 e risolvere la

DIOFANTEA.

Esempi

• Calcolare 4931^4931 mod 9• Calcolare 2^546321 mod 12 (residui quadratici)• Trovare la cifra delle unità di 2007^2007• Calcolare le ultime due cifre di 2007^2007^2007• Quanto vale la somma delle cifre di

999.999.999.999.995^2?• Quanto vale la somma delle cifre di (10^2012 +

1)^3?

Note

• Trovare la cifra delle unità di una certa espressione, o le due cifre più a destra, o simili, significa in realtà calcolare il valore dell’espressione data modulo 10, o 100, o altre potenze di 10. Esempio: 2007^2007= 7^2007 =7^3 =3 (mod 10)

• Alcuni problemi riguardano la divisibilità di un numero per un altro, e possono efficacemente essere schematizzati con una relazione del tipo x 0 (mod d ).

Feb 2012 *

Dato un qualsiasi intero positivo n, chiamiamo ciclostilato di n il numero che si ottiene concatenando 2012 scritture di n (in base 10). Per esempio il ciclostilato di 314 `e 314314314 . . . 314, dove le cifre “314” si ripetono 2012 volte.Determinare tutti gli interi positivi m tali che il ciclostilato di m sia multiplo di 9.Determinare tutti gli interi positivi m tali che il ciclostilato di m sia multiplo di 11.

Feb 2011 *Dimostrare che tutte le potenze di 3 hanno la cifra delle decine pari.

Arch 2012 **Qual è il più grande numero che divide

n5-5n3+4nqualsiasi sia il numero naturale n ≥ 3?

2012 Il primo esercizio di Dotto *

Dotto si sta esercitando con i numeri. Ha preso la funzione f(n) = 200 - 2n / ne ha calcolato le ultime due cifre (cioè le due più a destra) del prodotto f(1) * f(2) * … * f(99). Che cosa ha trovato?