Algebra
Sistemi congruenziali - Teorema cinese del resto
Prerequisiti
- Congruenze
- Saper fare le addizioni e le sottrazioni
- I moduli devono essere primi tra loro
Testo
Risolvere il seguente sistema di congruenze lineari:
x ≡ 3 mod 5
x ≡ 4 mod 7
x ≡ 2 mod 6
Passaggi
-
📢Controllare se i moduli sono primi tra loro.
MCD(5,7) = 1 MCD(6,7) = 1 MCD(5,6) = 1Questo sistema si può risolvere col teorema cinese del resto. ✅
-
:regional_indicator_n: Calcolare N, dato dalla moltiplicazione dei vari moduli
N = 5 * 7 * 6 = 210
- 💁 Calcolare e assegnare nomi a tutto.
-
calcolare le a
- a1, a2, a3 ⇒ 3, 4 e 2, ossia la parte dopo il simbolo di ≡
-
calcolare le b
- b1 ⇒ 7 * 6 = 42 : 6 e 7 sono i numeri (tranne il primo) dopo “mod” moltiplicati tra loro nella seconda e terza equazione
- b2 ⇒ 6 * 5 = 30 : 6 e 5 sono i numeri (tranne il secondo) dopo “mod” moltiplicati tra loro nella prima e terza equazione
- b3 ⇒ 7 * 5 = 35 : 7 e 5 sono i numeri (tranne il terzo) dopo “mod” moltiplicati tra loro nella prima e seconda equazione
-
calcolare le c
- scrivi un altro sistema di equazioni congruenziali, al quale devi mettere b al passo prima nella parte sinistra, e i moduli originali nella parte destra del “modulo”. L’1 non si cambia, rimane lì.
42x ≡ 1 mod 5 30x ≡ 1 mod 7 35x ≡ 1 mod 6- risolvi questo sistema andando a calcolare c
42x ≡ 1 mod 5 --> 2x ≡ 1 mod 5 --> c1 = 3 30x ≡ 1 mod 7 --> 2x ≡ 1 mod 7 --> c2 = 4 35x ≡ 1 mod 6 --> 5x ≡ 1 mod 6 --> c3 = 5- NOTA: la prima equazione è
2x ≡ 1 mod 5perché il resto della divisione di 42 per 5 è 2. Quindi creo la nuova equazione prendendo quel resto e ponendolo ≡ al modulo originale.- faccio la stessa cosa per le altre equazioni
- 🛒 OPZIONALE: Costruire una tabella con a, b e c. Ricordare chi era N.
-
N = 210 (passo 1)
a b c 1 3 42 3 2 4 30 4 3 2 35 5
Se sei veloce con i calcoli puoi anche non farla, tuttavia, è meglio farla per riordinare i dati trovati finora.
- ❎ Moltiplicare in sequenza le varie celle trovate e sommare i risultati tra loro. Porre il tutto “mod N”
-
Se non stai usando la tabella devi fare
a1*b1*c1+... mod Na b c molt 1 3 42 3 378 + 2 4 30 4 480 + 3 2 35 5 350 + 1208 - Quindi:
1208 mod 210
-
➖ Normalizziamo il risultato: si sottrae a 1208 il numero 210 fino ad arrivare ad un punto dove non si può più sottrarre.
1208 - 210 = 998 998 - 210 = 788 ... 368 - 210 = 158 -
✅ Ecco la soluzione: 158
x = 158 -
(OPZIONALE) Per fare la prova basta prendere le equazioni originali, sostituire e vedere se le equazioni vengono. Nello specifico:
158 ≡ 3 mod 5 158 - 5 = 153 153 - 5 = 148 ... 8 - 5 = 3Siccome viene 3, l’equazione è corretta, perché è uguale al numero dopo ≡
Sistemi congruenziali - Metodo sbatti (funziona sempre)
Il problema del metodo universale: è lungo, laborioso, pieno di calcoli grandi, ma funziona.
Prerequisiti
- Congruenze
- Saper fare le addizioni e le sottrazioni
Testo
Risolvere il seguente sistema di congruenze lineari:
x ≡ 5 mod 18
x ≡ 17 mod 21
x ≡ 23 mod 24
Passaggi
- C’è un teorema che afferma che se trovo una soluzione alle prime, e poi trovo una soluzione tra la soluzione di quelle due e la terza, allora ho trovato una soluzione che va bene per tutte e tre.
-
Si scrive:
x = 5 + 18k1Dove 5+18k1 è dato dalla prima equazione fregandosene del modulo.
- Si sostituisce alla seconda equazione, questa x.
-
Così
5 + 18k1 ≡ 17 mod 21
-
Si porta il 5 dall’altra parte, e si semplifica tutto qualora sia possibile in questo caso, per 3.
- In questo caso si può:
5 + 18k1 = 17 - 5 mod 21 18k1 = 12 mod 21 6k = 4 mod 7 -
Si trova l’inverso di 6 in mod. 7 con Bezout.
- 7 = 6 * 1 + 1
- 1 = 7 + 6(-1)
-
Ho trovato l’inverso
- moltiplico entrambi i membri per -1
(-1)6 k = 4(-1) mod 7 k = -4 mod 7 --> k è stato semplificato, mentre 4 bisogna moltiplicarlo per -1 k = 3 mod 7 -
Ho trovato k: adesso posso sostituire l’equazione iniziale
- me ne frego del modulo e scrivo: k2 app Z, k1 = 3 + 7k2 (k1 è preso dal passaggio precedente)
-
Il primo passaggio era
x = 5 + 18k1- adesso sono a conoscenza di quanto valga k1, quindi sostituisco
5 + 18 (3+7k2) = 5 + 54 + 126k2 = 59 + 126k2 -
Moltiplico i due moduli delle prime due equazioni: 18 * 21 = 378, quindi
x ≡ 59 mod 378 -
Devo fare la stessa cosa con la terza equazione. Si riportano solo i passaggi senza commenti.
Sistema: x ≡ 59 mod 378 x ≡ 23 mod 24 x = 59 + 378k1 59 + 378k1 ≡ 23 mod 24 378k1 = 23 - 59 mod 24 378k1 = -36 mod 24 --> normalizzo 378k1 = 12 mod 24 --> semplifico per 2 189k1 = 6 mod 12 --> semplifico per 3 63 k1 = 2 mod 4 Trovo l'inverso di 63 63 k1 ≡ 2 mod 4 63 = 4 * 15 + 1 3 = 63(1) + 4(-15) Quindi l'inverso di 63 è 1. k1 ≡ 2 mod 4 Scrivo quindi k app Z, k1 = 2 + 4k2 Risostituisco: la prima equazione scritta era x = 59 + 378k1 k1 ora ce l'ho, non mi resta che sostituire x = 59 + 378 (2 + 4k2) 59 + 762 + 1512 k2 815 + 1512 k2 Moltiplico i due moduli della seconda e terza equazione: 378 * 24, quindi x ≡ 815 mod 9072 -
La soluzione del sistema finale è 378
Sistemi congruenziali - Impossibili e non
Un sistema di equazioni congruenziali è impossibile quando scomponendo le equazioni in più sottoequazioni, esistono due equazioni con lo stesso modulo ma valore diverso.
Non impossibile avendo stesso modulo
x ≡ 5 mod 18
x ≡ 17 mod 21
x ≡ 23 mod 24
Per scomporlo:
-
Scomporre 18, 21 e 24 in fattori primi. Verranno fuori prodotti. Rispettivamente:
- 18: 9 * 2
- 21: 7 * 3
- 24: 3 * 8
-
Costruire le equazioni:
x ≡ mod 9 x ≡ mod 2 x ≡ mod 7 x ≡ mod 3 x ≡ mod 8 x ≡ mod 3 -
Devo riportare i numeri a destra di ≡ delle equazioni precedenti. Quindi:
x ≡ 5 mod 9 (rimane cosi) x ≡ 1 mod 2 (devo fare 17 mod 2 e scrivere quello che rimane) x ≡ 3 mod 7 x ≡ 2 mod 3 x ≡ 7 mod 8 x ≡ 2 mod 3 -
Ho due congruenze uguali. Le elimino e procedo nel risolvere le altre (ad esempio usando il metodo sbatti)
IMPOSSIBILE avendo stesso modulo
Testo:
x ≡ 7 mod 18
x ≡ 13 mod 21
x ≡ 11 mod 24
Per scomporlo:
-
Scomporre 18, 21 e 24 in fattori primi. Verranno fuori prodotti. Rispettivamente:
- 18: 9 * 2
- 21: 7 * 3
- 24: 3 * 8
-
Costruire le equazioni:
x ≡ mod 9 x ≡ mod 2 x ≡ mod 7 x ≡ mod 3 x ≡ mod 8 x ≡ mod 3 -
Devo riportare i numeri a destra di ≡ delle equazioni precedenti. Quindi:
x ≡ 7 mod 9 (rimane cosi) x ≡ 1 mod 2 (devo fare 17 mod 2 e scrivere quello che rimane) x ≡ 6 mod 7 x ≡ 1 mod 3 x ≡ 2 mod 8 x ≡ 2 mod 3 -
IL SISTEMA è IMPOSSIBILE! Infatti non esiste un numero che contemporaneamente soddisfa 2 mod 3 e 1 mod 3.
Sistema lineare con un parametro
Prerequisiti
- Teorema di Rouché Capelli
- data una matrice A a n incognite, abbiamo tre casi:
- unica soluzione: rk(A) = rk(A|b) = n
- infinite soluzioni: rk(A) = rk(A|b) = r < n
- nessuna soluzione: rk(A) != rk(A|b)
- NB: rango matrice “piccola”: rk(A), rango matrice aumentata rk(A|b)
- data una matrice A a n incognite, abbiamo tre casi:
- Gauss sulle matrici
- Concetto di pivot
- Concetto di portare la matrice a scala
- Concetto di rango (pivot)
Testo
Passaggi
- Trasformare la matrice aumentata a scala
- Vedere cosa succede per i parametri
- se una riga ha 0, la posso eliminare
- il rango di una matrice è il numero più piccolo di righe per colonne
- se elimino una qualsiasi riga, allora il rango “scende”
- Nei casi in cui c’è soluzione, mettere quel valore all’incognita e trovare x y z
Autovalori - autovettori
0 1 2
6 -1 4
-3 -1 -5
Trova matrice invertibile e matrice diagonale
-
Trovo il polinomio caratteristico che si trova facendo | lambda Identita - A |
x -1 -2 -6 x+1 -4 3 1 x+5(gia’ invertito i segni qua sopra)
-
Trovo il determinante: mi viene x(x+3)
-
Trovo gli zeri: x1 = 0, x2 = -3 e x3 = -3
-
Sostituisco nella matrice quella con la lambda, una volta x1 e una volta x2.
La prima volta mi esce
0 1 2
6 -1 4
-3 -1 -5
Devo portarmela a scala ridotta: dopo un po’ di manipolazioni mi esce:
1 0 1
0 1 2
0 0 0
Mi scrivo x e y (z non c’è), e mi escono
x + z = 0 --> x = -z
y + 2z = 0 --> y = -2z
Me lo scrivo sottoforma di vettore colonna: z(-1 -2 1)
- Stessa cosa con l’altro, mi verranno poi fuori
(1 -3 0)
(0 -2 1)
- Base: sono i vettori trovati
-1 1 0
-2 -3 -2
1 0 1
- D: sono gli autovalori
0 0 0
0 -3 0
0 0 -3
Basi Vettoriali
Prerequisiti
- basi vettoriali
- spazi vettoriali
- indipendenza vettoriale
- combinazione lineare
Riassunto
Una base vettoriale è un insieme di vettori linearmente indipendenti che generano uno spazio vettoriale. Ciò significa che ogni vettore nello spazio vettoriale può essere espressa come combinazione lineare dei vettori della base.
Supponiamo che abbiamo due vettori A = (2, 3) e B = (4, 5) in uno spazio vettoriale R2. La combinazione lineare dei due vettori è data da cA + dB dove c e d sono scalari. Ad esempio, se c = 1 e d = 2, la combinazione lineare sarà (2 * 1 + 4 * 2, 3 * 1 + 5 * 2) = (10, 11). In questo caso, il vettore (10, 11) è ottenuto come combinazione lineare dei vettori A e B con scalari 1 e 2 rispettivamente.
I generatori vettoriali sono invece un sottoinsieme di vettori che genera lo stesso spazio vettoriale. Possono essere utilizzati per creare una base vettoriale, ma non è detto che siano già una base.
Per esempio, se abbiamo uno spazio vettoriale V e una base vettoriale B = {v1, v2, …, vn}, allora i generatori vettoriali di V possono essere qualsiasi sottoinsieme di B, ad esempio G = {v1, v2}.
Generare uno spazio vettoriale significa costruire lo spazio a partire da un insieme di vettori a partire dai generatori e sono combinati tra loro per ottenere tutti i possibili vettori all’interno dello spazio.
Vettori linearmente indipendenti sono vettori che non possono essere descritti come una combinazione lineare di altri vettori. In altre parole, non esistono coefficienti scalari che possano essere utilizzati per produrre un vettore con una combinazione lineare di altri vettori.
Testo
Nello spazio vettoriale V = R4, si considerino i sottospazi
U1 := Span((1 1 −1 1), (0 −3 2 2))
U2 := (a b c d ∈ R4 | 3a + 2b + c = 0, b − c + d = 0)
(a) Si determini una base del sottospazio U1 ∩ U2.
(b) Si determini una base del sottospazio U1 + U2.
Soluzione
(a) Per determinare una base del sottospazio U1 ∩ U2, dobbiamo trovare vettori che appartengano a entrambi i sottospazi. Questo può essere fatto risolvendo un sistema di equazioni lineari.
Le equazioni che descrivono U2 sono: 3a + 2b + c = 0 b - c + d = 0
Per ogni vettore (a, b, c, d) che soddisfi queste equazioni, apparterrà a U2. Ora dobbiamo verificare che anche appartiene a U1. Possiamo farlo controllando se il vettore può essere espresso come combinazione lineare dei vettori che formano la base di U1. Se questo è possibile, allora il vettore apparterrà anche a U1.
La base di U1 è formata dai vettori (1 1 -1 1) e (0 -3 2 2). Possiamo rappresentare il vettore (a, b, c, d) come combinazione lineare di questi vettori usando i coefficienti alpha e beta: (a, b, c, d) = alpha * (1 1 -1 1) + beta * (0 -3 2 2)
Sostituendo i valori di a, b, c, d nel sistema di equazioni ottenuto dalla rappresentazione, possiamo risolvere per alpha e beta. Se troviamo una soluzione non nulla, allora il vettore apparterrà a entrambi i sottospazi e quindi apparterrà anche al loro intersezione.
Nel nostro caso, troviamo che la soluzione (a, b, c, d) = (1, -2, 1, 3) soddisfa entrambe le equazioni e può essere espresso come combinazione lineare dei vettori che formano la base di U1. Questo significa che (1, -2, 1, 3) apparterrà a U1 ∩ U2.
Questo ci dà un vettore che appartiene al sottospazio U1 ∩ U2. Possiamo verificare che non esiste un altro vettore che soddisfi entrambe le condizioni. Quindi (1, -2, 1, 3) è una base del sottospazio U1 ∩ U2.
Come ho trovato (1, -2, 1, 3)?
Risolvere un sistema lineare significa trovare dei valori che, sostituiti nell’equazione originale, diano zero.
Ho risolto con la sostituzione questo sistema:
3a + 2b + c = 0, b - c + d = 0 => quello in U2
Geometria (basi)
Determinare il parametro k ∈ R in modo tale che le due rette abbiano intersezione non vuota, e per questa scelta di k calcolare il punto di intersezione ed equazioni cartesiane del piano Π contenente le rette r1 e r2.
- Da prima equazione, possiamo sostituire c con
-3a - 2b: 3a + 2b + (-3a - 2b) = 0 2a = 0 a = 0 - Sostituiamo ora a e c nelle due equazioni:
3 * 0 + 2b + (-3 * 0 - 2b) = 0 2b = 0 b = 0 - Sostituiamo a, b e c nelle due equazioni:
0 + 0 + c = 0 c = 0 - Sostituiamo a, b, c nelle due equazioni
0 - 0 + d = 0 d = 0
Con questa cosa ho verificato il fatto che siano indipendenti. Basta che mi invento dei valori per cui il sistema risulti zero e ho fatto.
Se ad a b c d sostituisco (1, -2, 1, 3) ho fatto: sostituendo nel sistema originale questi valori ad a b c d mi viene tutto a zero.
(b) Per calcolare una base del sottospazio U1+U2, seguiamo questi passaggi:
- Calcoliamo la base di U2.
- Verifichiamo se ogni vettore della base di U2 appartiene anche a U1.
- Se un vettore della base di U2 non appartiene a U1, lo aggiungiamo alla base di U1.
- La base di U1+U2 sarà composta dai vettori che abbiamo ottenuto nei passaggi 2 e 3.
Per calcolare la base di U2, utilizziamo la soluzione dei sistemi di equazioni lineari:
3a + 2b + c = 0 \
b - c + d = 0
Possiamo utilizzare la seconda equazione per ottenere il valore di c in termini di a, b e d:
c = -b + d
Sostituendo questo valore in prima equazione, otterremo:
3a + 2b + (-b + d) = 0 \
3a - b + d = 0
Che può essere scritta come:
3a - b = -d \
b = 3a + d
Otteniamo due equazioni che descrivono le soluzioni di U2:
a = t \
b = 3t + d \
c = -3t - d \
d = s
Con t e s appartenenti a R. Queste equazioni descrivono tutti i vettori di U2.
Per calcolare la base di U2, scegliamo due valori specifici per t e s, ad esempio t=1 e s=0:
a = 1 \
b = 3 \
c = -3 \
d = 0
Questo darà il vettore (1, 3, -3, 0) che sarà uno dei vettori che compongono la base di U2. Scegliamo un altro valore per t e s, ad esempio t=0 e s=1:
a = 0 \
b = 1 \
c = -1 \
d = 1
Questo darà il vettore (0, 1, -1, 1) che sarà il secondo vettore che compongono la base di U2. La base di U2 sarà composta da questi due vettori.
Per calcolare la base di U1 + U2, dobbiamo verificare se i vettori della base di U2 appartengono a U1. Se un vettore della base di U2 non appartiene a U1, lo aggiungiamo alla base di U1. In questo caso, entrambi i vettori della base di U2 non appartengono a U1, quindi dobbiamo aggiungere entrambi i vettori alla base di U1. La base di U1 + U2 sarà composta dai vettori della base di U1 più i vettori della base di U2 che abbiamo appena aggiunto.Questa base sarà formata da 4 vettori: (1 1 −1 1), (0 −3 2 2), (0 −3 2 2) e (1 0 -3 3).