Teoria dei numeri
0,xxx…xxxxxxxxx
2013-esima cifra
Suggerimento: prova con 1/3, 1/11, 1/7, poi con 1/2013
4
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+4n
qualsiasi 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 / n
e ha calcolato le ultime due cifre (cioè le due più
a destra) del prodotto f(1) * f(2) * … * f(99).
Che cosa ha trovato?