Swappa : Uni / Matematica del discreto - Guida agli esercizi 1°Parte

Torna alla pagina di Matematica del discreto

Questa pagina è stata aggiornata GRAZIE agli appunti che AVETE INVIATO nel periodo di chiusura della sezione UniCrema!! È SERVITA A QUALCOSA, NO?! ;)

 :: Matematica del discreto - Guida agli esercizi 1°Parte ::

Indice

Algoritmo di Euclide per il calcolo del M.C.D.
Cambio di base per numeri con la virgola
Passaggio da base b a base b²
Congruenze
Congruenze del tipo x^y ≡ w^z
Calcolare l'inverso
Divisibilità
Equazioni Diofantee
Gruppi di sostituzioni
Parità e disparità
Periodo di un elemento di un gruppo finito
Sottogruppi
Gruppi ciclici
Omomorfismi

1. Algoritmo di Euclide per il calcolo del M.C.D.

Es: calcolare il M.C.D. tra a=387 e b=144

a/b=387/144=2 r=99
b/r=144/99=1 r₁=45
r/r₁=99/45=2 r₂=5
r₁/r₂=45/5=9 r₃=0

quindi M.C.D. (387,144)=9

2. Cambio di base per numeri con la virgola

Es: trasformare 7,2₁₀ in base 6.

trasformo la parte intera: 7₁₀ = 11₆
moltiplico la parte decimale per la base: 0,2*6=1,2
tolgo la parte intera: 1,2-1=0,2
(la cifra sottolineata è la parte decimale della nuova base)
moltiplico per la base: 0,2*6=1,2

quindi 7,2₁₀=11,(1)₆ (le parentesi indicano il periodo)

Es2: trasformare 347,6₁₀ in base 7.



quindi 347₁₀=1004₇
Per la parte decimale:

0,6*7 = 4,2–4 = 0,2

0,2*7 = 1,4–1 = 0,4

0,4*7 = 2,8–2 = 0,8

0,8*7 = 5,6–5 = 0,6 ho ottenuto il numero da cui sono partito quindi mi fermo.

(le cifre sottolineate vanno considerate come nell'esercizio precedente)

risultato: 347,6₁₀ = 1004,(4125)₇

3. Passaggio da base b a base b²

abcde_n=[a][bc][de]_n² con [bc]=(b*n)+c & [de]=(d*n)+e

Es: trasformare 1004,(4125)₇ in base 7²

[10][04],[41][25]: [10]=(1*7)+0=7, [04]=(0*7)+4=4, [41]=(4*7)+1=29, [25]=(2*7)+5=19

quindi risulta 7:4,(29;19)

4. Congruenze

a ≡ b mod n ⇔ a mod n = b mod n

Per risolvere gli esercizi occorre applicare le seguenti proprietà:

(P1)
a x ≡ b mod n ⇔ (a mod n) x ≡ (b mod n) (mod n)

Esercizio:
155x≡85 mod 6 ⇔ (155 mod 6) x ≡ (85 mod 6) (mod 6)
155x≡85 mod 6 ⇔ 5x ≡ 1 mod 6

(P2)
a x ≡ b mod n ⇒ ka x ≡ kb mod n

Esercizio:
5 x ≡ 2 mod 7 ⇒ 3*5 x ≡ 2*3 mod 7

(P3)
ka x ≡ kb mod kn ⇒ ax ≡ b mod n

Esercizio:
3 x ≡ 3 mod 6 ⇒ x ≡ 1 mod 2

(P4)
ka x ≡ kb mod n se M.C.D. k,n = 1 ⇒ ax ≡ b mod n

Esercizio:
5x ≡ 5 mod 2 ⇒ x ≡ 1 mod 2

(P5)
ka x ≡ kb mod n(k≠0) ⇒ ax ≡ b mod (n/ M.C.D. (k,n))

Esercizio:
6x ≡ 6 mod 21 ⇒ x ≡ 1 mod 21/3 ⇒ x ≡ 1 mod 7

(P6)
ax ≡ b mod n, d∣n ⇒ ax ≡ b mod d

Esercizio:
3x ≡ 4 mod 10 ⇒ 3x ≡ 4 mod 2 o 3x ≡ 4 mod 5
3x ≡ 4 mod 2 ⇒ (3 mod 2) x ≡ 4 mod 2 mod 2 ⇒ x ≡ 0 mod 2

(P7)
ax ≡ b mod r e ax ≡ b mod s ⇒ ax ≡ b mod (m.c.m.(r,s))

Esercizio:
5x ≡ 4 mod 9 e 5x ≡ 4 mod 6 ⇒ 5x ≡ 4 mod 18

5. Congruenze del tipo x^y ≡ w^z

Teorema di Fermat:

a^p−1 ≡ 1 mod p, se p è primo

Teorema di Eulero-Fermat:

a^φn ≡ 1 mod n, se n non è un numero primo

Es: 231⁴⁴ ≡ 88⁷² mod 5.

Porto tutto in mod 5: 1⁴⁴ ≡ 3⁷² mod 5 ⇒ 1 ≡ 3⁷² mod 5
72 non è un numero primo, quindi applico Eulero.
φ(5)=4 (φ(n) è il numero di interi positivi minori o uguali a n, primi con n

a⁴≡1 mod 5 M.C.D. 5,1=1 ⇒ 3⁴≡1 mod 5

3⁷²=3⁴¹⁸ ⇒ 1≡1¹⁸ mod 5 ⇒ 1≡1 mod 5, VERIFICATA

Es2: 97³⁷ ≡ 11¹³⁴ mod 7

6³⁷ ≡ 4¹³⁴ mod 7, 7 è un numero primo, quindi applico Fermat

a⁷⁻¹ ≡ 1 mod 7 ⇒ a⁶ ≡ 1 mod 7

(6⁶)⁶*(4⁶)²² * 4² mod 7 ⇒ 1⁶*6 ≡ 1²²*16 mod 7 ⇒ 6 ≡ 2 mod 7, NON VERIFICATA

6. Calcolare l'inverso

Es. Trovare l'inverso di 4 in mod 9.

4*a ≡ 1 mod 9, a è l'inverso, ossia quel numero che moltiplicato per quattro e diviso per nove dà resto 1.

7. Divisibilità

Ci sono due metodi per stabilire se un numero a è divisibile per un altro numero b.

Metodo 1:

Stabilire se 646727 è divisibile per 17 utilizzando il criterio 17*3=51

50≡−1 mod 51 50=5⋅10, MCD5,17=1

646727 ⇒64672⋅107 ⇒

64672⋅10⋅57⋅5 ⇒64672⋅5035 ⇒64672⋅−135=−6467235=−64637

64637 ⇒6463⋅107⇒6463⋅5035=−6428

6428 ⇒642⋅108⇒642⋅5040=−602

602 ⇒60⋅102⇒60⋅50 10=−50, non congruo a 0⇒ 646727 non divisibile per 17

Stabilire se 615908 è divisibile per 31

30≡−1 mod 31

615908⇒61590⋅108⇒61590⋅10⋅38⋅3⇒61590⋅30 24=−6159024=−61566

61566 ⇒6156⋅106 ⇒6156⋅3018=−6138

6138⇒613⋅108 ⇒613⋅3024=−589

589⇒ 58⋅109⇒58⋅3027=−31, divisibile per 31 ⇒615908 divisibile per 31

Metodo 2:

Stabilire se 646727 è divisibile per 31

6⋅10⁵ 4⋅10⁴6⋅10³7⋅10²2⋅10¹7⋅10⁰

calcolo i resti delle potenze di 10 (ossia calcolo le potenze di 10 mod 31)

10⁵=100000 ⇒ 100000 ≡ 25 mod 31,

10⁴=10000 ⇒ 10000 ≡ 18 mod 31, 10³=1000 ⇒ 1000 ≡ 8 mod 31, 10²=100 ⇒ 100≡7 mod 31''

10¹=10 ⇒ 10≡10 mod 31, 10⁰=1 ⇒ 1≡1 mod 31

sostituisco nella prima formula al posto delle potenze di 10 i resti trovati

6⋅254⋅186⋅87⋅72⋅107⋅1

6⋅25=150, 150≡−5 mod 31 ; 4⋅18=72, 72≡10 mod 31; 6⋅8=48, 48≡17 mod 31

7⋅7=49, 49≡18 mod 31 ; 2⋅10=20, 20≡20 mod 31 ; 7≡7 mod 31

−5101718207=67 ⇒ non divisibile per 31

8. Equazioni Diofantee

a⋅x b⋅y=c ammette soluzione se e solo se c multiplo di MCDa,b

Es. 2x3y=12

Calcolo MCD(2,3)=1; 12 è un multiplo di 1 quindi l'equazione è risolvibile.

So che:

ax≡c mod b oppure by≡c mod a quindi:

2x≡12 mod 3 ∨ 3y≡12 mod 2, porto nei rispettivi mod e scelgo la più "comoda"

2x≡0 mod 3 ∨ y≡0 mod 2, scelgo la II ⇒ y =02⋅h⇒ y=2h ⇒ 2x3⋅2h =12

2x6h=12 ⇒ 2x=12−6h ⇒ x=6−3h ⇒

{

x=6−3h
y =2h

Es2: determinare il più piccolo p>2 per cui 7x+3y=p ammette soluzioni e calcolarle.

MCD(7,3)=1, il più piccolo multiplo di 1 maggiore di 2 è 3, quindi p=3

7x≡3 mod 3 ∨ 3y≡3 mod 7⇒ x≡0 mod 3 ∨ 3y≡3 mod 7 ; scelgo la prima

x=03h ⇒ 7⋅3h3y=3⇒ 3y=3−21h ⇒

{

x=3h
y=1-7h

9. Gruppi di sostituzioni

f=(1 5 2 4 3) ⇒ f⁻¹=(1 3 4 2 5)

Es:

(

1 2 3 4 5 6
5 2 1 3 6 4

)

Cosa vuol dire? Descrive le trasformazioni, la prima riga elenca gli elementi, la seconda come cambiano, cioè:

1 diventa 5,

2 diventa 2,

3 diventa 1,

4 diventa 3,

5 diventa 6,

6 diventa 4.

Quindi partendo da 1 vado in 5, da 5 in 6, da 6 in 4, da 4 in 3, da 3 in 1. Allora posso scriverla così: 1 5 6 4 3.

Ogni permutazione (o sostituzione) può essere scritta, in modo unico, come prodotto di cicli disgiunti. Come si fa?

α=1 5 2 83 7 2 4 5 81 4 8 3 6
Si va da destra a sinistra, parto da 1 e vado a vedere in cosa di trasforma: 1 va in 4, (mi sposto nel secondo gruppo) 4 va in 5, (mi sposto nel terzo), 5 va in 2. Sono partito da 1 e sono arrivato in 2, quindi 1 va in 2.
Comincio a compilare il prodotto di cicli disgiunti:
α= 1 2 ..riparto: 2 nel primo gruppo non c'è, questo vuol dire che 2 va in 2, ossia non cambia, mi sposto nel secondo 2 va in 4, nel terzo 4 va in 4. Quindi 2 va in 4.
α= 1 2 4 ..proseguo in questo modo e ottengo α= 1 2 4 3 6 5
5 va in 5, mi sposto 5 va in 8, mi sposto 8 va in 1. 5 va in 1 quindi il ciclo si chiude.
α= 1 2 4 3 6 5  Gli elementi di α da cui sono partito sono 8, a={1,2,3,4,5,6,7,8}.
Nel nuovo ciclo che ho scritto ne compaiono 6, mancano {7} e {8} che quindi compongono un ciclo tra di loro. Infatti 7 va in 7, 7 va in 2, 2 va in 8.
Quindi se voglio scrivere α come prodotto di cicli disgiunti sarà: α=1 2 4 3 6 57 8

Vediamo un altro esempio per togliere ogni dubbio.
α=0 5 2 8 14 9 6 12 8 30 2 4 9 3⇒ α=0 1 4 62 9 8 3 5
L'unico elemento che manca è 7, ma non comparendo mai significa che non cambia, quindi non lo scrivo.

N.B: poiché si tratta di cicli non è importante da quale elemento si parte, io vado in ordine per comodità (parto dal minor elemento non ancora utilizzato) ma:
->0 1 4 6=1 4 6 0=4 6 0 1=6 0 1 4 quindi scrivere α=0 1 4 62 9 8 3 5

o , ad esempio , α=6 0 1 43 5 2 9 8 è la stessa cosa!!!

10. Parità e disparità

Per calcolarle la parità di una sostituzione occorre scriverla come prodotto di trasposizioni e poi contare il numero di trasposizioni.

1 2 4 3 6 58 7⇒1 21 41 31 61 57 8 ⇒6 ⇒ PARI
0 1 4 63 5 2 9 8⇒0 10 40 63 53 23 93 8⇒ 7⇒ DISPARI

11. Periodo di un elemento di un gruppo finito

Periodo di un ciclo.

caso1:

p=1 3 6 8 2 5 4 il ciclo ha lunghezza 7 (formato da 7 elementi), quindi il periodo di p è 7

caso2:

q=1 3 5 2 4 6 7 lunghezza cicli 4 e 3. m.c.m(4,3)=12, quindi il periodo di q è 12

IMPORTANTE:
Con u definiamo l'elemento neutro rispetto all'operazione.
a⁰=u ; a¹=u°a ; a²=u°a°a ; ..e così via
Ad esempio se ° corrisponde alla somma: a⁰=0 ; a¹=0a ; a²=0aa=2a

N.B: Sia p un elemento di periodo 12. Che periodo hanno p³, p⁵, p⁸, p⁹, p¹⁰? Come fare a calcolare il periodo di q^b se q ha periodo a?

Calcolo M.C.D.(a,b)
Calcolo m.c.m.= a⋅b/M.C.D.
periodo= (m.c.m. / b)

Nel nostro esercizio:

p¹²= p'^3 '^4=id ⇒ p'^3 ha periodo 4

p⁵: MCD5,12=1, mcm5,12=60, 60/5=12 ⇒ p⁵ ha periodo12

p⁸: MCD8,12=4, mcm 8,12=24, 24 /8=3⇒ p⁸ ha periodo 3

p⁹: MCD9,12=3, mcm 9,12=36, 36/ 9=4 ⇒ p⁹ ha periodo 4

p¹⁰: MCD10,12=2, mcm 10,12=60, 60 /10=6 ⇒ p¹⁰ ha periodo 6

12. Sottogruppi

S₆={1,2,3,4,5,6} α=2 6 3 54 6 53 4 61 5 3 ⇒α=1 4 2 6 5 3 H è un sottogruppo di S₆ generato da α. Calcolare ordine e elementi di H.

L'ordine del sottogruppo coincide con il periodo del generatore. α ha periodo 6 quindi gli elementi di H sono H={α , α 2, α 3, α 4, α5, α 6 =id}

α²=142653142653=125346; α³ =124653125346=16 23 45

α⁴ =14265316 23 45=152364 ; α⁵=124653152364=135624''

Per calcolare il laterale destro di α dato da, per esempio, (123) faccio semplicemente α(123); per il sinistro (123)α.

Sottogruppi di Z*₁₂,x={1,5,7,11}

il periodo di 1=1 per convenzione
il periodo di 5: 5ⁿ≡1 mod 12 , se n=2 5²≡1 mod 12 ⇒il periodo di 5 in Z*₁₂ è 2, sottogr. {1,5}
il periodo di 7: 7²≡1 mod 12⇒ il periodo di 7 è 2, sottogruppo {1,7}
il periodo di 11: 11²≡1 mod 12 ⇒ il periodo di 11 è 2, sottogruppo {1,11}

L'ordine del sottogruppo deve essere un divisore dell'ordine del gruppo.

Sottogruppi di Z*₁₆,x ={1,3,5,7,9,11,13,15}
L'ordine di Z*₁₆ è 8 quindi l'ordine dei sottogruppi può essere 2 o 4.

13. Gruppi ciclici

Trovare un generatore diverso da 1 per: Z₈,= {0,1,2,3,4,5,6,7}

Un generatore è un elemento appartenente al gruppo su cui continuando ad eseguire l'operazione del gruppo ottengo tutti gli elementi. Nell'esercizio:

1: 1⁰=0, 1¹=1, 1²=11=2, 1³=111=3 ... 1⁷=7 ok, è un generatore

2: 2⁰=0, 2¹=2, 2²=4, 2³=6, 2⁴=8 in mod8=0 , 2⁵=10=2 ⇒{0,2,4,6}2 non è un generatore

3: 3⁰=0, 3¹=3, 3²=6, 3³=9=1, 3⁴=12=4, 3⁵=15=7, 3⁶=18=2, 3⁷ =21=5

⇒{0,1,2,3,4,5,6,7}⇒3 è un generatore

14. Omomorfismi

Per svolgere gli esercizi bisogna prima osservare se il primo gruppo (dominio) è ciclico.

Se è ciclico l'esercizio è facile, devo solo costruire la tavola pitagorica degli omomorfismi. Si fa così:

nella prima colonna un generatore e le sue potenze (ad esempio h)
nella prima riga gli elementi del codomio
nella seconda riga copio gli elementi della prima riga
si riempiono le colonne applicando le potenze del generatore all'elemento del codominio. (tenere conto dell'operazione e del numero di elementi del codominio; se sono in Z₇,+ 2³=222=8, che in mod7 fa 1)

Es. GZ*₇,x

G è ciclico per ipotesi, elemento generatore "q", ordine 4

Z*₇,x è ciclico, i suoi elementi sono {1,2,3,4,5,6}

f	1	2	3	4	5	6
q	1	2	3	4	5	6
q²	1²=1	22=4	2	2	4	1
q³	1	23=8mod7=1	6	1	6	6
q⁴=id	1	2	4	4	2	1
Ker{f}	X	NO	NO	NO	NO	{q²,id}
Img{f}	{1}	NO	NO	NO	NO	{1,6}

Se c'è omomorfismo il nucleo è composto dalle potenze del generatore che danno il neutro dell'operazione (in questo caso 1).

Se non è ciclico si utilizzano gli ordini di nucleo e immagini.
Il teorema dell'ordine dice che l'ordine del dominio è dato dal prodotto di ordine del nucleo e ordine dell'immagine.

Ord(dominio)= Ord(ker) x Ord(img)

Un nucleo è l'insieme degli elementi che vengono trasformati nel neutro del codominio.
L'immagine è l'insieme degli elementi che sono trasformati negli elementi del dominio.
Esempio:

Z*₁₂,xZ*₁₄,x

Z*₁₂,x ha elementi {1,5,7,11}, quindi ordine 4 e non è ciclico

Z*₁₄,x ha elementi {1,3,5,9,11,13}, quindi ordine 6 ed è ciclico

Ord(dominio)=4 quindi 4=Ord(ker) x Ord(img)

4=1x4 non è omomorfismo perchè non esistono immagini di ordine 4

4=4x1 è l'omomorfismo banale

4=2x2 devo trovare l'immagine, ossia un sottogruppo di dimensione 2 di Z₁₄

n-1 ha sempre periodo 2 in Z_n, quindi come immagine prendo {1,13}

Ora costruisco la tabella: guardo gli elementi del nucleo e metto 1 in corrispondenza di quei valori nelle colonne, 13 nelle altre. Otterrò la seguente tabella:

Nucleo	Immagine	1	5	7	11
1,5	1,13	1	1	13	13
1,7	1,13	1	13	1	13
1,11	1,13	1	13	13	1
1,5,7,11	1,13	1	1	1	1