I problemi... si affrontano alla radice!

Vuoi proporre i tuoi esercizi? Qui puoi farlo!!

Moderatore: tutor

Bloccato
euler_25
Messaggi: 428
Iscritto il: 01 gen 1970, 01:00
Località: mooolto vicino...

Messaggio da euler_25 »

<!-- BBCode Start --><B>Problema i)</B><!-- BBCode End -->: essendo a,b€N tali che min{a,b} > 1, definiamo numero di Frobenius associato ad a e b l\'intero naturale f(a,b) := ab - (a+b). Supposto
<BR>D(a,b) = 1, si dimostri allora che l\'equazione diofantina in due indeterminate:
<BR>ax + by = c è sempre risolvibile in interi non negativi, ossia per x,y € N, quando c > f(a,b). Si provi inoltre che esistono <!-- BBCode Start --><I>esattamente</I><!-- BBCode End --> [f(a,b)+1]/2 ulteriori valori interi del parametro c, tali che 0 ≤ c ≤ f(a,b), per i quali l\'equazione: ax+by = c risulta interamente risolvibile in N.
<BR>
<BR><!-- BBCode Start --><B>Problema ii)</B><!-- BBCode End -->: essendo p un numero primo > 2 ed n un intero arbitrario > 0, determinare il resto della divisione intera per p della seguente sommatoria:
<BR>
<BR><center>S(n, p) := sum[k=1...p-1] k<sup>n</sup> = 1 + 2<sup>n</sup> + ... + (p-1)<sup>n</sup></center>
<BR>
<BR><!-- BBCode Start --><B>Problema iii)</B><!-- BBCode End -->: dimostrare che comunque scelto un n intero > 1 e per ogni a,b,c,d € Z tali che <!-- BBCode Start --><B>a e c</B><!-- BBCode End --> siano primi fra loro, esiste almeno un x€Z tale che:
<BR>
<BR><center>(ax + b)*(cx + d) ≡ 0 (mod n)</center>
<BR>
<BR>EDIT: errata corrige!!! <IMG SRC="images/forum/icons/icon_wink.gif"> <BR><BR>[ Questo Messaggio è stato Modificato da: euler_25 il 21-02-2004 21:47 ]
<center>Le cose cambiano... e i sentimenti pure...</center>
LB
Messaggi: 72
Iscritto il: 01 gen 1970, 01:00
Località: Milano

Messaggio da LB »

<!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR><!-- BBCode Start --><B>Problema iii)</B><!-- BBCode End -->: dimostrare che comunque scelto un n intero > 1 e per ogni a,b,c,d € Z tali che a e b siano primi fra loro, esiste almeno un x€Z tale che:
<BR>
<BR><center>(ax + b)*(cx + d) ≡ 0 (mod n)</center>
<BR>
<BR>[ Questo Messaggio è stato Modificato da: euler_25 il 21-02-2004 21:23 ]
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>
<BR>Falso.
<BR>Si prenda ad esempio n > 1, a = n, b = 1, c = n, d = 1.
<BR>
euler_25
Messaggi: 428
Iscritto il: 01 gen 1970, 01:00
Località: mooolto vicino...

Messaggio da euler_25 »

Uhm... sì, c\'è un errore nella traccia, in effetti! Ma certo che sei una roba, te! In ogni caso, quando ci hai ragione ci hai ragione, per cui... <IMG SRC="images/forum/icons/icon_cool.gif">
<BR>
<BR>P.S.: provvedo subito alla correzione... grazie!!! <IMG SRC="images/forum/icons/icon_razz.gif">
<center>Le cose cambiano... e i sentimenti pure...</center>
Avatar utente
karl
Messaggi: 926
Iscritto il: 01 gen 1970, 01:00

Messaggio da karl »

Problema (ii)
<BR>La somma 1^(n)+....+(p-1)^n si puo\' esprimere con un polinomio
<BR>di grado (n+1) in (p-1) che e\':
<BR>1/(n+1)[(p-1)^(n+1)+(Cn+1,1)*B1*(p-1)^(n)+(Cn+1,2)*B2*(p-1)^(n-1)+
<BR>+......+(Cn+1,n)*Bn*(p-1)]
<BR>dove le C sono gli ordinari coefficienti binomiali e le B i numeri di Bernoulli.
<BR>Per avere il resto bastera\' porre in questo polinomio p=0.
<BR>Da qualche prova che ho fatto mi pare che questo resto sia zero,in quanto
<BR>il polinomio in questione presenta sempre un fattore =p.Inoltre sembrerebbe
<BR>che la natura di p non incida piu di tanto sul resto.
<BR>Spero di non aver detto troppe cretinerie.
<BR>
ma_go
Site Admin
Messaggi: 1906
Iscritto il: 01 gen 1970, 01:00

Messaggio da ma_go »

allora...
<BR>premessa, intendo dimostrare che il resto è 0.
<BR>
<BR>diamo per dimostrato che l\'espressione di S<sub>n</sub>(m) sia un polinomio P(m) di (n+1)-esimo grado...
<BR>ora, P(0) = 0, quindi m|P(m). inoltre P(m+1) = P(m) + (m+1)<sup>n</sup>, e dunque [avendo che (m+1)|P(m+1)], (m+1)|P(m).
<BR>ma allora P(m) = m(m+1)Q(m), dove m ha grado n-1...
<BR>per determinare q sono quindi sufficienti n informazioni, ovvero n valori di P(m), a partire da 1.
<BR>
<BR>[aperta parentesi]
<BR>sia q il rappresentante privilegiato di n modulo p-1, dove 0<= q < p-2. allora si ha che S<sub>n</sub>(m) == S<sub>q</sub>(m) (mod p), per il piccolo teorema di fermat, quindi è sufficiente calcolare i resti per i vari q, non per tutti gli n...
<BR>[chiusa parentesi]
<BR>
<BR>ora... in maniera molto brutale, prendiamo un generico polinomio di (q-1)-esimo grado, e mettiamo a sistema i valori ottenuti sostituendo alla variabile ciò che noi vogliamo (in questo caso i primi q numeri positivi), eguagliati al rispettivo S<sub>q</sub>(i) (la chiarezza non è il mio forte, in questo punto).
<BR>brutalmente, calcoliamo il determinante, e osserviamo che non è mai divisibile per p (ora, non chiedetemi il perché, ma è così!).
<BR>quindi nessuno dei denominatori dei coefficienti (che sono razionali) ha come fattore p, quindi Q<sub>q</sub>(p-1) = a/b, dove p non divide b...
<BR>ma allora, la tesi si ottiene facilmente...
<BR>scusate l\'estrema ineleganza della cosa...
LB
Messaggi: 72
Iscritto il: 01 gen 1970, 01:00
Località: Milano

Messaggio da LB »

Ecco una soluzione molto piu\' semplice.
<BR>Essendo p primo > 2, esiste un generatore che chiamiamo g; vale inoltre g != 1.
<BR>
<BR>Dunque
<BR>sum(k = 1 -> p - 1) k^n = sum(k = 0 -> p - 2) (g^k)^n = sum(k = 0 -> p - 2) (g^n)^k (mod p)
<BR>
<BR>Se g^n != 1 <=> n != 0 (mod phi(p) = p - 1):
<BR>sum(k = 0 -> p - 2) (g^n)^k = ((g^n)^(p - 1) - 1)/(g^n - 1)
<BR>
<BR>((g^n)^(p - 1) - 1)/(g^n - 1) = ((g^(p - 1))^n - 1)/(g^n - 1) = (1 - 1)/(g^n - 1) = 0 (mod p)
<BR>
<BR>
<BR>Altrimenti, se g^n = 1:
<BR>sum(k = 0 -> p - 2) (g^n)^k = sum(k = 0 -> p - 2) 1^k = p - 1
<BR>p - 1 = -1 (mod p)
<BR>
<BR>
<BR>EDIT: avevo erroneamente scritto \"g - 1\" al denominatore anziche\' \"g^n - 1\", cosa che, come indicato da Lordgauss, portava ad ignorare il caso di resto -1.
<BR><BR><BR>[ Questo Messaggio è stato Modificato da: LB il 22-02-2004 01:01 ]
lordgauss
Messaggi: 478
Iscritto il: 01 gen 1970, 01:00
Località: Brunswick

Messaggio da lordgauss »

p è primo, pertanto esiste almeno un generatore g.
<BR>
<BR>Allora 1^n + 2^n + ... + (p-1)^n == sumg^(i*n) =
<BR>= (g^((p-1)n)-1)/(g^n-1).
<BR>
<BR>Quindi per n non multiplo di p-1 la somma è nulla mod p.
<BR>Per n multiplo di p-1 tale somma è invece congrua a -1.
lordgauss
Messaggi: 478
Iscritto il: 01 gen 1970, 01:00
Località: Brunswick

Messaggio da lordgauss »

Ecco, luca mi ha battuto sul tempo, però le annotazioni che ho fatto valgono. La somma non è sempre nulla.
Bloccato