Aiuto esercizio sulle CONGRUENZE...matematici genialoidi help me :-/

[D4rkAng3l]

Ciao,

vi propongo 2 esercizi che mi stanno creando qualche problemino...non sò se la mia soluzione è corretta...vi prego di aiutarmi perchè manca pochissimo all'esame di matematica discreta e sò che mi bocceranno

PRIMO ESERCIZIO:

In quale classe di Z5 si trova il numero 542872^(324)?

Essendo in Z5 avrò 5 classi di equivalenza (una per ogni resto): [0], [1], [2], [3], [4]

Per cui mi trovo a dover risolvere la seguente congruenza:

542872 % x (mod 5) usando il simbolo % per identificare la relazione di congruenza.

la congruenza può essere risolta in: 542872 % 2 (mod 5) perchè (542872 - 2)\9 dà un valore intero e con resto 0.

Ora scompongo in fattori l'esponente 324

324 = 4*81

Per cui:
542872^(324) % 2^324 ne segue che
542872^(324) % 2^(4^81) da cui segue che
542872^(324) % (2^4)^81

Ora mi chiedo in che classe casa 2^4 e per capirlo studio i seguenti casi:

2^0 = 1 e cade nella classe [1]
2^1 = 2 e cade nella classe [2]
2^2 = 4 e cade nella classe [4]
2^3 = 8 e cade nella classe [3]
2^4 = 16 e cade nella classe [1]

Per cui 542872^(324) % ([1])^81 ma ([1])^81 = [1] per cui:
542872^(324) % [1]

questo va bene così? come ragionamento fila?

SECONDO ESERCIZIO:
è simile ma ne sono ancora meno sicuro del primo perchè ho fatto dei giochetti con gli esponenti e non sò se è un po' una porcata quello che ho fatto...

In quale classe modulo 9 cade il numero 34572^(457) ?

Per prima cosa risolvo la seguente congruenza: 34572 % x (mod 9)
quindi: 34572 % 3 (mod 9) perchè (34572 - 3)\9 è un intero con resto 0

Ora provo a scomporre l'esponente 457....non è divisibile per nulla (vuol dire che è primo in Z giusto?)...faccio una porcata e decivo di scrivermi 457 come 456 + 1 quindi:

457 = 456 + 1

Scompongo ora 456 e quindi 456 = 57 * 2^3

Allora ho la seguente congruenza:

34572^(457) % 3^(457) che posso anche scrivere come:
34572^(457) % 3^(456 + 1) che posso quindi riscrivere come:
34572^(457) % (3^(456)) * 3 che posso ulteriormente riscrivere come:
34572^(457) % (3^(57*8)) *3 e ancora:
34572^(457) % ((3^8)^57) *3

Vado ora a studiare in che classe cade 3^8 per cui:

3^0 = 1 quindi cade nella classe [1]
3^1 = 3 quindi cade nella classe [3]
3^2 = 9 quindi cade nella classe [0]
3^3 = (3^2)*3 = [0] * 3 quindi cade nella classe [0]
3^4 = (3^3)*3 = [0] * 3 quindi cade nella classe [0]
....così via fino a 3^8 perchè moltiplicare la classe 0 ogni volta per 3 vuol dire moltiplicare un multiplo di 9 per 3....quindi sempre multiplo di 9 rimane...quindi per finire

3^8 quindi cade nella classe [0]

quindi ho che

34572^(457) % ((3^8)^57) *3
allora 34572^(457) % (([0])^57) * 3
e allora: 34572^(457) % 1*3
34572^(457) % 3

mmm dite che va bene? Scusate se sono stato eccessivamente prolisso ma visto che il forum non supporta i caratteri matematici ho pensato che includere tutti i passaggi potesse rendere più chiaro il tutto

Grazie mille
Andrea

[Ziosilvio]

Il risultato del primo è corretto; quello del secondo no.
Il buffo è che il tuo ragionamento parte bene, arriva al sodo, dopodiché fa una conclusione sbagliata.
(Per inciso: in un primo momento ha fregato anche me. Cosa vuol dire fare esercizi alle dieci e mezza di sera... )

I ragionamenti si potevano snellire ricordando un paio di cose.
La prima è che, per via della formula del binomio di Newton, (qm+r)^k = r^k (mod m) qualunque siano k ed m.
La seconda è che per ogni gruppo finito G e ogni a in G si ha a^|G| = 1, dove |G| è il numero di elementi di G e 1 è l'identità di G.

Per cui:

Il primo esercizio chiede di trovare 542872^324 (mod 5).
Dato che 542872 = 5*108574 + 2, questo è lo stesso che trovare 2^324 (mod 5).
Ma 324=4*81, e U5, il gruppo moltiplicativo degli interi tra 0 e 5 primi con 5, ha quattro elementi.
Quindi 2^324 = (2^|U5|)^81 = 1^81 = 1 (mod 5).

Il secondo esercizio chiede di trovare 34572^457 (mod 9).
Dato che 34572 = 9*3841 + 3, questo è lo stesso che trovare 3^457 (mod 9).
Ma qualunque potenza non banale di 3 è divisibile per 9: quindi: 34572^457 = 0 (mod 9).

[D4rkAng3l]

Grazie per l'aiuto anche se quel secondo ragionamento sui gruppi che ha fatto Zio Silvio non ho la minima idea di cosa sia visto che mi pare non sia stato trattato nel programma :-/

Per te qualche punticino me lo avrebbero potuto dare se lo avessi fatto così all'esame o ci sarebbe stata una bella croce sopra e 0 punti all'esercizio?

Grazie
Andrea

[Ziosilvio]

Originariamente inviato da D4rkAng3l

Grazie per l'aiuto

Di niente

anche se quel secondo ragionamento sui gruppi che ha fatto Zio Silvio non ho la minima idea di cosa sia visto che mi pare non sia stato trattato nel programma

Quel secondo ragionamento è una generalizzazione a gruppi finiti arbitrari del teorema di Eulero, che ti ha enunciato Morkar Karamat.

Per te qualche punticino me lo avrebbero potuto dare se lo avessi fatto così all'esame o ci sarebbe stata una bella croce sopra e 0 punti all'esercizio?

Non saprei dire con certezza, ma secondo me sarebbero stati clementi.