Aritmetica modulare/Esercizi

Wikibooks, manuali e libri di testo liberi.

Sommario
Categoria · Copertina · Bibliografia · modifica il template

Copertina Aritmetica modulare/Copertina
  1. La relazione di congruenza Aritmetica modulare/La relazione di congruenza
  2. Prime proprietà e applicazioni Aritmetica modulare/Prime proprietà e applicazioni
  3. Congruenze lineari Aritmetica modulare/Congruenze lineari
  4. Polinomi in aritmetica modulare Aritmetica modulare/Polinomi in aritmetica modulare
  5. Radici primitive Aritmetica modulare/Radici primitive
  6. Congruenze quadratiche Aritmetica modulare/Congruenze quadratiche
  7. Alcune applicazioni Aritmetica modulare/Alcune applicazioni
  8. Bibliografia Aritmetica modulare/Bibliografia
  9. Esercizi Aritmetica modulare/Esercizi

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

Indice

[modifica] 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)

Il tuo punteggio è 0 / 0


[modifica] 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 peg 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.

1. 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 =

Il tuo punteggio è 0 / 0


[modifica] 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 φ(x) è dispari.

Il tuo punteggio è 0 / 0


[modifica] 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 z2, 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 (X0,Y0,z0) questa soluzione. Allora

(X0z − 1,Y0z − 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)

[modifica] Capitolo 5

1. Trovare l'ordine moltiplicativo di:

6 mod 11 =
14 mod 25 =
13 mod 43 =
2 mod 15 =
3 mod 63 =

Il tuo punteggio è 0 / 0


  • 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 = φ(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.

Il tuo punteggio è 0 / 0


  • 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)

[modifica] 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


Il tuo punteggio è 0 / 0


[modifica] 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 = x2 + y2. Ma allora questo vale anche riducendo modulo p; di conseguenza a è somma di due residui quadratici.

Ricavato da "http://it.wikibooks.org/wiki/Aritmetica_modulare/Esercizi"
Strumenti personali