[Aritmetica modulare]Non riesco a dimostrare una cosa...

[ascatem2]

Giacchè è un argomento che ho anche fatto in algebra e geometria 1, ma per ora durante le lezioni facevo i sudoku (in compenso ho preso 30 nel compitino di analisi 1).... nn è che qualcuno può dimostrarmi o indicarmi la dimostrazione che:

(a1*a2*a3*...*an)%m=(a1%m)*(a2%m)*...*(an%m)

o che, meglio ancora,

(a1*a2*a3*...*an)%m=((a1%m)*(a2%m)*...*(an%m))%m

(a me servirebbe la seconda, a dire il vero)

sto cercando di dimostrarlo per induzione:

quando n=1

a1%m=a1%m verificato

quando n=n la suppongo vera e varrebbe
(a1*a2*a3*...*an)%m=(a1%m)*(a2%m)*...*(an%m)

se n=n+1

(a1*a2*a3*...*an*an+1)%m=(a1%m)*(a2%m)*...*(an%m)* (an+1%m)

non so come riportare questo a un caso con n+1 a quello con n in modo da dimostrare che è vera...

grazie

[fcaldera]

% starebbe per resto della divisione?

[ascatem2]

Originariamente inviato da fcaldera
% starebbe per resto della divisione?

sì, modulo

di per se deve essere una cazzata, ma è un mesetto che algebra non la guardo e il cervello è troppo stanco per ragionare...

[fcaldera]

hai dimostrato che per un n l'equivalenza è vera
supponiamo dunque che sia vera per un generico n e dimostriamo per n+1

ovvero che

(a1*a2*...*an*a(n+1)) % m = (a1%m)*(a2%m)*...*(an%m)*(an+1%m)

poichè per n supponi sia valida puoi riscrivere il termine a destra ovvero

(a1*a2*...*an*a(n+1)) % m = ((a1*a2*...*an) % m) *(an+1 % m)


ecco io avrei provato a questo punto a convicere il docente dell'equivalenza dei due termini, ma mi sa che è troppo semplice...

[tia86]

Prendi n=2 per semplicità

devi dimostrare (a1*a2)%m =? (a1%m) (a2%m)

Hai che




quindi

a1 = a1 % m

ma



quindi

a1 * a2 = (a1*a2) %m

ma



ergo

(a1%m)*(a2%m) = (a1*a2)%m

Ovvero hai dimostrato n=2

La generalizzazione è semplice.

Spero di non aver detto stronzate

[Handlewithcare]

Ma stasera sono partite le selezioni per le olimpiadi di matematica?

[fcaldera]

Originariamente inviato da tia86
Prendi n=2 per semplicità

devi dimostrare (a1*a2)%m =? (a1%m) (a2%m)

Hai che




quindi

a1 = a1 % m

ma



quindi

a1 * a2 = (a1*a2) %m

ma



ergo

(a1%m)*(a2%m) = (a1*a2)%m

Ovvero hai dimostrato n=2

La generalizzazione è semplice.

Spero di non aver detto stronzate

No tia, non funziona così. In questo modo saresti costretto a dimostrare per n=3,4,5,6.... inf

L'induzione funziona perchè dimostri per un certo n (ad esempio n=1) e assumi che sia valida per ipotesi per qualsiasi n. Quindi a partire dall'ipotesi induttiva dimostri che sia valida per n+1 o n-1, ma devi usarla quell'ipotesi...

[tia86]

Originariamente inviato da fcaldera
No tia, non funziona così. In questo modo saresti costretto a dimostrare per n=3,4,5,6.... inf

L'induzione funziona perchè dimostri per un certo n (ad esempio n=1) e assumi che sia valida per ipotesi per qualsiasi n. Quindi a partire dall'ipotesi induttiva dimostri che sia valida per n+1 o n-1, ma devi usarla quell'ipotesi...

Ma infatti non l'ho dimostrato per induzione, quello se lo fa lui.
Ho dato solo l'incipit, poi per generalizzarla basta applicare

e poi

all'n+1 fattore e l'hai dimostrata per induzione.
La dimostrazione per n=2 serve per capire come poi si fa per l'n+1 fattore