Aritmetica modulare/Esercizi

Di seguito sono presentati degli esercizi, con le rispettive soluzioni, divisi per capitoli.

Capitolo 1

1 Trovare:

20 mod 3 =

31 mod 4 =

1895 mod 7 =

43245 mod 13 =

2 Dire quali dei seguenti elementi sono invertibili:

	4 (modulo 8)
	10 (modulo 14)
	12 (modulo 31)
	15 (modulo 35)
	8 (modulo 9)
	438 (modulo 15)

Capitolo 2

• Dimostrare che se $b\equiv 1\mod d$ allora n è divisibile per d se e solo se lo è la somma delle sue cifre, quando n è scritto in base b.

Soluzione proposta

Chiaramente $b^{x}\equiv 1\mod d$ per ogni x naturale; scrivendo n in base b come

$n=a_{k}\cdot b^{k}+a_{k-1}\cdot b^{k-1}+\cdots +a_{1}\cdot b^{1}+a_{0}$

e riducendo modulo d si ha

$n\equiv a_{k}+a_{k-1}+\cdots +a_{1}+a_{0}$

e quindi n è diviso da d se e solo se lo è la somma delle sue cifre in base b.

Calcolare usando il piccolo teorema di Fermat o il teorema di Eulero:

$2^{75}\mod 5$ =

$5^{89}\mod 7$ =

$4^{90}\mod 11$ =

$16^{96}\mod 13$ =

$56681^{123432}\mod 13$ =

$14^{54}\mod 10$ =

$26^{32}\mod 12$ =

$7^{19}\mod 15$ =

$9^{9}\mod 6$ =

Capitolo 3

1 Risolvere:

$2x\equiv 3\mod 5$ =

$3x\equiv 7\mod 8$ =

$6x\equiv 8\mod 9$ =

$21x\equiv 7\mod 28$ =

$8x\equiv 7\mod 9$ =

$91x\equiv 991\mod 3$ =

2 Risolvere:

${\begin{cases}x\equiv 7\mod 9\\x\equiv 3\mod 5\end{cases}}$ =

${\begin{cases}x\equiv 2\mod 3\\x\equiv 3\mod 4\\x\equiv 4\mod 5\\x\equiv 5\mod 6\end{cases}}$ =

3 Risolvere:

$x^{4}+3x^{2}+7x+3\mod 21$ =

4 Determinare tutti gli x tali che $\phi (x)$ è dispari.

Capitolo 4

• Dimostrare, usando il solo teorema di Chevalley, che la congruenza

$x^{2}+y^{2}\equiv -1\mod p$

ha soluzione per ogni primo p.

Soluzione proposta

Moltiplichiamo tutto per $z^{2}$, ottenendo la congruenza $X^{2}+Y^{2}+z^{2}\equiv 0\mod p$. Questa ha una soluzione in cui non tutte le incognite sono pari a zero, e quindi per simmetria una in cui z è diversa da 0. Sia $(X_{0},Y_{0},z_{0})$ questa soluzione. Allora

$(X_{0}z^{-1},Y_{0}z^{-1})$

è una soluzione della congruenza originaria.

• Trovare tutte le soluzioni della congruenza

$x^{2}+2y^{2}-z^{2}\equiv 0\mod 3$

Soluzione

(0,0,0), (1,0,1), (1,0,2), (1,1,0), (1,2,0), (2,0,1), (2,0,2), (2,1,0), (2,2,0)

Capitolo 5

Trovare l'ordine moltiplicativo di:

6 mod 11 =

14 mod 25 =

13 mod 43 =

2 mod 15 =

3 mod 63 =

• Sapendo che $2^{9}\equiv 1\mod 73$ e $10^{8}\equiv 1\mod 73$, trovare una radice primitiva modulo 73.

Soluzione proposta

L'ordine di $2\cdot 10$ è $mcm(9,2)=72=\phi (73)$, e quindi 20 è radice primitiva.

1 Trovare le radici primitive modulo 23.

2 Sapendo che 2 è una radice primitiva modulo 13, trovare una radice primitiva modulo 169.

• Costruire una tavola di indici modulo 11 a partire dalla radice primitiva 2.

Soluzione

1 2 3 4 5 6 7 8 9 10 (elemento)
0 1 8 2 4 9 7 3 6 5 (indici)

Capitolo 6

• Dimostrare che se a è una radice primitiva modulo un primo p congruo a 1 modulo 4 allora anche p-a è una radice primitiva modulo p.

Soluzione proposta

Le potenze di -a sono le stesse di a, eccettuato il segno: quindi se $(-a)^{k}\equiv 1\mod p$ allora $a^{k}\equiv \pm 1\mod p$. k può essere uguale solo a p-1 o ${\frac {p-1}{2}}$: in quest'ultimo caso, tuttavia, essendo p è congruo a 1 modulo 4, (p-1)/2 è pari, e quindi si avrebbe anche $a^{k}\equiv 1\mod p$, impossibile perché a ha ordine p-1.

1 Elencare i residui quadratici modulo 13.

2 Calcolare: |type="{}" $\left({\frac {-26}{73}}\right)$ = { -1

Capitolo 7

• Dimostrare che in $\mathbb {Z} _{p}$ ogni elemento è somma di al più due residui quadratici usando il teorema sull'esistenza di infiniti primi in ogni progressione aritmetica.

Soluzione proposta

Sia p un primo dispari, e $a\in \mathbb {Z} _{p}$. Uno tra a, a+p, a+2p, a+3pè congruo a 1 modulo 4; sia b. La progressione aritmetica b+4pk è congrua ad a modulo p; in essa esistono infiniti numeri primi e quindi, in articolare, ne esiste uno: questo, essendo congruo a 1 modulo 4, è somma di due quadrati; sia $P=x^{2}+y^{2}$. Ma allora questo vale anche riducendo modulo p; di conseguenza a è somma di due residui quadratici.