Matematica Discreta a.a. 2006 - 2007 F OGLIO SULL ’ ARITMETICA MODULARE Esercizi relativi all'esercitazione N.6 del 28.XI.06
1. Calcolare a
18per ogni a ∈Z
19.
2. Provare che il quadrato di ogni intero dispari è congruo a 1 modulo 8.
3. Determinare esplicitamente l’insieme delle potenze di esponente r ≥0 della classe di 2 in Z
13, Z
14, Z
15, Z
16.
4. Determinare r ∈ Z
11 ,0≤ r ≤10 tale che r = 538. 5. Usare il piccolo teorema di Fermat per provare che a) 17 divide m= 1+ 11
104
b) 13 divide il numero N= 1+11
12n+6per ogni n≥0.
6. Per ogni n∈ {2,5,13,21,35,46,73,84} stabilire se l’equazione 12 ⋅ x = 7 ha soluzioni in Z
ne, in caso affermativo, determinarle (cfr. Niesi - Es. proposto 6.102 ).
7. Quanti sono gli elementi invertibili di Z
72? 8. Quali sono le due ultime cifre di 2006
1188?
9. Quanti sono gli x interi, 1≤x≤ 1000, tali che 6 ⋅ x = 23 in Z
13?
10. Sia N il numero naturale la cui rappresentazione decimale è a
n.. a
2a
1a
0dove 0≤ a
i≤ 9, i =0,..n ( ossia N=10
n⋅a
n+10
n-1⋅a
n-1+…+10
2⋅a
2+10
1⋅a
1+10
0⋅a
0). Provare che 6 divide N se e solo se 6 divide il numero M= 4 a
n+4 a
n-1+…4a
1+a
0.
11. Sia N un numero naturale con s cifre (nella sua rappresentazione decimale), s≥2.
Determinare quali sono i possibili numeri formati dalle due ultime cifre di N nel caso in cui N sia divisibile per 25.
12. Provare che in Z
8risulta 7
n= 1 se n è pari e 7
n= 7 se n è dispari .
13. Si consideri la funzione f:Z→Z
10definita da f(x)= x : stabilire se f è iniettiva, surgettiva.
14. Sia a ∈Z
pcon p primo, a ≠ 0 . Provare che in Z
psi ha:
y a x
a ⋅ = ⋅ ⇒ x = y .
15. Determinare tutti gli n∈ ù tali che 4 ⋅ 7 = 2
4in Z
n.
16. Determinare tutti gli a ∈ Z tali che a
11= a in Z
11.
R ISPOSTE
1. a
18= 0 se … , altrimenti per il piccolo teorema di Fermat a
18= 1 .
2. Sia a=2k+1 (k∈Z) un intero dispari. Il quadrato è a
2=4k
2+4k+1, quindi a
2-1=4k(k+1).
Siccome uno dei due numeri k, k+1 è pari, ne segue che a
2-1= 8 h (h∈Z) e quindi a
2è congruo a 1 modulo 8.
3. L’insieme delle potenze di 2 in Z
13è Z
13-{ 0 }; in Z
14e Z
15è { 1 , 2 , 4 , 8 }; in Z
16è { 0 , 1 , 2 , 4 , 8 }.
4. r = 4 .
5. a) 11
16⋅6+8= ... = − 1 b) 11
12⋅n+6= ... = − 1
6. In Z
212 ⋅ x = 7 equivale a … : nessuna soluzione. In Z
5unica soluzione x = 1 .
Procedere quindi come nell’Esercizio 5. dell’Esercitazione N.6: per Z
13si trova x = 6 ; per n= 21, 46, 84 non ci sono soluzioni.
7. ϕ(72) = ϕ(3
2) ϕ(2
3) = … = 24
8. In Z
100si ha 2006
1188= 6
1188. Calcolando 6
2= … , 6
3= … 6 , … si trova 6
1188= 36 . Ultime due cifre: 36.
9. 6 ⋅ x = 23 in Z
13ha la soluzione x = 6 , ma 6 = {6+13k|k∈Z}, 1000-6 = 13⋅76+6, quindi il numero di interi richiesti è 77.
10. Procedere come a pag.14 , Esercitazione N.6.
11. 0,25,50,75.
12. 7
2k7
2⎟
k= ... = 1
⎠ ⎞
⎜ ⎝
= ⎛ ; 7
2k+1= 7
2k⋅ 7 = 7 .
13. f è surgettiva, ma non è iniettiva, ad esempio 10≠0 ma f(10)=f(0)= 0 . 14. a è invertibile in Z
p, quindi moltiplicando a sinistra per a
−1si ha la tesi.
15. 28 = 16 ... ⇒ 12 = 0 che in Z
nvale se n divide 12, quindi n= 2,3,4,6.
16. Per il piccolo teorema di Fermat a
10= 1 se … . Ogni a∈Z va bene.
