# Aritmetica modulare/Esercizi

Aritmetica modulare
Copertina Bibliografia Tutti i moduli · Sviluppo
    CopertinaAritmetica modulare/Copertina
* La relazione di congruenzaAritmetica modulare/La relazione di congruenza
* Prime proprietà e applicazioniAritmetica modulare/Prime proprietà e applicazioni
* Congruenze lineariAritmetica modulare/Congruenze lineari
* Polinomi in aritmetica modulareAritmetica modulare/Polinomi in aritmetica modulare
* Radici primitiveAritmetica modulare/Radici primitive
* Congruenze quadraticheAritmetica modulare/Congruenze quadratiche
* Alcune applicazioniAritmetica modulare/Alcune applicazioni
* BibliografiaAritmetica modulare/Bibliografia
* EserciziAritmetica modulare/Esercizi
Modifica il sommario
Di seguito sono presentati degli esercizi, con le rispettive soluzioni, divisi per capitoli.

## 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.
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.

## 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.
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$
(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

* Sapendo che $2^{9}\equiv 1\mod 73$ e $10^{8}\equiv 1\mod 73$, trovare una radice primitiva modulo 73.
L'ordine di $2\cdot 10$ è $mcm(9,2)=72=\phi (73)$, e quindi 20 è radice primitiva.
* Costruire una tavola di indici modulo 11 a partire dalla radice primitiva 2.
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.
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.

## 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.
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.