Altro problema interessante in aritmetica intera (non so però come classificarlo!)
anonimo
dove x1..xn d1..dn,l sono tutte variabili intere positive tali che
MCD(d1..dn) divide l cos� ad intuito mi verrebbe da dire che il risultato di
quell'espressione sia multiplo di MCD(d1..dn) ovvero esprimibile nella forma
k*MCD(d1..dn) con k intero positivo, ora quello che voglio sapere �: al
variare di x1..xn come si fa a sapere se quel k pu� assumere tutti i valori
tali che 0<=k*MCD(d1..dn)<l oppure ne pu� assumere solo alcuni e quali senza
per� provare tutte le INFINITE combinazioni delle variabili x1..xn ? Va da
s� che anche questo problemino bench� ostico ha delle applicazioni molto
interessanti, lascio a voi il diletto di trovare anche applicazioni in campo
monetario!! :-)
Tetis
> Supponiamo di dover calcolare la seguente espressione: (x1*d1+..xn*dn)mod(l)
> dove x1..xn d1..dn,l sono tutte variabili intere positive tali che
> quell'espressione sia multiplo di MCD(d1..dn) ovvero esprimibile nella forma
> k*MCD(d1..dn) con k intero positivo,
è vero, infatti basta scrivere la definizione di congruenza
esplicitando l'ipotesi che esista questo fattore comune a tutti i d e
ad m.
ora quello che voglio sapere è: al
> variare di x1..xn come si fa a sapere se quel k può assumere tutti i valori
> tali che 0<=k*MCD(d1..dn)<l oppure ne può assumere solo alcuni e quali senza
> però provare tutte le INFINITE combinazioni delle variabili x1..xn ? Va da
> sè che anche questo problemino benchè ostico ha delle applicazioni molto
> interessanti, lascio a voi il diletto di trovare anche applicazioni in campo
> monetario!! :-)
Si comincia da un problema più semplice:
x1 d1 mod(m)
nel caso che MCD(d1,m) = 1 assume tutti i valori da 0 ad m-1. Di
conseguenza è facile dimostrare che nel caso MCD(d1,m)=e1
l'espressione x1 d1 mod(m) assume gli stessi valori di x1 e1 mod(m).
E' ancora semplice dimostrare che:
x1 d1 + x2 d2 mod(m)
quando d1 e d2 non hanno fattori comuni assume tutti i valori da 0 ad
m-1 e quindi se hanno il fattore comune e_12 assume tutti e soli i
valori di y1 e_12 mod(m), dove in particolare risulta che x1 e_12 d1'
+ x2 e_12 d2' mod(m) = (x1 d1' + x2 d2')e_12 mod(m) e quindi è
possibile l'identificazione (x1 d1' + x2 d2') = y1 mod(m) (dimostrarlo
è semplice esercizio di base).
Di conseguenza procedendo ad aggiungere una terza variabile e poi
un'altra etc... si giunge a dire che l'equazione:
(x1*d1+..xn*dn)mod(m)
assume tutti e soli i valori di:
y1 M.C.D.(d1,...,dn) mod(m)
Dove y1 assume tutti i valori nell'intervallo 0,(m-1). In conclusione
la risposta alla tua domanda è: quel k può assumer tutti i valori tali
che:
0<=k*MCD(d1..dn)<l
Poiché il punto chiave è la seconda affermazione soffermiamoci un
attimo su una sua dimostrazione:
se d1 o d2 è primo con m non c'è quasi nulla da dimostrare infatti x1
d1 mod(m) assume tutti i valori da 0 ad m-1 e l'aggiunta di un numero
qualsiasi non fa che traslare il sistema di resti.
se d1 è un divisore proprio (diverso da uno) di m (caso a cui
possiamo sempre ricondurci riconsiderando in luogo del d1 originario
il fattor comune fra d1 ed m) allora risulta che i resti distinti
sono m/d1 separati da intervalli di d1. E lo stesso vale,
simmetricamente per d2 che possiamo sostituire con l'eventuale fattor
comune con m, che genera quindi un sistema di m/d2 resti distinti
(0,d2,2d2,...). Ma se consideriamo x1 d1 + d2 mod(m) otteniamo ancora
un sistema di resti con la stessa cardinalità dei resti di x1 d1, ma
distinto, infatti in caso contrario d2 sarebbe un resto di x1 d1 e
risulterebbe divisibile per d1 (basta scrivere la definizione di
congruenza) mentre per ipotesi d1 e d2 sono coprimi, allo stesso modo
x1 d1 + 2 d2 mod(m) sono resti distinti da entrambi gli insiemi a meno
che 2d2 non sia già un resto di x1 d1 mod(m) nel qual caso è 2 = d1
oppure
d2 è un resto di x1 d1 che abbiamo dimostrato essere impossibile
etc... quindi in conclusione otteniamo esattamente
m/d1 * d1 = m resti distinti.
anonimo
"Tetis" <lje...@yahoo.it> ha scritto nel messaggio
news:5cb2304a-3005-49b6...@u7g2000yqm.googlegroups.com...
On 4 Gen, 17:02, "anonimo" <anon...@anonimo.it> wrote:
>> Supponiamo di dover calcolare la seguente espressione:
>> (x1*d1+..xn*dn)mod(l)
>> dove x1..xn d1..dn,l sono tutte variabili intere positive tali che
>> quell'espressione sia multiplo di MCD(d1..dn) ovvero esprimibile nella
>> forma
>> k*MCD(d1..dn) con k intero positivo,
>� vero, infatti basta scrivere la definizione di congruenza
>esplicitando l'ipotesi che esista questo fattore comune a tutti i d e
>ad m.
>> ora quello che voglio sapere �: al
>> variare di x1..xn come si fa a sapere se quel k pu� assumere tutti i
>> valori
>> tali che 0<=k*MCD(d1..dn)<l oppure ne pu� assumere solo alcuni e quali
>> senza
>> per� provare tutte le INFINITE combinazioni delle variabili x1..xn ? Va
>> da
>> s� che anche questo problemino bench� ostico ha delle applicazioni molto
>> interessanti, lascio a voi il diletto di trovare anche applicazioni in
>> campo
>> monetario!! :-)
>Si comincia da un problema pi� semplice:
>x1 d1 mod(m)
>nel caso che MCD(d1,m) = 1 assume tutti i valori da 0 ad m-1. Di
>conseguenza � facile dimostrare che nel caso MCD(d1,m)=e1
>l'espressione x1 d1 mod(m) assume gli stessi valori di x1 e1 mod(m).
>E' ancora semplice dimostrare che:
>x1 d1 + x2 d2 mod(m)
>quando d1 e d2 non hanno fattori comuni assume tutti i valori da 0 ad
>m-1 e quindi se hanno il fattore comune e_12 assume tutti e soli i
>valori di y1 e_12 mod(m), dove in particolare risulta che x1 e_12 d1'
>+ x2 e_12 d2' mod(m) = (x1 d1' + x2 d2')e_12 mod(m) e quindi �
>possibile l'identificazione (x1 d1' + x2 d2') = y1 mod(m) (dimostrarlo
>� semplice esercizio di base).
>Di conseguenza procedendo ad aggiungere una terza variabile e poi
>un'altra etc... si giunge a dire che l'equazione:
>(x1*d1+..xn*dn)mod(m)
>assume tutti e soli i valori di:
>y1 M.C.D.(d1,...,dn) mod(m)
>Dove y1 assume tutti i valori nell'intervallo 0,(m-1). In conclusione
>la risposta alla tua domanda �: quel k pu� assumer tutti i valori tali
>che:
>0<=k*MCD(d1..dn)<l
>Poich� il punto chiave � la seconda affermazione soffermiamoci un
>attimo su una sua dimostrazione:
>se d1 o d2 � primo con m non c'� quasi nulla da dimostrare infatti x1
>d1 mod(m) assume tutti i valori da 0 ad m-1 e l'aggiunta di un numero
>qualsiasi non fa che traslare il sistema di resti.
>se d1 � un divisore proprio (diverso da uno) di m (caso a cui
>possiamo sempre ricondurci riconsiderando in luogo del d1 originario
>il fattor comune fra d1 ed m) allora risulta che i resti distinti
>sono m/d1 separati da intervalli di d1. E lo stesso vale,
>simmetricamente per d2 che possiamo sostituire con l'eventuale fattor
>comune con m, che genera quindi un sistema di m/d2 resti distinti
>(0,d2,2d2,...). Ma se consideriamo x1 d1 + d2 mod(m) otteniamo ancora
>un sistema di resti con la stessa cardinalit� dei resti di x1 d1, ma
>distinto, infatti in caso contrario d2 sarebbe un resto di x1 d1 e
>risulterebbe divisibile per d1 (basta scrivere la definizione di
>congruenza) mentre per ipotesi d1 e d2 sono coprimi, allo stesso modo
>x1 d1 + 2 d2 mod(m) sono resti distinti da entrambi gli insiemi a meno
>che 2d2 non sia gi� un resto di x1 d1 mod(m) nel qual caso � 2 = d1
>oppure
>d2 � un resto di x1 d1 che abbiamo dimostrato essere impossibile
>etc... quindi in conclusione otteniamo esattamente
>m/d1 * d1 = m resti distinti.
grazie mille!! Sei un geniaccio anche tu :-))))