Osservazioni di aritmetica modulare

Osservazioni di aritmetica modulare

E sui teoremi di Fermat e di Wilson 1

Di Guido Carolla

Sunto. Il presente articolo ha fine prevalentemente didattico. Spesso viene perseguito il metodo

induttivo, dal concreto all’astratto, a cominciare dal primo paragrafo. Il percorso seguito ha lo

scopo, speriamo condiviso dal lettore, di rendere più comprensibili alcune argomentazioni che

trattano di aritmetica modulare con i numeri (primi e non), con riferimenti finali alla Teoria dei

gruppi.

Introduzione sui moduli

Dato un numero intero n > 1 ci sono n resti possibili della divisione di un qualsiasi intero per n.

Z

L'insieme di questi resti viene indicato con .

n

Z = { 0, 1, 2, …, n-1}

n

Per esempio: Z = { 0, 1, 2, 3, 4, 5, 6}

7

Denotiamo inoltre con ( )

mod n res x

x oppure con n

n.

x

il resto della divisione di per

r r

Quindi l'espressione = 27 mod 14, assegna ad il valore 13.

n, n classi di resto

In generale, dato un numero intero positivo i numeri interi si distribuiscono in

modulo n, n.

a seconda del resto che danno quando vengono divisi per

Due interi a, b stanno nella stessa classe di resto se e solo se

a = b mod n (1)

La (1) è perfettamente equivalente alla

n divide a-b (2)

a b n,

Si dice anche che e si scrive:

è congruo o congruente a modulo

a b (mod n).

≡

1 Docente ordinario di matematica e dirigente scolastico in ogni ordine di scuola a r. 1

Nel prosieguo cercheremo di dare qualche ulteriore elementare spiegazione ed adotteremo una

sintetica simbologia modulare per consentire la comprensione dell’argomento anche ai non addetti

ai lavori. ⇒

, [] 9 , possiamo avere le varie classi dei resti mod 9:

m n m n k

∀ ∈ − =

9

[ ] { }

0 ..., 27

, 18

, 9

,

0

,

9

,

18

, 27

,

36

,... ,

= − − −

9 [ ]

[ ] { }

{ }

1 2

..., 10

, 1

,

1

,

10

,

19

, 28

,

37

,... ..., 11

, 2

, 2

,

11

, 20

, 29

,

38

,...

, , …,

= − − = − −

9 9

[ ] { }

8 ..., 35

, 26

, 17

,

8

,

17

, 26

,

35

,... .

= − − −

9

Due teoremi sul mod 9

Lo scopo didattico dell’articolo ci suggerisce di ricorrere all’impostazione dei due teoremi che

seguono.

Teorema 1

Il modulo 9 del cubo di ogni numero primo, con eccezione del 3, è 1 oppure 8.

Dimostrazione:

2 che i possibili resti modulo 9 dei numeri primi, ad eccezione del 3

E` noto

[ ] [] [ ] [ ] [ ] [ ] [ ]

{ }

\ 3

p 1 2 4 5 7 8

1

, 2

, 4

,

5

,

7

,

8 , sono , ciò vuol dire che

= 9 9 9 9 9 9

9

dividendo ogni primo per 9 i resti sono esclusivamente 1, 2, 4, 5, 7, 8, ossia facendo la

somma delle cifre dei numeri primi e sottraendo sempre 9 si hanno solo e sempre 1, 2,

4, 5, 7, 8.

Ora, adottando la proprietà delle potenze dei moduli, ed , si ha in

n N m Z

∀ ∈ ∈

generale

[ ]

[ ]

n n

m ed in particolare, sottintendendo il pedice 9:

= m

9 9 [ ]

[ ] [ ] [ ] [ ]

3 3 3 3

[ ] [ ] [ ] [ ]

[ ] [ ] [ ] [ ] [ ] [ ]

3

3 3 3

1 ; 8 ; 64 1 ; 125 8 ;

= = = = = =

1 2 4 5

= = = = 5

1 2 4

[ ] [ ]

3 3

[ ] [ ]

[ ] [ ] [ ] [ ]

3 3

343 1 ; 512 8 c. v. d.

= = = =

7 8

= =

7 8 3 3

p p

Detta tesi equivale a due congruenze 1

(mod 9 ) e 8

(mod 9 ) quando dividendo

≡ ≡

ogni per 9 si hanno tre resti rispettivamente uguali a 7 per la prima congruenza e

p 1, 4,

2, 5, 8 per la seconda. [ ] [ ] [ ] [ ]

3

13 4 2197 1

13

Ess.: per 13 abbiamo , 2197 , ;

p = = = =

9 9 9 9

[ ] [ ] [ ] [ ]

3

11 2 1331 8

11

per 11 abbiamo , 1331

, .

p = = = =

9 9 9 9

Teorema 2

Il modulo 9 della potenza di 6 di ogni numero primo, ad eccezione del 3, è sempre 1.

Dimostrazione:

Adottando la proprietà delle potenze mod 9, sottintendendo sempre il pedice 9, abbiamo

2 “Alcune regolarità dai numeri primi” dello stesso autore 2