Congruenze 2 – Calcolo dell’inverso

(1)

Rappresentazioni in base b

Argomenti: cxvwxc Difficolt`a: wcvwcxvwcxvwcxvw

Prerequisiti: wxcvwxc

Completate la seguente tabella (in ogni riga deve comparire lo stesso intero scritto nelle basi indicate nelle intestazioni delle colonne).

2 3 4 5 10 16

100

Completare la seguente tabella (lo stesso numero razionale deve essere scritto nella prima colonna come frazione con numeratore e denominatore in base 10, e nelle colonne successive come allineamento decimale (eventualmente periodico) nelle basi indicate).

Rappresentazione in base

Frazione 2 3 4 5 10

1/2 1/3 1/4 1/5 1/6 1/7

0, 01

(2)

Primi e fattorizzazione

Argomenti: cxvwxc Difficolt`a: wcvwcxvwcxvwcxvw

Prerequisiti: wxcvwxc

Determinare per quali valori interi positivi di a le seguenti espressioni assumono valori interi.

Espressione Valori di a Espressione Valori di a a + 4

a + 1

2a + 25 a + 2 3a − 17

a + 3

a³+ 2 a + 1 a + 37

2a + 1

3a − 34 2a + 1 a²+ 30a

3a + 2

a + 79 2a²+ 1

Determinare se le seguenti proposizioni sono vere per ogni numero primo p, e per ogni coppia di interi a e b.

Proposizione Vera Falsa Proposizione Vera Falsa

Proposizione Vera Falsa

Se a e a^b sono interi, allora b `e intero 2 2 Se a e b sono interi, allora a^b `e intero 2 2

(3)

Congruenze 1 – Operazioni algebriche

Argomenti: Operazioni con le conguenze Difficolt`a: ⋆ ⋆ Prerequisiti: Definizione di congruenza, comportamento rispetto a somma e prodotto

Calcolare il rappresentante privilegiato degli interi indicati nella prima colonna, modulo gli interi indicati nelle colonne successive.

Modulo

Intero 3 4 5 8 9 10 11 25

202 2002 20002

5721 2002 · 5721

5721² 2002²· 5721² 2002²+ 5721²

Modulo

Intero 7 11 13 13 17 19 22 101

23 100 123 2.300 123.000

−14.600 1.460.000 1.460.123

(4)

Congruenze 2 – Calcolo dell’inverso

Argomenti: Calcolo dell’inverso modulo un intero Difficolt`a: ⋆ ⋆ Prerequisiti: Teorema di Bezout, inverso moltiplicativo

Calcolare l’inverso degli interi indicati nella prima colonna modulo gli interi indicati nelle colonne successive (indicare “N.E.” se l’inverso non esiste).

Modulo

Intero 3 5 7 8 9 10 13 29

2 3 4 5 6 7 8 9 10 11

Trovare i valori di x che risolvono le congruenze indicate modulo gli interi dati (indicare il rappresentante privilegiato della o delle soluzioni, o “N.E.” se la congruenza non `e mai verificata).

Modulo

Congruenza 3 5 7 8 9 10 12

2x ≡ x − 2 3x + 2 ≡ x − 1

−2x + 1 ≡ x − 1 5x + 6 ≡ 7x + 9

x − 3 ≡ 3x − 1

(5)

Equazioni diofantee di primo grado

Argomenti: Calcolo del rappresentante privilegiato Difficolt`a: ⋆ ⋆ Prerequisiti: Teorema di Bezout

Per le seguenti equazioni diofantee, indicare nella colonna “Soluzione particolare” la soluzione per cui x assume il minimo valore positivo possibile (mettendo “N.E.” se l’equazione non ammette soluzioni), ed indicare nella colonna “Numero soluzioni” il numero di soluzioni (x, y) con 0 ≤ x ≤ 1000.

Equazione Soluzione particolare Numero soluzioni 2x + 3y = 1

2x + 3y = 5 2x + 3y = 10

3x − 7y = 5 9x + 12y = 3 9x + 12y = 4 9x + 12y = 99 11x + 23y = 4 1000x + 2002y = 1 1000x + 2002y = 2 1000x + 2002y = 127 1000x + 2002y = 126

Per le seguenti equazioni diofantee, trovare la soluzione (o le soluzioni) per cui x²+ y²+ z² assume il minimo valore possibile, ed indicare il numero di soluzioni (x, y, z) con 0 ≤ x ≤ 1000 e 0 ≤ y ≤ 1000.

Equazione Soluzione particolare Numero soluzioni x + 2y + 3z = 1

2x + 3y + 4z = 5 3x + 4y + 5z = 3 6x + 10y + 15z = 1

(6)

Teorema cinese

Argomenti: Calcolo del rappresentante privilegiato Difficolt`a: ⋆ ⋆ Prerequisiti: Criteri di congruenza modulo i principali interi

Per ciascuno dei seguenti sistemi di congruenze, si calcoli la pi`u piccola soluzione x ≥ 0 (mettendo “N.E.” se il sistema non ammette soluzioni) ed il numero di soluzioni tali che 0 ≤ x ≤ 10000.

Sistema Soluzione Numero soluzioni

x ≡ 0 (mod 3), x ≡ 1 (mod 2) x ≡ 2 (mod 5), x ≡ 2 (mod 7) 3x ≡ 2 (mod 5), 2x ≡ 3 (mod 7) 7x ≡ −1 (mod 11), x ≡ 3 (mod 4)

x ≡ 1 (mod 5), x ≡ 2 (mod 7), x ≡ 3 (mod 11) x ≡ 3 (mod 7), x ≡ 7 (mod 8), x ≡ 8 (mod 3) x ≡ 5 (mod 6), x ≡ 8 (mod 14), x ≡ 9 (mod 21) x ≡ 1 (mod 6), x ≡ 9 (mod 14), x ≡ 16 (mod 21)

x ≡ 1 (mod 8), x ≡ 3 (mod 12), x ≡ 6 (mod 15) x ≡ 1 (mod 8), x ≡ 5 (mod 12), x ≡ 5 (mod 15)

Calcolare l’inverso degli interi indicati nella prima colonna modulo gli interi indicati nelle colonne successive (indicare “N.E.” se l’inverso non esiste).

Modulo

Intero 5 8 9 40 45 72 360

5 7 11 127 215 307

(7)

Struttura moltiplicativa 1 – Congruenze

Completare la seguente tabella calcolando la φ di Eulero.

m φ(m) m φ(m) m φ(m) m φ(m)

3 4 5 6

7 8 9 10

24 100 256 500

1000 2000 2001 2002

Modulo

Intero 3 5 7 9 13 10 21 360

13¹³ 2¹⁸ 3⁴⁴ 6²⁰⁰² 73²²⁰ 1000¹⁰⁰⁰ 2002²⁰⁰²

4⁴⁴ 5⁵⁵ 7⁷⁷ 6⁷⁸ 2002²⁰⁰²²⁰⁰²

(8)

Struttura moltiplicativa 2 – Ordine moltiplicativo

Completare la seguente tabella calcolando gli ordini moltiplicativi (indicando “N.E.” se la richiesta non ha senso).

a ord3(a) ord5(a) ord7(a) ord11(a) ord13(a) ord16(a) ord100(a) ord360(a) 2

3 4 5 7 11 12 2002

Determinare quali sono gli elementi di ordine dato modulo gli interi dati (indicare “N.E.”

se non ne esistono).

Ordine

Modulo 2 3 4 5 6 10

5 7 9 11 25 29 360 2002

(9)

Struttura moltiplicativa 3 – Generatori

Trovare tutti i generatori modulo gli interi m indicati.

m Generatori

3 5 7 9 11 13 17 19 23 25 27

Determinare il numero di generatori modulo gli interi dati (indicare 0 se la struttura moltiplicativa modulo l’intero dato non ammette generatori)

Intero Num. gen. Intero Num. gen. Intero Num. gen. Intero Num. gen.

2 3 4 5

6 7 8 9

10 11 12 13

14 15 16 17

18 19 20 23

25 100 101 2003

(10)

Struttura moltiplicativa 4 – Residui k-esimi

Trovare i residui delle potenze k-esime modulo gli interi indicati.

Modulo

Intero 3 5 7 8

2 3 4 5 6

Determinare quanti sono i residui delle potenze k-esime modulo gli interi indicati.

Modulo

Potenza k 3 5 7 9 100 360 2002

2 3 4 5 6 8 9 10 11 20 100 1000 2001