|
Wiki
UniCrema
Materie per semestre
Materie per anno
Materie per laurea
Help
|
|
Uni.MDD-EserciziPrimaParte History
Hide minor edits - Show changes to output
Changed line 412 from:
(:table align=center cellpadding=10 bgcolor=#E0EBF4:) to:
(:table align=center cellpadding=10 border=2 bordercolor=white bgcolor=#E0EBF4:) Changed line 484 from:
(:table align=center cellpadding=10 bgcolor=#E0EBF4:) to:
(:table align=center cellpadding=10 border=2 bordercolor=white bgcolor=#E0EBF4:)
Changed line 412 from:
(:table align=center cellpadding=10 bgcolor=#fbf3ff:) to:
(:table align=center cellpadding=10 bgcolor=#E0EBF4:) Changed line 484 from:
(:table align=center cellpadding=10 bgcolor=#fbf3ff:) to:
(:table align=center cellpadding=10 bgcolor=#E0EBF4:)
Added lines 11-32:
>>left bgcolor=#f5f9fc width=320px border='2px solid #cccccc' padding=5px<<
%center%'''Indice'''
# [[#e1|Algoritmo di Euclide per il calcolo del M.C.D.]]
# [[#e2|Cambio di base per numeri con la virgola]]
# [[#e3|Passaggio da base b a base b'^2^']]
# [[#e4|Congruenze]]
# [[#e5|Congruenze del tipo x'^y^' ≡ w'^z^']]
# [[#e6|Calcolare l'inverso]]
# [[#e7|Divisibilità]]
# [[#e8|Equazioni Diofantee]]
# [[#e9|Gruppi di sostituzioni]]
# [[#e10|Parità e disparità]]
# [[#e11|Periodo di un elemento di un gruppo finito]]
# [[#e12|Sottogruppi]]
# [[#e13|Gruppi ciclici]]
# [[#e14|Omomorfismi]]
>><<
----
[[#e1]] Added line 45:
Added line 89:
Added line 103:
Added line 162:
Added line 187:
Added line 196:
Added line 237:
Added line 273:
Added line 319:
Added line 330:
Added line 358:
Added line 383:
Added line 397:
Changed line 412 from:
(:table align=center cellspacing=10 bgcolor=#dddddd:) to:
(:table align=center cellpadding=10 bgcolor=#fbf3ff:) Changed line 484 from:
(:table align=center cellspacing=10 bgcolor=#dddddd:) to:
(:table align=center cellpadding=10 bgcolor=#fbf3ff:)
Changed lines 432-433 from:
to:
'''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 Z'_14_'
-->'''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:
(:table align=center cellspacing=10 bgcolor=#dddddd:)
(:cellnr:)'''Nucleo'''
(:cell:)'''Immagine'''
(:cell:)'''1'''
(:cell:)'''5'''
(:cell:)'''7'''
(:cell:)'''11'''
(:cellnr:)1,5
(:cell:)1,13
(:cell:)1
(:cell:)1
(:cell:)13
(:cell:)13
(:cellnr:)1,7
(:cell:)1,13
(:cell:)1
(:cell:)13
(:cell:)1
(:cell:)13
(:cellnr:)1,11
(:cell:)1,13
(:cell:)1
(:cell:)13
(:cell:)13
(:cell:)1
(:cellnr:)1,5,7,11
(:cell:)1,13
(:cell:)1
(:cell:)1
(:cell:)1
(:cell:)1
(:tableend:)
Added lines 364-434:
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'_7_',+ 2'^3^'=222=8, che in mod7 fa 1)''
'''Es. GZ*'_7_',x'''
>>left bgcolor=#f5f9fc width=auto border='2px solid #cccccc' padding=5px<<
G è ciclico per ipotesi, elemento generatore "q", ordine 4
->Z*'_7_',x è ciclico, i suoi elementi sono {1,2,3,4,5,6}
(:table align=center cellspacing=10 bgcolor=#dddddd:)
(:cellnr:)'''f'''
(:cell:)'''1'''
(:cell:)'''2'''
(:cell:)'''3'''
(:cell:)'''4'''
(:cell:)'''5'''
(:cell:)'''6'''
(:cellnr:)'''q'''
(:cell:)1
(:cell:)2
(:cell:)3
(:cell:)4
(:cell:)5
(:cell:)6
(:cellnr:)'''q'^2^''''
(:cell:)1'^2^'=1
(:cell:)22=4
(:cell:)2
(:cell:)2
(:cell:)4
(:cell:)1
(:cellnr:)'''q'^3^''''
(:cell:)1
(:cell:)23=8''mod''7=1
(:cell:)6
(:cell:)1
(:cell:)6
(:cell:)6
(:cellnr:)'''q'^4^'=id'''
(:cell:)1
(:cell:)2
(:cell:)4
(:cell:)4
(:cell:)2
(:cell:)1
(:cellnr:)'''Ker{f}'''
(:cell:)X
(:cell:)NO
(:cell:)NO
(:cell:)NO
(:cell:)NO
(:cell:){q'^2^',id}
(:cellnr:)'''Img{f}'''
(:cell:){1}
(:cell:)NO
(:cell:)NO
(:cell:)NO
(:cell:)NO
(:cell:){1,6}
(:tableend:)
Se c'è omomorfismo il nucleo è composto dalle potenze del generatore che danno il neutro dell'operazione (in questo caso 1).
>><<
Added lines 21-22:
Added lines 64-65:
Added lines 77-78:
Added lines 135-136:
Added lines 159-160:
Added lines 167-168:
Added lines 206-363:
----
!!!8. Equazioni Diofantee
'''a⋅x b⋅y=c ''ammette soluzione se e solo se'' c multiplo di MCDa,b'''
'''Es. 2x3y=12'''
>>left bgcolor=#f5f9fc width=auto border='2px solid #cccccc' padding=5px<<
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''
(:table:)
(:cellnr valign=middle:)
-->2x6h=12 ⇒ 2x=12−6h ⇒ x=6−3h ⇒
(:cell:)[++++{++++]
(:cell:)x=6−3h\\
y =2h
(:tableend:)
>><<
'''Es2: determinare il più piccolo p>2 per cui 7x+3y=p ammette soluzioni e calcolarle.'''
>>left bgcolor=#f5f9fc width=auto border='2px solid #cccccc' padding=5px<<
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''
(:table:)
(:cellnr valign=middle:)
->x=03h ⇒ 7⋅3h3y=3⇒ 3y=3−21h ⇒
(:cell:)[++++{++++]
(:cell:)x=3h\\
y=1-7h
(:tableend:)
>><<
----
!!!9. Gruppi di sostituzioni
'''f=(1 5 2 4 3) ⇒ f'^−1^'=(1 3 4 2 5)'''
Es:
(:table:)
(:cellnr:)
[++++(++++]
(:cell:)1 2 3 4 5 6\\
5 2 1 3 6 4
(:cell:)[++++)++++]
(:tableend:)
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.
>>left bgcolor=#f5f9fc width=auto border='2px solid #cccccc' padding=5px<<
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'^0^'=u''' ; '''a'^1^'=u°a''' ; '''a'^2^'=u°a°a''' ; ..e così via\\
Ad esempio se ° corrisponde alla somma: a'^0^'=0 ; a'^1^'=0a ; a'^2^'=0aa=2a
'''N.B''': Sia p un elemento di periodo 12. Che periodo hanno p'^3^', p'^5^', p'^8^', p'^9^', p'^10^'? 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'^12^'= p'^3 '^4=id ⇒ p'^3 ha periodo 4
->p'^5^': MCD5,12=1, mcm5,12=60, 60/5=12 ⇒ p'^5^' ha periodo12
->p'^8^': MCD8,12=4, mcm 8,12=24, 24 /8=3⇒ p'^8^' ha periodo 3
->p'^9^': MCD9,12=3, mcm 9,12=36, 36/ 9=4 ⇒ p'^9^' ha periodo 4
->p'^10^': MCD10,12=2, mcm 10,12=60, 60 /10=6 ⇒ p'^10^' ha periodo 6
----
!!!12. Sottogruppi
S'_6_'={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'_6_' generato da α. Calcolare ordine e elementi di H.
>>left bgcolor=#f5f9fc width=auto border='2px solid #cccccc' padding=5px<<
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: 5'^n^'≡1 mod 12 , se n=2 5'^2^'≡1 mod 12 ⇒il periodo di 5 in Z*'_12_' è 2, sottogr. {1,5}
* il periodo di 7: 7'^2^'≡1 mod 12⇒ il periodo di 7 è 2, sottogruppo {1,7}
* il periodo di 11: 11'^2^'≡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: Z'_8_',= {0,1,2,3,4,5,6,7}
>>left bgcolor=#f5f9fc width=auto border='2px solid #cccccc' padding=5px<<
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^'=0, 1'^1^'=1, 1'^2^'=11=2, 1'^3^'=111=3 ... 1'^7^'=7 ok, è un generatore
->2: 2'^0^'=0, 2'^1^'=2, 2'^2^'=4, 2'^3^'=6, 2'^4^'=8 in mod8=0 , 2'^5^'=10=2 ⇒{0,2,4,6}2 non è un generatore
->3: 3'^0^'=0, 3'^1^'=3, 3'^2^'=6, 3'^3^'=9=1, 3'^4^'=12=4, 3'^5^'=15=7, 3'^6^'=18=2, 3'^7^' =21=5
->⇒{0,1,2,3,4,5,6,7}⇒3 è un generatore
>><<
----
!!!14. Omomorfismi
Changed lines 157-193 from:
to:
!!!7. Divisibilità
Ci sono due metodi per stabilire se un numero ''a'' è divisibile per un altro numero ''b''.
'''Metodo 1:'''
>>left bgcolor=#f5f9fc width=auto border='2px solid #cccccc' padding=5px<<
'''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''
>><<
>>left bgcolor=#f5f9fc width=auto border='2px solid #cccccc' padding=5px<<
'''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:'''
>>left bgcolor=#f5f9fc width=auto border='2px solid #cccccc' padding=5px<<
'''Stabilire se 646727 è divisibile per 31'''
->6⋅10'^5^' 4⋅10'^4^'6⋅10'^3^'7⋅10'^2^'2⋅10'^1^'7⋅10'^0^'
->''calcolo i resti delle potenze di 10 (ossia calcolo le potenze di 10 mod 31)''
->10'^5^'=100000 ⇒ 100000 ≡ 25 mod 31,
->10'^4^'=10000 ⇒ 10000 ≡ 18 mod 31, 10'^3^'=1000 ⇒ 1000 ≡ 8 mod 31, 10'^2^'=100 ⇒ 100≡7 mod 31''
->10'^1^'=10 ⇒ 10≡10 mod 31, 10'^0^'=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''
>><<
Changed lines 11-13 from:
!!!!1. Algoritmo di Euclide per il calcolo del M.C.D. tra a & b
a=387, b=144 to:
!!!1. Algoritmo di Euclide per il calcolo del M.C.D.
'''Es: calcolare il M.C.D. tra ''a=387'' e ''b=144''''' Changed line 21 from:
!!!!2. Cambio di base per numeri con la virgola
to:
!!!2. Cambio di base per numeri con la virgola Added line 24:
>>left bgcolor=#f5f9fc width=auto border='2px solid #cccccc' padding=5px<< Changed lines 32-33 from:
to:
Added line 36:
>>left bgcolor=#f5f9fc width=auto border='2px solid #cccccc' padding=5px<< Changed lines 60-61 from:
!!!!3. Passaggio da base b a base b'^2^'
to:
>><<
!!!3. Passaggio da base b a base b'^2^' Added line 67:
>>left bgcolor=#f5f9fc width=auto border='2px solid #cccccc' padding=5px<< Changed lines 71-72 from:
to:
Changed lines 77-79 from:
* '''(P1): ''a x ≡ b mod n ⇔ (a mod n) x ≡ (b mod n) (mod n)'''''\\
Es: 155x≡85 mod 6 ⇔155 mod 6 x≡85 mod 6mod 6\\
155x≡85 mod 6⇔ 5x≡1 mod 6
to:
'''(P1)'''\\
''a x ≡ b mod n ⇔ (a mod n) x ≡ (b mod n) (mod n)''
>>left bgcolor=#f5f9fc width=auto border='2px solid #cccccc' padding=5px<<
''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''
>>left bgcolor=#f5f9fc width=auto border='2px solid #cccccc' padding=5px<<
''Esercizio:''\\
5 x ≡ 2 mod 7 ⇒ 3*5 x ≡ 2*3 mod 7
>><<
'''(P3)'''\\
''ka x ≡ kb mod kn ⇒ ax ≡ b mod n''
>>left bgcolor=#f5f9fc width=auto border='2px solid #cccccc' padding=5px<<
''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''
>>left bgcolor=#f5f9fc width=auto border='2px solid #cccccc' padding=5px<<
''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))''
>>left bgcolor=#f5f9fc width=auto border='2px solid #cccccc' padding=5px<<
''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''
>>left bgcolor=#f5f9fc width=auto border='2px solid #cccccc' padding=5px<<
''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))''
>>left bgcolor=#f5f9fc width=auto border='2px solid #cccccc' padding=5px<<
''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'^44^' ≡ 88'^72^' mod 5.'''
>>left bgcolor=#f5f9fc width=auto border='2px solid #cccccc' padding=5px<<
Porto tutto in mod 5: ''1'^44^' ≡ 3'^72^' mod 5 ⇒ 1 ≡ 3'^72^' 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'^4^'≡1 mod 5 M.C.D. 5,1=1 ⇒ 3'^4^'≡1 mod 5''
->''3'^72^'=3'^4^''^18^' ⇒ 1≡1'^18^' mod 5 ⇒ 1≡1 mod 5, VERIFICATA''
>><<
'''Es2: 97'^37^' ≡ 11'^134^' mod 7'''
>>left bgcolor=#f5f9fc width=auto border='2px solid #cccccc' padding=5px<<
''6'^37^' ≡ 4'^134^' mod 7'', 7 è un numero primo, quindi applico Fermat
->''a'^7−1^' ≡ 1 mod 7 ⇒ a'^6^' ≡ 1 mod 7''
''(6'^6^')'^6^'*(4'^6^')'^22^' * 4'^2^' mod 7 ⇒ 1'^6^'*6 ≡ 1'^22^'*16 mod 7 ⇒ 6 ≡ 2 mod 7'', NON VERIFICATA
>><<
!!!6. Calcolare l'inverso
'''Es. Trovare l'inverso di 4 in mod 9'''.
>>left bgcolor=#f5f9fc width=auto border='2px solid #cccccc' padding=5px<<
''4*a ≡ 1 mod 9'', a è l'inverso, ossia quel numero che moltiplicato per quattro e diviso per nove dà resto 1.
>><<
Changed line 11 from:
!!!!Algoritmo di Euclide per il calcolo del M.C.D. tra a & b to:
!!!!1. Algoritmo di Euclide per il calcolo del M.C.D. tra a & b Changed lines 14-21 from:
a/b=387/144=2 r=99
b/r=144/99=1 r'_1_'=45
r/r'_1_'=99/45=2 r'_2_'=5
r'_1_'/r'_2_'=45/5=9 r'_3_'=0 quindi M.C.D. (387,144)=9
Es: trasformare 7,2'_10_' in base 6. to:
a/b=387/144=2 r=99\\
b/r=144/99=1 r'_1_'=45\\
r/r'_1_'=99/45=2 r'_2_'=5\\
r'_1_'/r'_2_'=45/5=9 r'_3_'=0
quindi '''M.C.D. (387,144)=9'''
!!!!2. Cambio di base per numeri con la virgola
'''Es: trasformare 7,2'_10_' in base 6.''' Changed line 27 from:
[-(la cifra sottolineata è la parte decimale della nuova base. Quindi 7,2'_10_'=11,(1)'_6_' . Le parentesi indicano il periodo)-] to:
[-(la cifra sottolineata è la parte decimale della nuova base)-] Changed lines 29-33 from:
è la parte decimale nella nuova base. Quindi 7,2'_10_'=11,(1)'_6_' Le parentesi indicano il
periodo.
Es2: trasformare 347,6'_10_' in base 7.
to:
quindi '''7,2'_10_'=11,(1)'_6_' ''' (le parentesi indicano il periodo)
'''Es2: trasformare 347,6'_10_' in base 7.'''
Changed lines 56-58 from:
347,6'_10_' = 1004,(4125)'_7_'
to:
risultato: '''347,6'_10_' = 1004,(4125)'_7_''''
!!!!3. Passaggio da base b a base b'^2^' Changed lines 61-62 from:
Es: trasformare 1004,(4125)'_7_' in base 7'^2^'\\ to:
'''Es: trasformare 1004,(4125)'_7_' in base 7'^2^'''' Changed lines 65-66 from:
quindi risulta 7:4,(29;19) to:
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)'''''\\
Es: 155x≡85 mod 6 ⇔155 mod 6 x≡85 mod 6mod 6\\
155x≡85 mod 6⇔ 5x≡1 mod 6
Added lines 1-67:
(:title Matematica del discreto - Guida agli esercizi 1°Parte:)
[[Torna alla pagina di Matematica del discreto->Uni.MatematicaDelDiscreto]]
----
>>evvai<<
Questa pagina è stata aggiornata GRAZIE agli appunti che AVETE INVIATO nel periodo di chiusura della sezione UniCrema!! '''''È SERVITA A QUALCOSA, NO?!''''' [++;)++]
>><<
%titolo%''':: Matematica del discreto - Guida agli esercizi 1°Parte ::'''
!!!!Algoritmo di Euclide per il calcolo del M.C.D. tra a & b
a=387, b=144
a/b=387/144=2 r=99
b/r=144/99=1 r'_1_'=45
r/r'_1_'=99/45=2 r'_2_'=5
r'_1_'/r'_2_'=45/5=9 r'_3_'=0 quindi M.C.D. (387,144)=9
!!!!Cambio di base per numeri con la virgola
Es: trasformare 7,2'_10_' in base 6.
# trasformo la parte intera: 7'_10_' = 11'_6_'
# 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. Quindi 7,2'_10_'=11,(1)'_6_' . Le parentesi indicano il periodo)-]
# moltiplico per la base: 0,2*6=1,2
è la parte decimale nella nuova base. Quindi 7,2'_10_'=11,(1)'_6_' Le parentesi indicano il
periodo.
Es2: trasformare 347,6'_10_' in base 7.
(:table:)
(:cellnr:)[@
347 | 4
49 | 0
7 | 0
1 | 1
0 |@]
(:cell:)
\\
\\
\\
''''''
(:tableend:)
quindi 347'_10_'=1004'_7_'\\
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)-]
347,6'_10_' = 1004,(4125)'_7_'
!!!!Passaggio da base b a base b'^2^'
abcde'_n_'=[a][bc][de]'_n_''^2^' con [bc]=(b*n)+c & [de]=(d*n)+e
Es: trasformare 1004,(4125)'_7_' in base 7'^2^'\\
[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)
----
[[Torna alla pagina di Matematica del discreto->Uni.MatematicaDelDiscreto]]
|
|
