ARITMETICA DEI NUMERI INTERI

ARITMETICA DEI NUMERI INTERI

1. QUOZIENTE APPROSSIMATO DI DUE NUMERI

Considereremo sia numeri naturali

N=

{

0, 1, 2,3, …

}

sia i numeri interi

Z =

{

… ,−2,−1,0, 1, 2, …

}

.

Presi due numeri naturali a, b con a > b e b > 1, consideriamo la successione dei multipli di b:

(1)

b ∙1, b ∙ 2, b∙ 3, … , b ∙q , …

In essa vi si trova il numero ba

¿

a. Si conclude che in essa esisteranno due elementi consecutivi che comprendono a; sia

bq ≤ a<b

(

q +1

)

=

bq +b

.

Se allora poniamo

r=a−bq

, sarà certamente

r <b

, così potremo scrivere

(2)

a=bq+r , con 0 ≤ r <b

I due numeri q e r si dicono quoziente approssimato e resto di a per b e l’operazione che permette di trovarli, divisione approssimata; a poi si chiama dividendo e b divisore.

Si può dimostrare che le (2) individuano i due numeri q ed r in modo univoco; infatti se si avesse anche

(3)

a=b q

₁

+

r

₁

, con r

₁

<

b

,

risulterebbe

bq+r =b q

₁

+

r

₁ , da cui, sottraendo da ambo i membri dell’uguaglianza

b q

₁ ed

r

, seguirebbe

bq+r −b q

₁

−

r =b q

₁

+

r

₁

−

b q

₁

−

r

cioè

bq−b q

₁

=

r

₁

−

r

, o anche,

b ∙

(

q−q

1

)

=

r

1

−

r

.

Allora

r

₁

−

r

sarebbe multiplo di b, il che è impossibile, perché tanto r che r1 sono minori di b; si dovrà quindi avere r1 – r = 0 e perciò anche q – q1 = 0.

Osservazione1: se

a=b

si ha

q=1

e

r=0

.

Osservazione 2: se

a<b

si ha

q=0

e

r=a

.

Osservazione 3: se

b=1

si ha

q=a

e

r=0

.

Osservazione 4: il caso

b=0

non viene considerato, cioè si assumerà sempre

b ≠ 0

. In generale si dimostra il seguente

Teorema

Presi due numeri interi a, b con

b ≠ 0

, esistono due e due soli interi,

q

ed

r

tali che

a=bq+r , con 0 ≤ r <

|

b

|

Dimostrazione

1^ caso:

a ≥ 0, b>0

Lo abbiamo appena mostrato. 2^ caso:

a<0,b>0

Consideriamo il valore assoluto di a e dividiamolo per b, si ha

|

a

|

=

bq+r , con 0≤ r <b

tenendo conto che

|

a

|

=−

a

, si ottiene

−

a=bq+r ,

ossia

a=b(−q)−r

. Se

r=0

abbiamo concluso, altrimenti togliendo e aggiungendo b dal secondo membro dell’ultima uguaglianza si ha

a=b (−q )−b+b−r

, cioè

a=b (−q−1)+b−r

posto

_q

'

₌₋

_q−1

e

_r

'

₌

_b−r

si ottiene

a=bq '+r '

con

q '

e

r '

unici per l’unicità di q ed r e con

_0<r

'

<

|

b

|

.

3^caso:

a ≥ 0, b<0

Consideriamo il valore assoluto di b e dividiamo a per b, si ha

a=

|

b

|

q +r , con 0 ≤r <

|

b

|

tenendo conto che

|

b

|

=−

b

, si ottiene

a=−bq+r

ossia

a=b(−q)+r

. Posto

q

'

=−

q

e

r

'

=

r

si ottiene

a=bq '+r '

con

q '

e

r '

unici per l’unicità di q ed r e con

_{0 ≤ r}

'

<

|

b

|

.

4^ caso:

a<0,b<0

Consideriamo i valori assoluti di a e b, dividendo

|

a

|

per

|

b

|

si ha

|

a

|

=

|

b

|

q+r , con 0 ≤ r <

|

b

|

tenendo conto che

|

a

|

=−

a

e

|

b

|

=−

b

, si ottiene

−

a=−bq+r

, ossia

a=bq−r

Se

r=0

abbiamo concluso, altrimenti aggiungendo e togliendo b al secondo membro dell’ultima uguaglianza si ha

a=bq+b−b−r

, cioè

a=b

(

q+1

)

−

b−r

, ovvero

a=b

(

q+1

)

+

|

b

|

−

r

posto

_q

'

=

q+1

e

r

'

=

|

b

|

−

r

si ottiene

con

q '

e

r '

unici per l’unicità di q ed r e con

_0<r

'

_<

|

b

|

.

(

termine della dimostrazione)

Esempi di divisioni approssimate

1)

a=18,b=15

,

18=1 ∙15+3(q=1, r=3)

2)

a=−42, b=−35

,

42=1∙ 35+7 →−42=−1

⋅35−7 →

−42=1

⋅(−35 )−35+35−7 →−42=2⋅ (−35)+28(q=2, r=28)

3)

a=54,b=−15

,

54=3 ∙15+9→ 54=−3

⋅(−15)+9 (q=−3, r=9)

4)

a=−20, b=16

,

20=1 ∙ 16+4 →−20=−1

⋅16−4 →

−20=−1

⋅16−16+16−4 →−20=−2⋅16+12(q=−2, r=12)

2. IL M.C.D. DI DUE O PIÙ NUMERI, NUMERI PRIMI Definizioni

1) Se il resto della divisione di a per b è uguale a zero si dice che b divide a e si scrive:

b∨a

. Ovviamente risulta che a è un multiplo di b ossia

a=bq

e viceversa, se a è un multiplo di b

allora b divide a.

2) Dicesi primo un numero divisibile solo per se stesso e per l’unità. I numeri non primi si dicono composti.

4) Chiamasi massimo comun divisore (m.c.d.) di due o più numeri il più grande dei loro divisori comuni.

3) Due numeri si dicono primi tra loro se il loro m.c.d. è l’unità.

5) Chiamasi minimo comune multiplo (m.c.m.) di due o più numeri, il minore dei loro multipli comuni.

Sussistono i seguenti teoremi:

1) Se c divide a e b allora divide anche a+b, a-b,

a

⋅b

; infatti dalla divisibilità di a e b per c

segue che

a=c q

₁

,b=c q

₂ da cui si ha

a+b=c q

₁

+

c q

₂

=

c

₍

q

₁

+

q

₂

₎

=

cq

,

a−b=c q

₁

−

c q

₂

=

c

₍

q

₁

−

q

₂

₎

=

cq '

,

a

⋅b=c q

₁

⋅c q

₂

=

c

₍

q

₁

c q

₂₎

=

cq ' '

, ovvero

a+b

,

a−b

,

a

⋅b

, sono multipli di c e quindi sono divisibili per c.

2) Esiste un semplice procedimento, detto algoritmo euclideo, che ci consente di ottenere il m.c.d. di due numeri qualunque interi positivi a, b. Per fissare le idee supponiamo a > b, allora non è difficile dimostrare che m.c.d.(a, b) = m.c.d.(a-kb, b) con k numero intero qualsiasi. Operando ripetutamente delle trasformazioni come quella indicata si giunge a determinare agevolmente il m.c.d.(a, b).

Esempio: m.c.d.(96, 35) = m.c.d.(96– 2∙35 , 35) = m.c.d. (26, 35) = m.c.d.(26, 35 – 26) = m.c.d. (26, 9) = m.c.d.(26 - 2∙9, 9) = m.c.d.(8, 9) = m.c.d.(8, 9 – 8) = m.c.d.(8, 1) = 1.

3) Un numero n non primo può sempre decomporsi nel prodotto di fattori primi, cioè sussiste la decomposizione

(4)

n= p

₁α1

p

2

α2

… p

r αr

e si dimostra facilmente che tale decomposizione è unica; infatti se sussistesse anche l’altra decomposizione

_n=q

₁β1

q

2 β2

…q

s βs , risulterebbe (5)

p

₁α1

p

2 α2

… p

r αr

=

q

₁β1

q

2 β2

… q

s βs

ma allora, il numero primo p1, dividendo il primo membro della (5) dovrebbe dividere anche il secondo e siccome tutti i fattori q di esso sono numeri primi, dovrebbe essere p1 uguale ad uno di essi.

Sia per esempio p1 = q1 e dimostriamo che deve essere anche

α

1

=

β

1 ; infatti se fosse

α

1

>

β

1 , dalla (5), dividendone ambo i membri per

p

₁β1 , seguirebbe

p

₁α1−β1

p

2 α2

… p

r αr

=

q

₂β2

… q

s βs

Il che è impossibile, perché p1 dividerebbe il primo membro ma non il secondo. Così continuando segue l’asserto. Quando si scrive la (4) si è soliti dire che si è proceduto alla fattorizzazione del numero n in fattori primi.

4) La serie dei numeri primi è illimitata; infatti sia p un numero primo e consideriamo il numero

n=1⋅2 ⋅3 ⋅…⋅ p +1= p !+1> p

Tale numero può essere primo, oppure no; ma se non è primo, non può ammettere divisori primi minori di p, perché se

q< p

fosse uno di questi, dividerebbe n e p! e quindi 1, il che è assurdo; segue che esiste un numero primo maggiore di p.

3. CONGRUENZE E L’INSIEME DEI RESTI MODULO n

Definizione: Due numeri interi a, b si dicono congrui tra loro modulo n, se la loro differenza è multipla di n, cioè se

a−b=k ∙n ,

con

nϵ N , k

∈ Z

;

si usa scrivere

a ≡b (mod n)

e leggere “a congruo b, modulo n” Sussiste il Teorema del resto:

Condizione necessaria e sufficiente affinché due interi a, b siano congrui modulo n, è che, divisi per n, diano lo stesso resto.

Infatti, se

a=nq+r , b=n q

1

+

r

, con

r<n

, sottraendo membro a membro risulta

a−b=n

₍

q−q

₁

₎

⇔ a ≡b(mod n)

Viceversa, se

a ≡b (mod n)

dividendo tanto a che b per n, si ha

a=nq+r , b=n q

'

da cui,

_a−b=n

₍

_q−q

'

₎

+(

r−r

'

)

e quindi necessariamente,

r−r

'

=0,

cioè

r=r '

il che dimostra il teorema.

Valgono le proprietà:

a) Se

a ≡b (mod n)

, allora

a−b ≡0 (mod n)

.

Infatti per definizione

a ≡b (mod n)

⇔ a−b=k ∙ n

ossia

a−b

è un multiplo di n e quindi diviso per n ha come resto zero esattamente come 0 diviso n ha come resto zero, pertanto per il teorema precedente

a−b ≡0 (mod n)

.

b) Se

a ≡b (mod n)

, allora

a+c ≡b +c (mod n)

; e viceversa.

Infatti per il teorema precedente i resti delle divisioni di a e b con n sono uguali, ossia risulta

a=nq+r , b=n q

'

+

r

, dividendo c per n si ha

c=n q

''

+

r ' '

e pertanto

a+c=nq+r +n q

' '

+

r

''

=

n(

q+q

''

)

+

r +r

'' , per cui risulta

a+ c ≡r+ r

''

(

mod n)

, analogamente

b+c=n q

'

+

r +n q

''

+

r

' '

=

n

(q

'

+

q

' '

)

+

r +r ' '

per cui risulta

b+c ≡r +r

''

(

mod n)

, ora essendo

a+c

e

b+c

congrui modulo n allo stesso numero

r +r ' '

, per il teorema precedente se divisi per n hanno lo stesso resto di

r +r ' '

e quindi uguale resto, pertanto per il teorema precedente risultano congrui tra loro modulo n.

c) Se

a ≡b (mod n)

, allora

a ∙ c ≡ b ∙c (mod n)

.

Infatti, come su, posto

_{a=nq+r , b=n q}

'

+

r

,

c=n q

''

+

r ' '

, si ha

a ∙ c=(nq+r )(

n q

' '

+

r

''

)

=

n

(qn q

' '

+

q r

' '

+

r q

' '

)

+

r ∙ r ' '

, dunque

ac ≡ r r

'

(

mod n)

, analogamente

b ∙ c=(nq '+r )

(

n q

' '

+

r

''

)

=

n

(

q ' n q

''

+

q ' r

''

+

r q

' '

)

+

r ∙r ' '

, dunque

bc ≡ r r

'

(

mod n)

, ora essendo

ac

e

bc

congrui modulo n allo stesso numero

_{r r}

' , ragionando come sopra, sono tra loro congrui.

d) Più congruenze rispetto allo stesso modulo si possono sommare (o moltiplicare) membro a membro, ottenendo una nuova congruenza rispetto allo stesso modulo.

Infatti, se

a

i

≡b

i

(

mod n)

, per

i=1, 2,3, … , r

, cioè se

a

_i

=

b

_i

+

h

_i

n

, sommando membro a membro si ottiene,

∑

i=1 r

a

_i

=

∑

i=1 r

b

_i

+

n

∑

i=1 r

h

_i

_∑

i=1 r

a

_i

≡

_∑

i=1 r

b

_i

(

mod m)

Analogamente, moltiplicando membro a membro, si ottiene

b

(

¿¿

i+h

i

n)=

∏

i=1 r

b

i

+

nK

∏

i=1 r

a

_i

=

∏

i=1 r

¿

, con

Kϵ Z

da cui

∏

r

a

_i

≡

_∏

r

b

_i

(

mod n)

e) In particolare, se

a ≡b (mod n)

è anche

_a

r

_{≡ b}

r

₍

_{mod n)}

.

Più in generale se con p(x) indichiamo un polinomio razionale intero, con coefficienti appartenenti all’insieme

Z

degli interi, da

a ≡b (mod n)

si deduce

p(a)≡ p(b)(mod n)

.

Osservazione

La congruenza modulo n fissa una relazione tra i numeri interi (relazione di equivalenza), cioè un legame tra i numeri così che l’insieme

Z

viene suddiviso in sottoinsiemi, ossia in classi, in ciascuna delle quali vi sono solo numeri tra loro congruenti modulo n, ovvero solo numeri che hanno lo stesso resto se divisi per n. Per fissare le idee consideriamo un caso numerico, assumiamo n=7. Tutti i resti possibili della divisione per 7 sono: 0, 1, 2, 3, 4, 5, 6. I sottoinsiemi di

Z

individuati dalla congruenza modulo 7 sono in tutto 7, nella prima classe vi saranno tutti gli interi il cui resto della divisione per 7 è 0, nella seconda vi saranno tutti gli interi che hanno per resto 1 e così via fino all’ultima classe che conterrà tutti gli interi che divisi per 7 hanno resto uguale a 6. Si è soliti indicare le classi con

[0], [1], [2], [3], [4], [5], [6]

dove all’interno delle parentesi quadre vi è indicato un numero che appartiene alla classe. Definizione: Talvolta per questioni di opportunità si considerano come rappresentanti delle classi i numeri che in valore assoluto risultano minori di

{

n

2

}

nel nostro specifico caso minori o uguali a 3, ossia

[0], [1], [2], [3], [-3], [-2], [-1].

Così facendo si dice che si considera il sistema minimo completo di resti.

Nota: Questa terminologia è a mio avviso legata alla confusione che esiste sul significato del termine resto, se togliamo la condizione che il resto debba essere non negativo e minore del valore assoluto del divisore, possiamo scrivere tutta una serie di identità, come

13=2 ∙ 7−1 ;13=1 ∙ 7+6 ;…

dove i “resti” sono: -1, 6, ecc.

4. CRITERI DI DIVISIBILITÀ NEL SISTEMA DECIMALE

Le proprietà delle congruenze trovano un’interessante applicazione nella determinazione dei così detti criteri di divisibilità nel sistema di numerazione decimale.

Sia N un qualunque numero e

a

0

, a

1

, a

2

, … , a

k le sue cifre, rispettivamente dell’ordine 0, 1, 2, .

. . , k, così che si possa scrivere

N=a

k

10

k

+

a

k−1

10

k−1

+

…+a

0 ;

indicando con

α

_r , il minimo “resto” di

₁₀

r _{, rispetto ad un modulo n, cioè ponendo}

10

r

≡ α

r

(

mod n)

, con

α

r il numero intero in valore assoluto più piccolo fra quelli della sua

classe di appartenenza generata dalla relazione di congruenza modulo n, avremo evidentemente

(6)

N ≡ a

k

α

k

+

a

k−1

α

k−1

+

…+a

1

α

1

+

a

0

(

mod n)

α

(

¿¿

0=1)

¿

I “resti”

α

₀

=1, α

₁

, α

₂

, … , α

_k , si chiamano i coefficienti di divisibilità per n nel sistema decimale, rispettivamente di ordine 0, 1, 2, … , k.

Dalla (6) si deduce la proprietà:

Un numero scritto secondo il sistema decimale, diviso per n dà lo stesso resto della somma dei prodotti di ciascuna cifra, per il coefficiente di divisibilità per n, di egual ordine della cifra. Esempi

a) Sia n=2, il primo dei coefficienti di divisibilità è 1 e tutti gli altri sono zero; perciò sarà

N ≡ a0

(

mod 2)

Pertanto si ha che un numero N è divisibile per 2 se lo è la sua ultima cifra ossia se termina per

0 o per una cifra pari.

b) Sia n=3, i coefficienti di divisibilità sono tutti 1 e perciò sarà

N ≡ a

0

+

a

1

+

…+a

k

(

mod 3)

Pertanto si ha che un numero N è divisibile per 3 se lo è la somma delle sue cifre ossia se la somma delle sue cifre è un multiplo di tre.

c) Sia n=5, il primo dei coefficienti di divisibilità è 1 e tutti gli altri sono zero; perciò sarà

N ≡ a

0

(

mod 5)

Pertanto si ha che un numero N è divisibile per 5 se lo è la sua ultima cifra ossia se termina per

0 o per 5.

d) Sia n=11, i coefficienti di divisibilità sono alternativamente 1 e -1, perciò sarà

N ≡ a0

−

a1

+

a2

+

…+(−1)a

k

(

mod 11)

Pertanto si ha che un numero N è divisibile per 11 se lo è il numero dato dalla somma delle cifre d’ordine pari meno la somma delle cifre d’ordine dispari.

Si sono così ricavati i noti criteri di divisibilità per 2, 3, 5, 11.

5. TEOREMI DI FERMAT ED EULERO

Teorema di Fermat: Se p è un numero primo ed a un naturale primo con esso, sussiste la congruenza

_a

p −1

_{≡1(mod p)}

_.

Infatti se consideriamo i (p – 1) numeri

a , a ∙ 2,a ∙ 3, …, a∙ (p−1)

,

che risultano tutti primi con p, e li dividiamo per p, otteniamo, se indichiamo con

a ∙ i

uno qualunque di essi,

a ∙ i=p ∙ q

i

+

r

i , con

r

i

<

p

,

i=1, 2,… , (p−1)

da cui la congruenza

(7)

a ∙ i≡r

i

(

mod p)

I resti

r

_i risultano tra loro tutti diversi, perché se fosse

r

_i

=

r

_m risulterebbe

a ∙ i=p ∙ q

_i

+

r

_i ,

a ∙ m= p∙ q

_m

+

r

_i

e quindi

a (i−m)= p(q

_i

−

q

_m

)

, da cui si dedurrebbe che p dividerebbe il prodotto

a (i−m)

ed essendo primo con a, dovrebbe dividere

i−m< p

, il che è assurdo.

Se ne conclude che, salvo l’ordine, i resti

r

_i non sono che i numeri 1, 2, …, (p – 1) e quindi che

_∏

i=1 p−1

i=

_∏

i=1 p −1

r

_i ; se allora moltiplichiamo le (7) membro a membro, segue

(

∏

i=1 p−1

i

)

a

p−1

=

(

∏

i=1 p−1

r

i

)

(mod p)

⇒a

p −1

≡1(mod p)

, il che dimostra il teorema.

Teorema di Eulero: Se a è primo con n, si ha la congruenza

a

φ(n )

_{≡1 (mod n)}

_{, con}

_φ(n)

l’indicatore di Gauss, ovvero il numero dei numeri minori di n e primi con esso. La dimostrazione è del tutto analoga alla precedente.

6. EQUAZIONI DIOFANTEE

In matematica, un'equazione diofantea (chiamata anche equazione diofantina) è un'equazione

in una o più incognite con coefficienti interi di cui si ricercano le soluzioni intere. L'aggettivo diofanteo si riferisce al matematico greco del III secolo Diofanto di Alessandria, che studiò equazioni di questo tipo e fu uno dei primi matematici a introdurre il simbolismo nell'algebra. Vi sono diversi modi per ottenere una soluzione intera della equazione

(8)

ax +by=c

con a, b, c interi. Un modo può essere quello riportato nell’esempio seguente. Sia per esempio l’equazione

5 x−12 y =48 ;

avremo

x=

48

5

+

12

5

y

, da cui, attribuendo alla y i valori 0, 1, 2, 3, 4, segue

x

₀

=

48

5

=9+

3

5

,

x

1

=

60

5

=12

,

x

2

=

72

5

=14 +

2

5

,

x

3

=

84

5

=16+

4

5

,

x

4

=

96

5

=19+

1

5

Una soluzione intera dell’equazione proposta sarà quindi data dalla coppia

(

x=12, y=1)

. Un altro metodo per la risoluzione della (8) ci è offerto dalla teoria delle congruenze. Supposto per fissare le idee, che sia b > 0, la ricerca delle soluzioni intere della (8) equivale infatti alla risoluzione della congruenza

(9)

ax ≡ c (mod b)

e viceversa.

Infatti se

(

x

0

, y

0

)

è una soluzione intera della (8), segue

a x

0

+

b y

0

=

c

, cioè

a x

0

−

c

multiplo di b e quindi

a x

0≡ c (mod b) .

Viceversa, se

x

₀ è una soluzione della (9), si ha

a x

₀

−

c=kb

con k intero opportuno e quindi

a x

₀

−

kb=c

, cioè la coppia,

(

x

0

,−k

)

o anche

(

x

0

,

a x

₀

−

c

b

)

è una soluzione intera della (8).

Esercizi

1) Risolviamo con il metodo delle congruenze l’equazione dell’esempio precedente

5 x−12 y =48

.

Ricerchiamo le soluzioni della congruenza

5 x ≡ 48(mod 12)

5 x−48=k ∙12

,

5 x=k ∙12+48

,

x=

k ∙12+48

5

,

x=

k ∙12+4 ∙12

5

,

x=

(

k +4)∙12

5

Le soluzioni intere di questa equazione sono date per k=1, 6, 11, … -9, -14, -19, … in corrispondenza delle quali otteniamo le soluzioni intere (

x=

(

k +4)∙12

5

, y =k

¿

dell’equazione data:

(

x

1

=12, y

1

=1

)

,

(

x

2

=24, y

2

=6

)

,

(

x

3

=36, y

3

=11

)

,

… ,

(

x '

1

=−12, y '

1

=−9

)

,

(

x '

2

=−24, y '

2

=−14

)

,

(

x '

3

=−36, y '

3

=−19

)

,

...

2) Determinare le soluzioni intere dell’equazione

_{2 x}

2

_{−3 y}

2

₌

₃₇

.

Se

(

x

₀

, y

₀

)

è una soluzione dell’equazione data, lo sarà ovviamente anche della congruenza

2 x

2

−3 y

2

≡37(mod quel che ci pare)

Non vale però il viceversa. Se scopriamo che la congruenza, per un fissato modulo n, non ha soluzioni, sicuramente non ne avrà neanche l’equazione assegnata.

2 x

2

−3 y

2

≡37(mod 3)

Tenendo conto che

_{3 y}

2

_{≡ 0(mod 3)}

_{, sommando membro a membro le due congruenze si} ottiene

_{2 x}

2

_{−3 y}

2

_{+3 y}

2

_{≡ 37+0 (mod 3)}

, ovvero

_{2 x}

2

_{≡37(mod 3)}

, considerando poi che

37 ≡1(mod 3)

, per il teorema del resto risulterà senz’altro che

2 x

2

≡1(mod 3)

applicando ancora più volte in modo opportuno le proprietà delle congruenze si ha:

2 x

2

_{≡1 (mod 3) →−2 x}

2

_{≡−1 (mod 3) →3 x}

2

_{−2 x}

2

_{≡−1 (mod 3) →}

x

2

_{≡−1 (mod 3) → x}

2

+

1≡ 0 (mod 3)

quest’ultima congruenza non ha soluzioni, pertanto neanche l’equazione assegnata ammette soluzioni.

La congruenza

(10)

_x

2

+

1 ≡0 (mod 3 )

non ha soluzioni, infatti se a fosse una soluzione della (10) allora, o a contiene 3 come fattore primo o non lo contiene. Se a contiene 3 come fattore primo allora anche

a

2 _{lo contiene e} per la (10) 3 dovrebbe dividere 1, il che è assurdo. Se a non contiene 3 come fattore primo e quindi a e 3 sono primi tra loro, per il teorema di Eulero deve avvenire che

a

φ(3 )

≡1(mod 3)

ma

φ (3)=2

, e pertanto si ha

_a

2

_{≡1 (mod 3) ,}

_{la quale sommata membro a membro alla} congruenza

1≡ 1

(

mod 3

)

da

a

2

+1 ≡2(mod 3)

dunque dovrebbe avvenire per la (10) che

_a

2

+

1 ≡0 (mod 3 )

e

a

2

+1 ≡2(mod 3)

il che è assurdo dal momento che

0

_{≢2(mod 3)}

.