ALGEBRA E LOGICA (Pareschi e Schoof) 1^{o} esonero Roma 3 aprile 2002, 14:00–15:45.

COGNOME . . . . . . . . . . . . . . . . . . . . . . . . . . .  NOME . . . . . . . . . . . . . . . . . .  ANNO . . . . . . . . .

Inserire le risposte negli spazi predisposti, accompagnandole con spiegazioni chiare ed essenziali. NON SI ACCETTANO RISPOSTE SCRITTE SU ALTRI FOGLI. Ogni esercizio vale 6 punti.

1. Determinare la tavola di verità della forma proposizionale (¬p) → (q ∧ r).

\begin{matrix}p & q & r & ¬p & q ∧ r & (¬p) → (q ∧ r) \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 & 0 & 1 \\ 1 & 1 & 0 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 & 1 & 1 \end{matrix}

2. Dimostrare per induzione che ∑_{k=1}^{n}(2k − 1)^{2} è uguale a \frac{n(2n−1)(2n+1)}{3}.

Abbiamo che

∑_{k=1}^{n+1}(2k − 1)^{2} = ∑_{k=1}^{n}(2k − 1)^{2} + (2n + 1)^{2}.

Per induzione questo è uguale a

\begin{aligned}\frac{n(2n − 1)(2n + 1)}{3} + (2n + 1)^{2} & = \frac{2n + 1}{3}(n(2n − 1) + 3(2n + 1)), \\ & = \frac{(2n + 1)(2n + 3)(n + 1)}{3}. \end{aligned}

Concludiamo che la formula vale per n+1 quando vale per n. Siccome vale anche per n = 1, la dimostrazione è completa.

3. Sia n = 55. Sia D = 17 e sia x = 9. Determinare un esponente E tale che (x^{D})^{E} ≡ x (mod n).

Sia p = 5 e q = 11. Siccome p e q sono primi, abbiamo che x^{(p−1)(q−1)} ≡ 1 (mod n). Quindi, se E soddisfa DE ≡ 1 (mod (p − 1)(q − 1)), allora ((x^{D})^{E} = x^{DE} ≡ 1 (mod n). Sositituendo D = 17 e (p − 1)(q − 1) = 4 · 10 = 40 basta quindi risolvere l’equazione 17E ≡ 1 (mod 40). Abbiamo che

1 · 40 + 0 · 17 = 40,
0 · 40 + 1 · 17 = 17,
1 · 40 + (−2) · 17 = 6, (1^{a} eq. − 2 · 2^{a} eq.)
(−2) · 40 + 5 · 17 = 5, (2^{a} eq. − 2 · 3^{a} eq.)
3 · 40 + (−7) · 17 = 1. (3^{a} eq. − 4^{a} eq.)

e quindi E = −7 ≡ 23 (mod 40) è una soluzione.

4. Trovare tutte le soluzioni x ∈ Z del sistema di congruenze \{ \begin{matrix}x ≡ 6 (mod 9); \\ x ≡ 4 (mod 8). \end{matrix}

Siano n, m, r, s ∈ Z. Se a, b ∈ Z soddisfano an + bm = 1, allora le

soluzioni x ∈ Z del sistema di congruenze \{ \begin{matrix}x ≡ r (mod n), \\ x ≡ s (mod m), \end{matrix} sono x ≡

san + brm (mod nm).

Sia n = 9, m = 8, r = 6 e s = 4. Siccome 1 · 9 + (−1) · 8 = 1 possiamo prendere a = 1 e b = −1. Le soluzioni sono quindi x = 4·1·9+(−1)·6·8 = −12 ≡ 60 (mod 72).

Alternativamente: dalla prima equazione segue che x = 6 + 9h per un h ∈ Z. Sostituendo nella seconda, abbiamo che 6 + 9h ≡ 4 (mod 8).Da cui 9h ≡ −2 (mod 8), cioè h ≡ −2 (mod 8). In altre parole h = −2 + 8s per un s ∈ Z e quindi x = 6 + 9(−2 + 8s) = −12 + 72s per un s ∈ Z.

5. Costruire una biezione da Z all’insieme dei numeri interi congrui a 3 (mod 7).

Sia S = {m ∈ Z : m ≡ 3 (mod 7)}. Allora la mappa f : Z ⟶ S data da f(n) = 3 + 7n è una biezione. In effetti, se f(n) = f(n′), allora 3 + 7n = 3+7n′ e quindi n = n′ e si vede che f è iniettiva. D’altraparte f è suriettiva, perché ogni m ∈ S ha la forma 3 + 7n e quindi m = f(n) per un n ∈ Z.