Esercizi Metodi algebrici - R.V.Vincelli

1 Si dimostri che tutti e soli i sottogruppi di pZ,�q sono ciclici.

pZ,�q e un gruppo ciclico con generatore 1, infatti x1y � t1n : n P Zu �tn : n P Zu. Possiamo allora applicare il teorema fondamentale dei gruppi cicli-ci per il quale ogni sottogruppo d’un ciclico e anch’esso ciclico.

Dimostrazione. Sia G ciclico di generatore a P G, ossia G � xay, H ¤ G; seH � t1u allora H � 1 � 1 (banalmente ciclico). Consideriamo quindi H � t1u;per la ciclicita di G, H � tat : t P T � Zu (infatti H � G, G ciclico); poniamom � mintt P T u. Vogliamo mostrare che H e ciclico con generatore am ossiavale H � xamy; procediamo illustrando la doppia inclusione. xamy � H: sex P xamy allora x � pamqk � am � � � � � am k volte e d’altra parte am P H,H gruppo (e percio chiuso rispetto alla somma). H � xamy: sia b P H; perquanto osservato prima, b � at per un certo t P T . Poiche T � Z si puodividere t ed ottenere t � mq � r con 0 ¤ r   m; di conseguenza si puoscrivere at � apmq � rq � amq � ar da cui ar � at � amq; giacche at P H e�amq � pamq�q P H e ar P H (ancora perche gruppo). m era stato scelto comeminimo, da cui segue che r � 0; per questo si ha b � at � amq � pamqq P xamye si conclude H � xamy

2 Dopo aver ricordato la definizione di ideale di un anello A, si consideri l’anellopZ,�, �q.

• Si provi che tutti e soli gli ideali di Z sono ideali principali (un ideale I di unanello A si dice principale se esiste a P I tale che I � paq � tah : h P Au);

• Si determinino gli ideali massimali I di pZ,�, �q e si riconosca che trovarei quozienti Z{I con I massimale equivale a trovare gli anelli Zn che sonocampi.

Ideale: I � A tc:

• 0A P I

• a, b P I ñ a� b P I

• a P I, b P Añ ab P I

pZ,�, �q e un dominio ad ideali principali, dimostrazione:

• l’anello commutativo pZ,�, �q e un dominio integrale: infatti lo zero e l’unosono differenti e vale la legge di cancellazione del prodotto

• se dimentichiamo il � allora un ideale e un sottogruppo di pA,�q:

– 0A P I (def)

– a, b P I ñ a� b P I (def)

– a P I ñ a�1 P I: a�1 � �a � �1a e per hp a P I, b � �1 P A ñab � a � �1 � �1 � a � �a

1

• quindi dato un qualsiasi ideale I abbiamo con esso anche un sottogruppodi pA,�q: nel nostro caso per ogni I abbiamo un sottogruppo di pZ,�q

• nell’esercizio precedente si e mostrato che tutti e soli i sottogruppi dipZ,�q sono ciclici ossia di forma tan : n P Zu, la quale e anche definizionedi ideale principale paq

Ideale massimale: I � A, EJ : I � J � A (allora I   A in pIdealspAq,�q).Ideale primo: I � A, ab P I ñ a P I _ b P INumero primo: n P Z � t0, 1u e primo se ha esattamente due divisori, 1 ed nstesso.Lemma di Bezout: se a, b P Z � t0u, pa, bq � d allora Dx, y P Z tc ax � by � d.La dimostrazione e costruttiva nell’algoritmo di Euclide esteso:

Algoritmo 1 L’algoritmo di Euclide esteso equivale all’algoritmo di Euclideeseguito all’indietro

1: procedure AlgoritmoDiEuclideEsteso(a, b)2: xÐ 03: y Ð 14: lastxÐ 15: lasty Ð 06: while b � 0 do7: q Ð floorpa{bq8: a, bÐ b, a%b9: x, lastxÐ lastx� qx, x

10: y, lasty Ð lasty � qy, y11: end while12: return lastx, lasty13: end procedure

In Mathematica si ha la funzione ExtendedGCD[a, b].

Equazione diofantina lineare intera: equazione di forma ax�by � c con a, b, c P Zdi cui si cerca soluzione in Z. Essa ha soluzione sse d � pa, bq � c.

Dimostrazione. Sia px0, y0q soluzione; allora ax0 � by0 � c e poiche d � a, b edαx0 � dβy0 � cñ dpαx0 � βy0q � cñ dk � cñ d � c. Se d � c allora c � dr;se d � pa, bq per il l. di Bezout Du, v P Z : au � bv � d; moltiplicando per rottengo aur � bvr � dr ñ aur � bvr � cñ pur, vrq e soluzione.

Lemma di Euclide: se p primo e p � ab allora p � a oppure p � b.

Dimostrazione. p � abô ab � 0 pmod pq; per assurdo sia p � a, b. Allora a � kpmod pq b � e pmod pq con k, r � 0, da cui ab � kr pmod pq, kr � 0 poichepZ{pq campo, percio dominio, e nei domini non esistono divisori dello zero

Perche gli ideali primi si chiamano cosı?

Dimostrazione. In Z gli ideali primi sono tutti e soli i principali ppq per p zero oprimo; poiche pbq � p�bq (l’elemento che in pbq si genera con un intero positivoin p�bq con uno negativo e viceversa) consideriamo solo ppq. p0q � t0u, ed in

2

un dominio ab � 0 ñ a � 0 _ b � 0; Z e un dominio abbiamo detto, ed allorat0u e primo poiche ab � 0 ñ a � 0 � ab_ b � 0 � ab P Iq. pprimoq: anzituttoe proprio; se non lo fosse sarebbe 1 P ppq ñ Da P A : 1 � ap ñ a � p�1

ma Z non e un campo . Poi, se ab P ppq allora ab � cp con c P A da cuip � ab; applicando il l. di Euclide p � a _ p � b ñ a � pk _ b � pk1 conk, k1 P Añ a P ppq _ b P ppq.

Individuiamo ora gli ideali massimali di pZ,�, �q come esattamente gli idealiprimi ppq nonnulli dell’anello.

Dimostrazione. Si consideri l’ideale massimale ppq; se vale ppq � pqq allora de-v’essere pqq � Z ñ q � 1 oppure pqq � ppq ñ q � p per la massimalita di ppq.Se a P pbq allora a � bx x P Z da cui b � a; dovendo qui essere p P pqq segue che1 � p oppure p � p che e definizione di p primo.

Facendo un passo indietro, sappiamo che quozientando un anello commuta-tivo su un qualsiasi suo ideale si puo ottenere un altro anello commutativo: cioha senso poiche, per parlare di anello commutativo, e richiesto un gruppo com-mutativo su �, un ideale preso solo rispetto a � e un sottogruppo del gruppoin questione ed ogni sottogruppo di un commutativo e sottogruppo normale; leoperazioni � e � sono definite come di consueto. Il fatto che questo nuovo anellosia o meno un campo, essendo chiaro che 0A{I � 1A{I , passa per l’esistenza diun inverso per ogni x � 0A{I .Visualizziamo l’anello quoziente: Z{ppq � ta� ppq : n P Zu � ta� np : a, n P Zuossia s’individua la classe di resto modulo p di rappresentante a. Ad un livellopiu basso e possibile arrivare in modo analogo a ppZ{nq,�q quozientando Z sulsottogruppo ciclico xny.Per discutere l’invertibilita degli elementi nonnulli possiamo allora equivalente-mente analizzare ppZ{pq � tr0spu, �q e vedere se ogni elemento ha inverso.

Dimostrazione. rasp P pZ{pq � tr0spu e invertibile sse esiste rxsp : rasprxsp � 1ossia sse ax � 1 pmod pq. La congruenza e vera sse n � pax� 1q ossia sse esisteun q P Z tc ax � 1 � nq ossia sse l’equazione diofantina lineare ax � nq � 1ha soluzione, il che e possibile sse pa, nq � 1. Ora, se p e primo e coprimo aqualsiasi 0   a   p

3 Valutare il simbolo di Legendre p 74119283 q, indicando il tempo dell’algoritmo.

Ricordiamo anzitutto la definizione; per a P Z, p � 2 primo (d’ora in poi chia-meremo il primo numeratore, il secondo denominatore):

�ap

�

$'&'%

1 se a e un residuo quadratico modulo p e a � 0 pmod pq

�1 se a non e un residuo quadratico modulo p e a � 0 pmod pq

0 se a � 0 pmod pq.Posto pa, pq � 1, a e un residuo quadratico modulo p se la congruenza x2 � apmod pq ha soluzioni.Una generalizzazione che permette il denominatore dispari e non necessaria-mente primo e il simbolo di Jacobi ; per a P Z, n � pα1

1 pα22 � � � pαk

k : p an q ��ap1

α1�ap2

α2

� � ��apk

αk

dove p api q e il simbolo di Legendre.

3

Un algoritmo naive per il calcolo del simbolo di Legendre potrebbe essere ilseguente:

• calcolare pa, nq; se si ottiene p il risultato e 0

• altrimenti cercare una soluzione alla congruenza provando ogni resto pos-sibile

Notiamo che questo approccio ingenuo risulta comunque fattibile; infatti l’MCDe calcolabile in modo veloce e la ricerca di una soluzione sarebbe lineare in p(una classe di resto modulo p ha esattamente p elementi).Possiamo pero sfruttare alcune leggi e proprieta associate ai simboli, ed il calcolorisulta piu efficace. Gli strumenti da adoperare sono i seguenti:

1. legge di reciprocita quadratica:�mn

���nm

�p�1q

m�12

n�12 �

# �nm

�se n � 1 pmod 4q or m � 1 pmod 4q

��nm

�se n � m � 3 pmod 4q

2. primo supplemento alla legge:��1n

�� p�1q

n�12 �

#1 se n � 1 pmod 4q

�1 se n � 3 pmod 4q

3. secondo supplemento alla legge:�2n

�� p�1q

n2�18 �

#1 se n � 1, 7 pmod 8q

�1 se n � 3, 5 pmod 8q

4. riduzione del numeratore: Se a � b pmod nq allora p an q ��bn

�5. scomposizione del numeratore:

�abn

�� p an q

�bn

�6. scomposizione del denominatore (duale della precedente)

Anzitutto, il simbolo di Legendre e di fatto un caso particolare del simbolo diJacobi, quindi la strategia si applica piu in generale al calcolo del secondo:

• se si conosce una fattorizzazione del numeratore o del denominatore, scom-porre il simbolo nel corrispondente prodotto di simboli, in base ai fattori;osserviamo che se non si conosce, non e opportuno calcolarla poiche nonesiste algoritmo di fattorizzazione veloce

• se il numeratore e minore del denominatore, applicare la regola (1)

• ridurre il numeratore scegliendo b   a

• se b pari allora usare la (5) altrimenti ritornare al passo (1)

Ripetendo questa procedura si arriva ad avere il prodotto di simboli rappresen-tanti i casi basi, coperti dalle regole di supplemento.Calcoliamo quindi p 74119283 q:

p 74119283 q1� �p 92837411 q

4� �p 18727411 q5� �p 2

7411 qp9367411 q

5� �p 27411 q

2p 4687411 q

5� �p 27411 q

3p 2347411 q

5�

�p 27411 q

4p 1177411 q

1� �p 27411 q

4p 7411117 q4� �p 2

7411 q4p 40

117 q5� �p 2

7411 q5p 20

117 q5� �p 2

7411 q6p 10

117 q5�

�p 27411 q

7p 5117 q

1� �p 27411 q

7p 1175 q 3� �p 27411 q

7p 25 q3� �rp�1q

74112�18 s7p�1q

52�18 �

�p�16865365�7 � �13q � �p�1 � �1q � �1Proviamo quindi a scrivere un’implementazione algoritmica; assumiamo che il

4

compito di questo programma sia calcolare direttamente il simbolo senza preoc-cuparsi di eventuali fattorizzazioni conosciute (si puo pensare che una proceduradi livello superiore se ne occupi):

Algoritmo 2 Questo algoritmo calcola il simbolo di Jacobi p an q con a P Z, n P Zdispari. I primi due if corrispondono ai casi base, i secondi due gestiscono l’ap-plicazione della reciprocita mentre il terzo rappresenta la riduzione del numera-tore. extractClassElement e una procedura che assumiamo di avere, per estrarreun elemento di una certa classe di resto.1: procedure Jacobi(a, n)2: if a � �1 then

3: return p�1qn�12

4: end if5: if a � 2 then

6: return p�1qn2�1

8

7: end if8: if a   n then9: if a � 1 pmod 4q _ n � 1 pmod 4q then

10: return Jacobi(n, a)11: else12: return -Jacobi(n, a)13: end if14: end if15: if a%2 � 0 then16: return Jacobi(2, n)�Jacobi(a{2, n)17: else18: a1 ÐextractClassElement(a, n)19: return Jacobi(a1, n)20: end if21: end procedure

Discutiamo informalmente la complessita di questo algoritmo, astraendo daoperazioni di basso livello come somme e prodotti: i due casi base in quest’otticasono eseguiti in tempo costante. Ora, vediamo come un unico passo d’iterazio-ne la sequenza di azioni di scambio delle variabili, con la legge di reciprocita,seguita dalla riduzione fattore 2 e dalla riduzione su modulo. Siccome con essail numeratore e dimezzato ogni volta, il tempo globale della procedura non puoche essere Oplg nq.All’interno di un singolo passo pero, siamo chiamati principalmente a due ope-razioni: valutare a � 1 pmod 4q, estrarre un elemento dalla classe rasn. Essendoche alla base di entrambe vi sono moltiplicazione e divisione (cioe moltiplicazio-ne lunga e divisione intera) e che queste hanno costo quadratico nel numero dibit dell’elemento maggiore, che nel nostro caso e al piu n, otteniamo Opplg nq2q.Da cio segue che la complessita in tempo risultante e Opplg nq3q.

4 Si dia la definizione di numero pseudoprimo e di numero pseudoprimo diEulero rispetto a una base b. Si provi in entrambi i casi, che il numero dibasi b tali che n sia pseudoprimo (pseudoprimo di Eulero) rispetto a b e al piu

5

φpnq (con φpnq si indica la funzione di Eulero; ricordare il teorema di Lagrange).

Pseudoprimo (di Fermat): n dispari lo e per b : 1   b   n tc pb, nq � 1(base) se vale bn�1 � 1 pmod nq.Pseudoprimo di Eulero: n dispari lo e per b : 1   b   n se tc pb, nq � 1 (base)

se vale bn�12 � p bn q pmod nq.

Osserviamo che in entrambe le definizioni la base b e richiesta essere coprimaal candidato primo n, percio cerchiamo le nostre basi nel gruppo moltiplicativodegli interi modulo n, pZ{nq� � trasn : pa, nq � 1u. L’ordine di questo gruppoe φpnq giacche contiene un numero di elementi pari ai numeri minori di n chesono coprimi ad n stesso, cioe la definizione della funzione di Eulero.Inoltre, considerando la struttura dell’insieme delle basi B come sottogruppodi pZ{nq� e grazie al teorema di Lagrange possiamo dimostrare il seguente: sian non primo; se n non e pseudoprimo per almeno una base c, allora non lo erispetto ad almeno la meta delle possibili altre basi b.

Dimostrazione. Posizioniamoci in pZ{nq�; le basi per cui n e pseudoprimo sonotutte e sole quelle dell’insieme B � tb P pZ{nq� : bn�1 � 1 pmod nq; mostriamoche vale B ¤ pZ{nq�

1. 1pZ{nq� P B: 1r � 1@r P Z

2. x, y P B: xy � z ñ pxyqn�1 � zn�1 ñ xn�1yn�1 � zn�1 x,yPBñ 1 � 1 �

zn�1 ñ zn�1 � 1

3. x P B ñ x1 P B: x1 � x�1 ñ px�1qn�1 � x1n�1 ñ x�1pn�1q � x1n�1 ñ

pxn�1q�1 � x1n�1 xPBñ 1�1 � x1n�1 ñ x1n�1 � 1

Se b1, b2 sono basi, allora anche b1b2 lo e, infatti: bn�11 � 1 pmod nq ^ bn�1

2 �pmod nq ñ bn�1

1 bn�12 � 1 � 1 ñ b1b

n�12 � 1 pmod nq; percio vale b1, b2 P B ñ

b1b2 P B. Esiste una c tc n non e pseudoprimo rispetto ad essa, percio c R B;consideriamo cbi: essa non puo essere una base, poiche se lo fosse lo sarebbeanche cbib

1i (b1i e base perche bi lo e e B e gruppo) ossia c P B . Da cio

possiamo dire che B non contiene piu elementi del suo complemento, e quindila sua cardinalita dev’essere inferiore a s � 1

2φpnq (per n ¥ 3 φpnq e pari eds dev’essere inferiore o uguale) . Detto altrimenti, per il teorema di Lagrange

deve valere |B| � |pZ{nq�||Z{nq�:B| e siccome B e un sottogruppo proprio (esiste appunto

c R B) il suo indice puo essere al massimo 2, da cui segue che |B|   φpnq{2.

Per gli pseudoprimi di Eulero la dimostrazione e analoga: senza necessitadi ricorrere ai gruppi si puo considerare che, proprio come sopra, il prodotto diuna base per una non-base da una non-base.

5 Si dimostri che il gruppo alterno delle permutazioni pari su n oggetti, An, enormale nel gruppo simmetrico Sn.

Una permutazione e pari se puo essere scritta come prodotto non banale diun numero pari di scambi.Un sottogruppo e normale se l’immagine della funzione coniugio γgphq � ghg1

e contenuta in esso.

6

Mostriamo che An ha la stessa cardinalita del suo complemento Sn�An � Bn;sia β P Bn e si consideri la mappa fβ : Bn Ñ An tc fβpxq � βx; essa e unabigezione, infatti:

• e iniettiva: fβpxq � fβpyq ñ βx � βy ñ β1βx � β1βy ñ x � y

• e suriettiva: @y P AnDx P Bn : fβpyq�1 � x, l’elemento e di forma β1yche e in Bn certamente poiche composizione di permutazione dispari epermutazione pari

Essendo i due insiemi in corrispondenza biunivoca, hanno la stessa cardinalita,e potendo essere una permutazione solamente o pari o dispari, essa e n!

2 . Ap-plicando il t. di Lagrange l’indice di An in Sn e 2. Ora possiamo applicare ilseguente teorema: se un sottogruppo ha indice 2 allora e normale.

Dimostrazione. Obiettivo e mostrare pH ¤ G, g P G, h P Hq ñ ghg1 P H (def).Se ho iGpHq � 2 allora ho due soli laterali distinti: 1GH (l’uno esiste perforza) eaH con a R H (sono distinti: H � aH ô a1 P H ed H gruppo). I laterali destri(sinistri) formano una partizione, quindi G e formato dall’unione disgiunta di Hed aH ed una qualsiasi g0 P G deve stare in uno dei due coset. Se g0 P H alloraγg0phq P H poiche prodotto di tre elementi di H che e un gruppo: quindi H e“seminormale” (contiene il coniugio dei suoi elementi scegliendo g0 in H stesso).L’altro caso si ha se g0 P aH allora g0 � ax, x P H e vale γg0phq � γaxphq �axhpaxq�1 � axhx�1a�1 con.� apxhx�1qa�1 � aγxphqa�1 � aha con h P H. Siaγg0phq R H per g0 R H, ossia H non sia normale se non prendiamo g0 P H;

allora dev’essere, per quanto appena calcolato, γg0phq � aha1 P aH e quindi

aha1 � ay, y P H. Cancellando a ho ha1 � y e quindi a � y1h ma avevamo dettoa R H e y1h e il prodotto di due elementi in H e quindi e anch’esso in H

6 Si determini un campo finito di ordine 54 e si dica se esiste un campo diordine 35.

Se I e ideale massimale di A allora A{I e un campo.

Dimostrazione. Se I massimale allora I proprio ed ho quindi almeno due ele-menti distinti in A{I, 0A{I , a� I, se ne avessi uno solo potrei costruire un solocoset ed avrei I � A (con Lagrange). L’identita di � e I, mentre quella di � e1� I e vale I � 1� I ô �1� 0 P I ñ �1 P I ñ �1 � �1 � 1 P I ñ I � Añ Inon massimale, quindi possiamo concludere che 0A{I � 1A{I .Ora devo verificare che ogni nonnullo sia invertibile su �. Prendo a� I; aA� Ie a sua volta ideale di A (si puo verificare direttamente) tc I � aA� I e per lamassimalita di I e sicuramente aA � I � A. Per quest’ultimo fatto c’e alloraun modo di scrivere 1A partendo da aA � I ossia 1A � ab � i ñ ab � 1A � icon b P A, i P I. Ricordando com’e definito il prodotto sull’anello A{I ha sensoscrivere pa � Iqpb � Iq � ab � I e sostituendo con l’uguaglianza per ab si ot-tiene ab � I � 1A{I � i � I; per i � 0 ottengo 1 � I � 1A{I da cui segue chepa� Iq1 � pb� Iq.

Un elemento a P A si dice irriducibile se non puo essere scritto come prodottodi due elementi non unita ossia tali che non dividano 1A cioe che non sianinvertibili.Se fpxq P F rxs irriducibile allora pfpxqq massimale.

7

Dimostrazione. Sia J : pfpxqq � J ; vale allora J � pgpxqq con gpxq P pfpxqq(devo poter scrivere tutti i polinomi di pfpxqq almeno). fpxq P pfpxqq per

p(x)=1ñ fpxq P pgpxqq ñ fpxq � gpxqqpxqf irrñ gpxq P F _ qpxq P F (costanti).

Se gpxq P F allora gpxq unita e pgpxqq � F rxs poiche ho 1F rxs � gpxqg1pxq Ppgpxqq ñ J � F rxs. Se qpxq P F allora fpxq � agpxq, a P F ñ gpxq � a1fpxq ñgpxq P pfpxqq ñ J � pfpxqq. Quindi nel primo caso ho J � F rxs, nel secondoJ � pfpxqq cioe pfpxqq e massimale.

Per pfpxqq P F rxs � 0F rxs ogni laterale tgpxq � pfpxqq : gpxq P F rxsu diF rxs{pfpxqq contiene un solo polinomio hpxq a grado minore del grado di fpxqpari ad n.

Dimostrazione. Per dimostrare questo teorema abbisognamo di leggere F rxscome dominio euclideo ossia come dominio fornito di un’apposita funzione,il grado degp�q, che permette una generalizzazione del consueto algoritmo diEuclide sugli interi. Se degpgq   n allora hpxq � gpxq � gpxq � fpxq0F rxs.Altrimenti posso dividere g per f ed ottengo gpxq � qpxqfpxq � hpxq condegphq   n; quindi ho gpxq P hpxq � pfpxqq ma anche hpxq P gpxq � pfpxqqpoiche hpxq � gpxq � qpxqfpxq. Come con Z interpretiamo i laterali comeclassi di resto modulo fpxq ovvero come contenenti tutti e soli i polinomi chedivisi per fpxq hanno medesimo resto; presi due rappresentanti allora sono nel-la stessa classe se sono congrui modulo fpxq. Ora, gpxq � qpxqfpxq � hpxq,hpxq � gpxq � qpxqfpxq quindi f � g � h, e siamo dunque liberi si considerarehpxq � pfpxqq al posto di gpxq � pfpxqq. Siano h1pxq, h2pxq P hpxq � pfpxqq;rappresentando la medesima classe sono ancora congrui modulo fpxq e quindih1pxq � pfpxqq � h2pxq � pfpxqq ñ h1pxq � h2pxq P pfpxqq ñ f � h1� h2 ñ Dq :qf � h1�h2. Abbiamo pero che degph1q�degph2q ¤ maxtdegph1q, degph2qu   ne d’altra parte degpqfq � degpqq�degpfq ¡ n per qpxq � 0 e quindi l’unica pos-sibilita e qpxq � 0 ñ h1pxq � h2pxq � 0 ñ degph1q � degph2q; di conseguenza ilrappresentante a grado minore di n e solo uno.

@n, p primo Dfpxq P pZ{pqrxs : degpfq � n, f irriducibile. Si possono trovarevari modi per ottenere siffatti fpxq. E’ pero possibile, come nei test di compo-stezza (primalita) visti un approccio casuale (stile metodi Monte Carlo) basatosull’analogo del teorema dei numeri primi riguardo ai polinomi irriducibili su diun campo finito: in un campo finito F di dimensione q il numero di polinomimonici (ossia con coefficiente direttore 1F ) irriducibili di grado n e nell’ordine diqn

n che ponendo x � qn diventa xlogb x

. Poiche ci sono esattamente qn polinomi

monici di grado n, scegliendone uno a caso la probabilita che sia irriducibile ecirca 1{n. Assumendo per l’estrazione casuale una complessita di tempo linearenel grado ed essendoci test d’irreducibilita deterministici di tempo polinomiale(es. algoritmo di Rabin), la strada e piu che percorribile.Infine: @p primo , n ¥ 1D!F : F campo, |F | � pn.

Dimostrazione. Prendiamo fpxq P pZ{pq irriducibile e consideriamo pZ{pqrxs{pfpxqq:con i risultati di sopra, sappiamo che e un campo ed ogni sua classe ha un solopolinomio a grado inferiore di degpfq � n. Contare i rappresentanti equivale acontare gli elementi del campo, ed i rappresentanti sono tutti e soli i polinomidi grado inferiore ad n a coefficienti in pZ{pq, che sono in numero pn.

8

Adoperando Mathematica possiamo agire come intuito in precedenza: co-struire un polinomio avendone scelto i coefficienti a caso e testarne l’irriduci-bilita; se necessario si puo procedere a costruire simbolicamente i polinomi delcampo. Ci limitiamo per semplicita a fornire qualche indicazione, senza costruireil programma intero; i passi sono principalmente due:

• con RandomChoice[Table[i, i, 0, p], n] otteniamo n coefficien-ti per il nostro polinomio di grado n� 1 a coefficienti in pZ{pq: dovrebbeessere n ¡ 0 poiche le costanti non sono polinomi irriducibili ed il direttoree sempre 1 cercando noi tra i polinomi monici

• con IrreduciblePolynomialQ[poly,Modulus->p] verifichiamo l’ir-riducibilita del polinomio simbolico costruito in pZ{pqrxs

Nel caso particolare di 54, dopo vari tentativi i coefficienti t4, 0, 0, 4u dannoil polinomio di grado 4 x4 � 4x3 � 4 che risulta irriducibile in pZ{5qrxs. Lagenerazione di tutte le possibili 54 � 625 5-uple di coefficienti per i polinomidel campo e istantanea attraverso il comando Tuples[0, 1, 2, 3, 4, 5].35 � 5 � 7 non e esprimibile in forma pn con p primo, n ¡ 0 e quindi non esisteun campo finito di ordine 35.

7 Si determinino le radici quadrate di 1 modulo 105 � p3 � 5 � 7q.

Dobbiamo risolvere x2 � 1 pmod 105q; per prima cosa applichiamo il teo-rema cinese del resto e cerchiamo soluzioni per x2 � 1 pmod 3q, x2 � 1pmod 5q, x2 � 1 pmod 7q. In tutte e tre le congruenze il modulo e primo,quindi possiamo applicare il seguente: p primo, a2 � 1 pmod pq ñ a � �1pmod pq.

Dimostrazione. a2 � 1 pmod pq ñ p � pa2 � 1q ñ p � apa � 1a q

l. di Euc.ñ p �

a _ p � pa � 1a q; p � a ô a � pk, k P Z ñ p2k2 � 1 pmod pq ñ hp2 � 1

pmod pq ñ p � p1�hp2q, no; p � pa� 1a q ô a� 1

a � pk, k P Z, l’unica possibilitae k � 0, a � �1.

Soluzione a tutte e tre le congruenze e allora x � �1. Abbiamo allora 23 � 8triple di soluzioni da mappare in altrettante soluzioni modulo 105 attraverso iso-morfismo. Dobbiamo allora risolvere 8 sistemi di congruenze di formax � �1 pmod 3qx � �1 pmod 5qx � �1 pmod 7qPer le quali si ha una soluzione applicando ancora il t. cinese del resto, que-sta volta nella forma piu applicativa, che illustriamo brevemente. Supponia-mo di avere un sistema cui congruenze sono di forma x � ai pmod nqi peri � 1, . . . , k, pnr, nsq � 1@r, s. Definiamo il prodotto N � n1 � � �nk; per ognii, pni, N{niq � 1. Applicando l’identita di Bezout con l’algoritmo di Euclideesteso possiamo trovare degli interi ri, si tali che rini � siN{ni � 1. Poniamoei � siN{ni; l’espressione diventa rini � ei � 1. Questa garantisce che il restodella divisione di ei per ni e 1 e la definizione di ei stesso, la quale contieneN , che sia divisibile per nj � ni. Da cio deduciamo ei � 1 pmod nqi, ej � 0pmod nqj per ni � nj . Sfruttando la proprieta base rispetto al prodotto della

relazione � si puo scrivere x �°ki�1 aiei ed x e soluzione simultanea al sistema

9

di congruenze.Per esempio nel nostro caso prendiamo a1 � a3 � 1, a2 � �1 ed ovviamenten1 � 3, n2 � 5, n3 � 7. N � 105; N{n1 � 35, N{n2 � 21, N{n3 � 15. Le cop-pie dell’identita sono rispettivamente p12,�1q, p�4, 1q, p�2, 1q. e1 � 1 �35 � 35,e2 � 1 � 21 � 21, e3 � 1 � 15 � 15. Soluzione e allora 1 � 35� 1 � 21� 1 � 15 � 71.Per trovarle tutte utilizziamo il seguente programma Mathematica (osservandoche non necessariamente la procedura illustrata e quella utilizzata - possibile sene adoperino ottimizzazioni):For[i = 1, i <= 8, i++, Print[ChineseRemainder[Tuples[1, -1,3][[i]], 3, 5, 7]]]Le soluzioni sono t1, 76, 64, 34, 71, 41, 29, 104u.

8 Si dimostri che un numero n e primo se e solo se ci sono solo due radiciquadrate p1,�1q modulo n.

Dimostrazione. Meta dimostrazione consiste nel l. di Euclide. D’altro canto perrisolvere una congruenza modulo n � pp1qa1 � � � ppkq

ak applicando il t. cinese del

resto si possono risolvere k congruenze modulo ppkqk ed il numero di r-uple damappare indietro a singoli risultati del problema originale tramite l’isomorfismoe maggiore di 2 (soluzione �1) sse n non e primo.

10