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

[ ]

[ ] [ ] [ ]

6 6 6 6

[ ] [ ] [ ] [ ]

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

6

6 6 6

1 ; 64 1 ; 4096 1 ; 15625 1 ;

= = = = = = =

1 2 4 5

= = = = 5

1 2 4

[ ] [ ]

6 6

[ ] [ ]

[ ] [ ] [ ] [ ]

6 6

117649 1 ; 262144 1 c. v. d.

= = = =

7 8

= =

7 8

6

p

Detta tesi equivale alla congruenza 1

(mod 9 ) .

≡ 6 ( )

p

Naturalmente non solo tutte le potenze di 6 dei primi, con esclusione di 3, danno 1 mod 9

≡

6 6

p p

( e 1 sono nella stessa classe di resto se e solo se 1 mod 9 , per cui l’equivalenza è 9 divide

=

6

p

( 1 )), ma anche tutte le restanti potenze di 6 dei numeri naturali ad esclusione di 3 e di tutti i

−

suoi multipli: cioè a partire da 1, ogni gruppo di tre numeri ha, per i primi due, l come mod 9, per il

terzo no.

Inoltre, prima di proseguire col mod 9, osserviamo che anche dalla potenza quarta di tutti i primi

con i moduli 10 e 12 possiamo avere tutti 1, con eccezioni rispettivamente per le coppie di primi 2,

5 e 2, 3. Infatti abbiamo le due congruenze

4 4

p p ,

1

(mod 10 ) e 1

(mod 12 )

≡ ≡

che sono verificate rispettivamente con le possibili classi dei resti dei moduli 10 e 12 dei numeri

[ ] [ ]

{ } { }

\ 2

,

5 \ 2

,

3

p p

1

,

3

,

7

,

9 e 1

,

5

,

7

,

11

primi .

∈ ∈

10 12

Con ciò, a nostro avviso, nulla viene tolto pero` alla “Generalita` che

delle argomentazioni...”

andremo ad esporre nel relativo paragrafo ed alle singolarita` di quelle esposte e che seguono sui

moduli 7, 9, 5. 1

m − ( ) { }

a 1 mod con : e non divisibile per ,

Dalla congruenza di Fermat m m m numeroprim

o a m

≡ ∈

( )

p 1

−

p p p p

ed 1 mod , per la quale non ci sono preclusioni, in quanto

posti abbiamo

a m

= = ≡

1

2 1

2 1

ad ed abbiamo sostituito due numeri primi; per la proprietà che dice “se due numeri sono

a m

congrui mod i loro rispettivi prodotti per 0 sono congrui mod

m, n mn”,

≠

3 1

− ( ( )

)

p p p p

3 e per 3 3 1 mod 3 3

per abbiamo ed in generale per abbiamo anche

n

= = ⋅ ≡ ⋅ =

2 2

1

2

p p

3

( 1

) 0 (mod 9 ) , dove .

− ≡ 3

≠ 6 ( ) { }

d : 3

Analoga dimostrazione abbiamo per 1 mod 9 con con

d d numeridisp

ari k

∈ ≠

≡ ( )

d 1

−

d d d d

ed 1 mod

abbiamo , per la quale qui vi è la preclusione

posti a m

k=1,2,3,…: = = ≡

1

2 1 2 1

d d

non debba essere divisibile per

che .

2 1

Per la proprietà` che dice “se due numeri sono congrui mod i loro rispettivi prodotti per 0

m, n ≠

3 1

− ( ( )

)

d d

3 e per 3

sono congrui mod mutatis mutandis, per abbiamo 3 1 mod 3 3 ed

n

mn”, = = ⋅ ≡ ⋅

1 2

2

3

( d

d d d

in generale per : 1

) 0 (mod 9 ) , dove 3 .

k

= − ≡ ≠

2

In particolare dall’asserto di Fermat, operando le sostituzioni ed abbiamo, per 7 ,

a=p m=7, p ≠

7 1 6

− ( ) ( )

p p

1 mod 7 e quindi 1 mod 7 , che rispetto alla tesi del teorema 2, cioe`, per 3 ,

p

≡ ≡ ≠

6 4 ( )

p p

1

(mod 9 ) , varia solo per il modulo; per ed abbiamo per 5

, 1 0 mod 5 .

a=p m=5, p

≡ ≠ − = 3

[ ] [ ]

6 6 ( )

1771561 1

11 11

Es.: per abbiamo 1771561 , , ossia 1 mod 7 , perché

p=11 =

= ≡

7 7

( ) ( )

[ ] [ ]

6 6 6

( )

1771561 1

11 11 11

7 divide 1 ed anche , ossia 1 mod 9 , perché 9 divide 1 ,

=

− ≡ −

9 9

infatti da 1771561-1=1771560 verifichiamo 1771560:7=253080 e 1771560:9=196840.

Ora, da quanto ottenuto sopra per il teorema di Fermat, per la proprietà del trasporto del termine 1,

( ) ( )

p p

1 1

− −

p p p p

cioe` 1 mod , 1 0 mod e per il teorema di Wilson, per il quale sussiste la

≡ − ≡

1 1

2 1 2 1

( ) ( )

p p

1 ! 1 0 mod

congruenza reciproca , considerata l’uguaglianza dei secondi membri

− + ≡

1 1 ( )

p 1

−

p p

p 1 ! 1

deduciamo che divide con resto zero tanto 1 che , per cui possiamo

− +

−

1

2

1 1

p p

da due primi, comunque presi e` immediata la possibilità di trovare due

e

affermare: 1 2

p

numeri entrambi multipli di , secondo le funzioni di numeri interi

1

 

p 1

−

p

  (

( ) )

1 1

− p 1 ! 1

− +

2

( ) ( )

  p

p p dei quali numeratori del secondo

, e

h k

= = 1

p p

1 2 1

1 1

p

membro, il numero primo è, a parte 1, il minore divisore comune.

1

Per concludere il paragrafo riportiamo un esempio:

7 -

1

p p 5

per 7 e per 5 da 1 15624

, abbiamo 15624 : 7 2232 e da

h

= = − = = =

1 2

( )

7 - 1 ! 1 721 abbiamo 721 : 7 103 . I due numeri 15624 e 721 sono entrambi multipli di 7 ed

k

+ = = =

hanno chiaramente lo stesso 7, a parte 1, come minimo divisore comune. Ora scambiando i valori,

cioè per 5 e 7 abbiamo i due numeri multipli 2400 e 25, il cui minimo comune divisore e’ 5.

p p =

1= 2

Test di primeità e test parziali di primeità

I primi due test che riportiamo, come noto, sono tratti il primo dal teorema di Wilson, il secondo dal

( ) ( )

1 ! 1 0 mod

piccolo teorema di Fermat relativi rispettivamente alle congruenze e

p p

− + ≡

1

p − ( )

a 1 0 mod e il terzo dagli sviluppi che abbiamo ottenuto dal teorema di Fermat, in

p

− ≡ 6

p

particolare con 1 :

− ( )

1 ! 1

1) per il primo test, il numero è primo se divide senza resto ;

p

p − +

riportiamo di seguito alcune primeità parziali, pur consapevoli che esse lasciano il tempo che

trovano; 1

p −

a a N

∀ ∈

2) per il secon