Salve! Ultimamente teoria dei numeri è un topic affollato, so godetevi questo:
<BR>
<BR>
<BR>Dimostrare che in modulo p primo dispari
<BR>
<BR>1^(p-2) + 2^(p-2) +...+ ((p-1)/2)^(p-2) == (2-2^p)/p
Congruenze frazionate
Moderatore: tutor
-
publiosulpicio
- Messaggi: 774
- Iscritto il: 01 gen 1970, 01:00
Mi spiace lasciare orfano un così bel problema!
<BR>Con inv(k) indico l\'inverso di k (modulo p),
<BR>con (n k) il coefficiente binomiale (n su k).
<BR>Tutte le uguaglianze sono da prendere come congruenze.
<BR>
<BR>A) 2^t = sum[j=0..t] (t j)
<BR>B) (p k)/p = (-1)^(k+1) inv(k) mod p
<BR>
<BR>Dunque
<BR>
<BR>sum[j=1..(p-1)/2] j^(p-2) = (2-2^p)/p
<BR>
<BR>si può scrivere anche come
<BR>
<BR>sum[j=1..(p-1)/2] inv(j) = 2 sum[j=1..(p-1)/2] (-1)^j inv(j)
<BR>
<BR>ovvero
<BR>
<BR>sum[j=1..(p-1)/2] inv(2j) = sum[j=1..(p-1)/2) (-1)^j inv(j)
<BR>
<BR>adesso basta considerare che -inv(k) = inv(p-k)
<BR>per riscrivere tutti i termini \"dispari\" del membro dx ed
<BR>ottenere, brute force, la tesi. Sayonara!
<BR>
<BR>
<BR>Con inv(k) indico l\'inverso di k (modulo p),
<BR>con (n k) il coefficiente binomiale (n su k).
<BR>Tutte le uguaglianze sono da prendere come congruenze.
<BR>
<BR>A) 2^t = sum[j=0..t] (t j)
<BR>B) (p k)/p = (-1)^(k+1) inv(k) mod p
<BR>
<BR>Dunque
<BR>
<BR>sum[j=1..(p-1)/2] j^(p-2) = (2-2^p)/p
<BR>
<BR>si può scrivere anche come
<BR>
<BR>sum[j=1..(p-1)/2] inv(j) = 2 sum[j=1..(p-1)/2] (-1)^j inv(j)
<BR>
<BR>ovvero
<BR>
<BR>sum[j=1..(p-1)/2] inv(2j) = sum[j=1..(p-1)/2) (-1)^j inv(j)
<BR>
<BR>adesso basta considerare che -inv(k) = inv(p-k)
<BR>per riscrivere tutti i termini \"dispari\" del membro dx ed
<BR>ottenere, brute force, la tesi. Sayonara!
<BR>
<BR>
In questi giorni carnevaleschi, approfittando dell\'intera settimana di vacanza concessami dalla mia scuola, sto riguardando le sol di vecchi giochi. Finalmente ho trovato il tempo di leggere quella di Euler sul problema di Steiner (in versione corretta). Questo esercizio nn mi è mai stato chiaro e sto cercando di capirlo. Perfavore aiutatemi: ho provato per un\'ora e mezza a capire l\'ermetica sol di Jack e nn ci sono riuscito!
<BR>
<BR>Prima di tutto, confermatemi questa definizione:
<BR>
<BR>1)Inverso di k (modulo p) è quel numero che moltiplicato per k dà 1 (modulo p).Cioè:
<BR>k*inv(k)==1 (modulo p)
<BR>
<BR>2) Per trasformare la parte sinistra dell\'uguaglianza è stato applicato fermat?
<BR>Si considera cioè:
<BR> a^(p-1)=1 [mod p] da cui
<BR> a^(p-2)=a^(-1)=inv(a) [mod p]
<BR>
<BR>
<BR>Il passaggio che mi è oscuro è questo (se i punti 1 e 2 sono corretti il resto mi sembra chiaro).
<BR>
<BR> (2-2^p)/p == 2 sum[j=1..(p-1)/2] (-1)^j inv(j)
<BR>
<BR>Cioè, usando i punti (A) e (B) introdotti da Jack all\'inizio della sua soluzione sono in grado di esprimere 2^(p-1) in funzione di una sommatoria con inv(j). Ma quel numero è diverso e nn sono riuscito a raccapezzarmi. Forse utilizzando le serie geometrice 2^(p-1)-1=1+2+2^2+...+2^(p-2) si giunge a qualcosa ma come...
<BR>Se proprio nn volete scrivere i calcoli scrivete perlomeno una descrizione sommaria dei passaggi. Al max chiederò altre conferme.
<BR>
<BR> Thx
<BR>
<BR>ps1: Colgo l\'occasione per augurare buona fortuna a tutti (a chi ne bisogno e chi non) coloro che hanno partecipato alle gare di Febbraio.
<BR>ps2: evviva: è uscito il gionalino numero 11!. Magari stavolta spedirò qualche sol, sempre che trovi il tempo (dell\'ultimo ne avevo risolti un bel pò, pur nn avendo spedito una sol)...
<BR>
<BR><BR><BR>[ Questo Messaggio è stato Modificato da: info il 23-02-2004 19:47 ]
<BR>
<BR>Prima di tutto, confermatemi questa definizione:
<BR>
<BR>1)Inverso di k (modulo p) è quel numero che moltiplicato per k dà 1 (modulo p).Cioè:
<BR>k*inv(k)==1 (modulo p)
<BR>
<BR>2) Per trasformare la parte sinistra dell\'uguaglianza è stato applicato fermat?
<BR>Si considera cioè:
<BR> a^(p-1)=1 [mod p] da cui
<BR> a^(p-2)=a^(-1)=inv(a) [mod p]
<BR>
<BR>
<BR>Il passaggio che mi è oscuro è questo (se i punti 1 e 2 sono corretti il resto mi sembra chiaro).
<BR>
<BR> (2-2^p)/p == 2 sum[j=1..(p-1)/2] (-1)^j inv(j)
<BR>
<BR>Cioè, usando i punti (A) e (B) introdotti da Jack all\'inizio della sua soluzione sono in grado di esprimere 2^(p-1) in funzione di una sommatoria con inv(j). Ma quel numero è diverso e nn sono riuscito a raccapezzarmi. Forse utilizzando le serie geometrice 2^(p-1)-1=1+2+2^2+...+2^(p-2) si giunge a qualcosa ma come...
<BR>Se proprio nn volete scrivere i calcoli scrivete perlomeno una descrizione sommaria dei passaggi. Al max chiederò altre conferme.
<BR>
<BR> Thx
<BR>
<BR>ps1: Colgo l\'occasione per augurare buona fortuna a tutti (a chi ne bisogno e chi non) coloro che hanno partecipato alle gare di Febbraio.
<BR>ps2: evviva: è uscito il gionalino numero 11!. Magari stavolta spedirò qualche sol, sempre che trovi il tempo (dell\'ultimo ne avevo risolti un bel pò, pur nn avendo spedito una sol)...
<BR>
<BR><BR><BR>[ Questo Messaggio è stato Modificato da: info il 23-02-2004 19:47 ]