cerca
Matematica del discreto - Guida agli esercizi 1°Parte
modifica cronologia stampa login logout

Wiki

UniCrema


Materie per semestre

Materie per anno

Materie per laurea


Help

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 ::

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 r1=45
r/r1=99/45=2 r2=5
r1/r2=45/5=9 r3=0

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

2. Cambio di base per numeri con la virgola

Es: trasformare 7,210 in base 6.

  1. trasformo la parte intera: 710 = 116
  2. moltiplico la parte decimale per la base: 0,2*6=1,2
  3. tolgo la parte intera: 1,2-1=0,2
    (la cifra sottolineata è la parte decimale della nuova base)
  4. moltiplico per la base: 0,2*6=1,2

quindi 7,210=11,(1)6 (le parentesi indicano il periodo)

Es2: trasformare 347,610 in base 7. 

347 | 4
 49 | 0
  7 | 0
  1 | 1
  0 |




quindi 34710=10047
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,610 = 1004,(4125)7

3. Passaggio da base b a base b2

abcden=[a][bc][de]n2 con [bc]=(b*n)+c & [de]=(d*n)+e

Es: trasformare 1004,(4125)7 in base 72

[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 xy ≡ wz

Teorema di Fermat:

ap−1 ≡ 1 mod p, se p è primo

Teorema di Eulero-Fermat:

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

Es: 23144 ≡ 8872 mod 5.

Porto tutto in mod 5: 144 ≡ 372 mod 5 ⇒ 1 ≡ 372 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

a4≡1 mod 5 M.C.D. 5,1=1 ⇒ 34≡1 mod 5
372=3418 ⇒ 1≡118 mod 5 ⇒ 1≡1 mod 5, VERIFICATA

Es2: 9737 ≡ 11134 mod 7

637 ≡ 4134 mod 7, 7 è un numero primo, quindi applico Fermat

a7−1 ≡ 1 mod 7 ⇒ a6 ≡ 1 mod 7

(66)6*(46)22 * 42 mod 7 ⇒ 16*6 ≡ 122*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⋅105 4⋅1046⋅1037⋅1022⋅1017⋅100
calcolo i resti delle potenze di 10 (ossia calcolo le potenze di 10 mod 31)
105=100000 ⇒ 100000 ≡ 25 mod 31,
104=10000 ⇒ 10000 ≡ 18 mod 31, 103=1000 ⇒ 1000 ≡ 8 mod 31, 102=100 ⇒ 100≡7 mod 31''
101=10 ⇒ 10≡10 mod 31, 100=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=(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.
a0=u ; a1=u°a ; a2=u°a°a ; ..e così via
Ad esempio se ° corrisponde alla somma: a0=0 ; a1=0a ; a2=0aa=2a

N.B: Sia p un elemento di periodo 12. Che periodo hanno p3, p5, p8, p9, p10? Come fare a calcolare il periodo di qb se q ha periodo a?

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

Nel nostro esercizio:

p12= p'^3 '^4=id ⇒ p'^3 ha periodo 4
p5: MCD5,12=1, mcm5,12=60, 60/5=12 ⇒ p5 ha periodo12
p8: MCD8,12=4, mcm 8,12=24, 24 /8=3⇒ p8 ha periodo 3
p9: MCD9,12=3, mcm 9,12=36, 36/ 9=4 ⇒ p9 ha periodo 4
p10: MCD10,12=2, mcm 10,12=60, 60 /10=6 ⇒ p10 ha periodo 6

12. Sottogruppi

S6={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 S6 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}

α2=142653142653=125346; α3 =124653125346=16 23 45
α4 =14265316 23 45=152364 ; α5=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*12,x={1,5,7,11}

  • il periodo di 1=1 per convenzione
  • il periodo di 5: 5n≡1 mod 12 , se n=2 52≡1 mod 12 ⇒il periodo di 5 in Z*12 è 2, sottogr. {1,5}
  • il periodo di 7: 72≡1 mod 12⇒ il periodo di 7 è 2, sottogruppo {1,7}
  • il periodo di 11: 112≡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*16,x ={1,3,5,7,9,11,13,15}
L'ordine di Z*16 è 8 quindi l'ordine dei sottogruppi può essere 2 o 4.

13. Gruppi ciclici

Trovare un generatore diverso da 1 per: Z8,= {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: 10=0, 11=1, 12=11=2, 13=111=3 ... 17=7 ok, è un generatore
2: 20=0, 21=2, 22=4, 23=6, 24=8 in mod8=0 , 25=10=2 ⇒{0,2,4,6}2 non è un generatore
3: 30=0, 31=3, 32=6, 33=9=1, 34=12=4, 35=15=7, 36=18=2, 37 =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ì:

  1. nella prima colonna un generatore e le sue potenze (ad esempio h)
  2. nella prima riga gli elementi del codomio
  3. nella seconda riga copio gli elementi della prima riga
  4. 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 Z7,+ 23=222=8, che in mod7 fa 1)

Es. GZ*7,x

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

Z*7,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
q2 12=1 22=4 2 2 4 1
q3 1 23=8mod7=1 6 1 6 6
q4=id 1 2 4 4 2 1
Ker{f} X NO NO NO NO {q2,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*12,xZ*14,x
Z*12,x ha elementi {1,5,7,11}, quindi ordine 4 e non è ciclico
Z*14,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 Z14
n-1 ha sempre periodo 2 in Zn, 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

Torna alla pagina di Matematica del discreto