Se qualcuno è interessato a sviluppare il topic, lo faccia sapere.
<BR>Ecco un imput iniziale.
<BR>Abbiamo detto cos\'è un generatore. Avvalendoci dei simpatici teoremi in cui esso è protagonista (o anche in altro modo, chi lo vieta), dimostrare che
<BR>1^k + 2^k + ... + (p-1)^k, con k non multiplo di p-1, è divisibile per p.
Teoria dei numeri - olimpionacamente advanced
Moderatore: tutor
oilà...
<BR>immagino p primo, comunque:
<BR>innanzitutto p>2, altrimenti non esisterebbe nessun k non multiplo di 1...dunque p-1 pari
<BR>1) se k dispari basta raccogliere 1^k con (p-1)^k,2^k con (p-2)^k etc etc,tutti i termini verranno quindi divisibili per p.
<BR>2)se k è pari e non multiplo di p-1 la faccenda è complicata...boh!mi sa che è meglio che vada a studiare kant.
<BR>ciao ciao
<BR>
<BR>
<BR>immagino p primo, comunque:
<BR>innanzitutto p>2, altrimenti non esisterebbe nessun k non multiplo di 1...dunque p-1 pari
<BR>1) se k dispari basta raccogliere 1^k con (p-1)^k,2^k con (p-2)^k etc etc,tutti i termini verranno quindi divisibili per p.
<BR>2)se k è pari e non multiplo di p-1 la faccenda è complicata...boh!mi sa che è meglio che vada a studiare kant.
<BR>ciao ciao
<BR>
<BR>
-
psion_metacreativo
- Messaggi: 645
- Iscritto il: 01 gen 1970, 01:00
Innanzitutto se p = 2 è falso.
<BR>
<BR>Altrimenti esiste un generatore > 1, che chiamiamo g.
<BR>
<BR>Allora
<BR>sum(1 <= i <= (p - 1)) {i^k} =
<BR>= sum(0 <= i < (p - 1)) {(g^i)^k} =
<BR>= sum(0 <= i < (p - 1)) {(g^k)^i} =
<BR>= ((g^k)^(p - 1) - 1)/(g ^k- 1) = *
<BR>= ((g^k)^(p - 1) - 1) =
<BR>= 1 - 1 =
<BR>= 0 (p)
<BR>
<BR>* se g^k = 1, allora k = 0 (p - 1) contro l\'ipotesi
<BR><BR><BR>[ Questo Messaggio è stato Modificato da: LB il 17-09-2003 18:24 ]
<BR>
<BR>Altrimenti esiste un generatore > 1, che chiamiamo g.
<BR>
<BR>Allora
<BR>sum(1 <= i <= (p - 1)) {i^k} =
<BR>= sum(0 <= i < (p - 1)) {(g^i)^k} =
<BR>= sum(0 <= i < (p - 1)) {(g^k)^i} =
<BR>= ((g^k)^(p - 1) - 1)/(g ^k- 1) = *
<BR>= ((g^k)^(p - 1) - 1) =
<BR>= 1 - 1 =
<BR>= 0 (p)
<BR>
<BR>* se g^k = 1, allora k = 0 (p - 1) contro l\'ipotesi
<BR><BR><BR>[ Questo Messaggio è stato Modificato da: LB il 17-09-2003 18:24 ]
ogni numero a compreso tra 1 e p-1 ha un inverso nello stesso intervallo (cioè un numero b tale ab==1 mod p)
<BR>eccettuati quindi quei numeri per cui a^2==1 ==> a==+1 o a==-1 che sono 1 e p-1, tutti gli altri si possono accoppiare in modo che il prodotto di ogni coppia sia ==1 mod p
<BR>quindi 1*2*3*...*(p-2)==1 mod p
<BR>moltiplicando per p-1 (che è ==-1 mod p) si ha la tesi
<BR>eccettuati quindi quei numeri per cui a^2==1 ==> a==+1 o a==-1 che sono 1 e p-1, tutti gli altri si possono accoppiare in modo che il prodotto di ogni coppia sia ==1 mod p
<BR>quindi 1*2*3*...*(p-2)==1 mod p
<BR>moltiplicando per p-1 (che è ==-1 mod p) si ha la tesi
[img:18oeoalk]http://www.narutolegend.it/char_img/Sasuke.jpg[/img:18oeoalk]
gia, funziona anche con gli inversi...
<BR>ecco come ho fatto io:
<BR>se p è primo allora esiste un generatore g tale che per i che va da 1 a p-1, g^i assume tutti i valori di congruenza mod(p) tra 1 e p-1 allora p!==g^1g^2g^3....g^(p-1)==g^(p(p-1)/2) mod(p) da cui si ricava che p(p-1)/2==(p-1)/2 mod(p-1) allora g^(p(p-1)/2)==g^((p-1)/2)==-1 mod p
<BR>ecco come ho fatto io:
<BR>se p è primo allora esiste un generatore g tale che per i che va da 1 a p-1, g^i assume tutti i valori di congruenza mod(p) tra 1 e p-1 allora p!==g^1g^2g^3....g^(p-1)==g^(p(p-1)/2) mod(p) da cui si ricava che p(p-1)/2==(p-1)/2 mod(p-1) allora g^(p(p-1)/2)==g^((p-1)/2)==-1 mod p