Aritmetica modulare/Esercizi
Di seguito sono presentati degli esercizi, con le rispettive soluzioni, divisi per capitoli.
Capitolo 1[modifica]
Capitolo 2[modifica]
- Dimostrare che se Errore del parser (SVG (MathML può essere abilitato tramite plug-in del browser): risposta non valida ("Math extension cannot connect to Restbase.") dal server "http://localhost:6011/it.wikibooks.org/v1/v1/":): {\displaystyle 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 Errore del parser (SVG (MathML può essere abilitato tramite plug-in del browser): risposta non valida ("Math extension cannot connect to Restbase.") dal server "http://localhost:6011/it.wikibooks.org/v1/v1/":): {\displaystyle b^x\equiv 1\mod d} per ogni x naturale; scrivendo n in base b come
- Errore del parser (SVG (MathML può essere abilitato tramite plug-in del browser): risposta non valida ("Math extension cannot connect to Restbase.") dal server "http://localhost:6011/it.wikibooks.org/v1/v1/":): {\displaystyle 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
- Errore del parser (SVG (MathML può essere abilitato tramite plug-in del browser): risposta non valida ("Math extension cannot connect to Restbase.") dal server "http://localhost:6011/it.wikibooks.org/v1/v1/":): {\displaystyle 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 3[modifica]
Capitolo 4[modifica]
- Dimostrare, usando il solo teorema di Chevalley, che la congruenza
- Errore del parser (SVG (MathML può essere abilitato tramite plug-in del browser): risposta non valida ("Math extension cannot connect to Restbase.") dal server "http://localhost:6011/it.wikibooks.org/v1/v1/":): {\displaystyle x^2+y^2\equiv -1\mod p}
ha soluzione per ogni primo p.
Moltiplichiamo tutto per Errore del parser (SVG (MathML può essere abilitato tramite plug-in del browser): risposta non valida ("Math extension cannot connect to Restbase.") dal server "http://localhost:6011/it.wikibooks.org/v1/v1/":): {\displaystyle z^2} , ottenendo la congruenza Errore del parser (SVG (MathML può essere abilitato tramite plug-in del browser): risposta non valida ("Math extension cannot connect to Restbase.") dal server "http://localhost:6011/it.wikibooks.org/v1/v1/":): {\displaystyle 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 Errore del parser (SVG (MathML può essere abilitato tramite plug-in del browser): risposta non valida ("Math extension cannot connect to Restbase.") dal server "http://localhost:6011/it.wikibooks.org/v1/v1/":): {\displaystyle (X_0,Y_0,z_0)} questa soluzione. Allora
- Errore del parser (SVG (MathML può essere abilitato tramite plug-in del browser): risposta non valida ("Math extension cannot connect to Restbase.") dal server "http://localhost:6011/it.wikibooks.org/v1/v1/":): {\displaystyle (X_0z^{-1},Y_0z^{-1})}
è una soluzione della congruenza originaria.
- Trovare tutte le soluzioni della congruenza
- Errore del parser (SVG (MathML può essere abilitato tramite plug-in del browser): risposta non valida ("Math extension cannot connect to Restbase.") dal server "http://localhost:6011/it.wikibooks.org/v1/v1/":): {\displaystyle 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[modifica]
- Sapendo che Errore del parser (SVG (MathML può essere abilitato tramite plug-in del browser): risposta non valida ("Math extension cannot connect to Restbase.") dal server "http://localhost:6011/it.wikibooks.org/v1/v1/":): {\displaystyle 2^9\equiv 1\mod 73} e Errore del parser (SVG (MathML può essere abilitato tramite plug-in del browser): risposta non valida ("Math extension cannot connect to Restbase.") dal server "http://localhost:6011/it.wikibooks.org/v1/v1/":): {\displaystyle 10^8\equiv 1\mod 73} , trovare una radice primitiva modulo 73.
L'ordine di Errore del parser (SVG (MathML può essere abilitato tramite plug-in del browser): risposta non valida ("Math extension cannot connect to Restbase.") dal server "http://localhost:6011/it.wikibooks.org/v1/v1/":): {\displaystyle 2\cdot 10} è Errore del parser (SVG (MathML può essere abilitato tramite plug-in del browser): risposta non valida ("Math extension cannot connect to Restbase.") dal server "http://localhost:6011/it.wikibooks.org/v1/v1/":): {\displaystyle 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[modifica]
- 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 Errore del parser (SVG (MathML può essere abilitato tramite plug-in del browser): risposta non valida ("Math extension cannot connect to Restbase.") dal server "http://localhost:6011/it.wikibooks.org/v1/v1/":): {\displaystyle (-a)^k\equiv 1\mod p} allora Errore del parser (SVG (MathML può essere abilitato tramite plug-in del browser): risposta non valida ("Math extension cannot connect to Restbase.") dal server "http://localhost:6011/it.wikibooks.org/v1/v1/":): {\displaystyle a^k\equiv\pm 1\mod p} . k può essere uguale solo a p-1 o Errore del parser (SVG (MathML può essere abilitato tramite plug-in del browser): risposta non valida ("Math extension cannot connect to Restbase.") dal server "http://localhost:6011/it.wikibooks.org/v1/v1/":): {\displaystyle \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 Errore del parser (SVG (MathML può essere abilitato tramite plug-in del browser): risposta non valida ("Math extension cannot connect to Restbase.") dal server "http://localhost:6011/it.wikibooks.org/v1/v1/":): {\displaystyle a^k\equiv 1\mod p} , impossibile perché a ha ordine p-1.
Capitolo 7[modifica]
- Dimostrare che in Errore del parser (SVG (MathML può essere abilitato tramite plug-in del browser): risposta non valida ("Math extension cannot connect to Restbase.") dal server "http://localhost:6011/it.wikibooks.org/v1/v1/":): {\displaystyle \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 Errore del parser (SVG (MathML può essere abilitato tramite plug-in del browser): risposta non valida ("Math extension cannot connect to Restbase.") dal server "http://localhost:6011/it.wikibooks.org/v1/v1/":): {\displaystyle 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 Errore del parser (SVG (MathML può essere abilitato tramite plug-in del browser): risposta non valida ("Math extension cannot connect to Restbase.") dal server "http://localhost:6011/it.wikibooks.org/v1/v1/":): {\displaystyle P=x^2+y^2} . Ma allora questo vale anche riducendo modulo p; di conseguenza a è somma di due residui quadratici.