congruenze modulo p

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
mens
Messaggi: 12
Iscritto il: 16 set 2008, 16:01

congruenze modulo p

Messaggio da mens » 16 set 2008, 16:21

Due esercizi su primi e congruenze:

1. Sia $ p $ primo, $ p\equiv1(mod4) $. Far vedere che $ z = (\frac{p-1}{2})! $ soddisfa $ z^2\equiv-1(modp) $

2. Per ogni intero $ n >= 0 $ calcolare $ 1^n + 2^n + ... + (p-1)^n (modp) $

PS Spero di aver usato bene il TeX, scusate ma è la prima volta che lo uso :)

String
Messaggi: 225
Iscritto il: 01 giu 2008, 17:21

Messaggio da String » 16 set 2008, 19:24

1) Credo che si dimostri con il teorema di Wilson. Infatti $ $ \left(\frac {p-1}{2}\right)!^2 $ si può anche scrivere come $ (p-1)\cdot (p-2)\cdots 2\cdot 1 $ dato che $ p-1 $ è divisibile per 4. Ma il teorema di Wilson ci dice che questo prodotto è $ \equiv -1\pmod p $
2) Se n è dispari allora tutti i residui mod p si annullano e quindi quella somma è $ \equiv 0\pmod p $. Se invece n è pari dovrebbe essere sempre $ \equiv 0\pmod p $ ma non so come dimostrarlo...
"fatti non foste a viver come bruti,
ma per seguir virtute e canoscenza"(Dante)

Rigel
Messaggi: 74
Iscritto il: 19 mag 2008, 17:33
Località: Sternatia

Messaggio da Rigel » 16 set 2008, 21:04

Mah, il secondo punto viene molto bene coi generatori. abbiamo che $ 1,..., p-1 $ sono congrui a $ g,..., g^{p-1} $ (non importa l'ordine), dove g è un generatore.
Quindi $ 1^n+...+(p-1)^n\equiv g^n+...+g^{n(p-1)}\equiv $
$ $g^n(1+...+g^{n(p-2)})\equiv g^n\frac{g^{n(p-1)}-1}{g^n-1}\quad \pmod p$ $
Per il piccolo teorema di Fermat $ g^{n(p-1)}-1\equiv 1^n-1\equiv 0 \pmod p $. ora però dobbiamo assicurarci che il denominatore non sia multiplo di p, ciò avviene se $ g^n-1\equiv 0 \pmod p $, cioè se $ p-1|n $, ovvero se $ 4|n $. in questo caso $ g^n\equiv 1 \pmod p $ e quindi $ 1^n+...+(p-1)^n\equiv 1+...+1\equiv p-1 \pmod p $
Ultima modifica di Rigel il 18 set 2008, 20:35, modificato 1 volta in totale.
"Non ho particolari talenti, sono solo appassionatamente curioso." Albert Einstein

mens
Messaggi: 12
Iscritto il: 16 set 2008, 16:01

Messaggio da mens » 17 set 2008, 00:04

String ha scritto:Infatti $ $ \left(\frac {p-1}{2}\right)!^2 $ si può anche scrivere come $ (p-1)\cdot (p-2)\cdots 2\cdot 1 $ dato che $ p-1 $ è divisibile per 4.
Scusa ma se per esempio prendi $ p=5 $ quel fattoriale non è uguale alla produttoria che hai scritto...
La realtà è solo una teoria. [i]John Wheeler[/i]

mens
Messaggi: 12
Iscritto il: 16 set 2008, 16:01

Messaggio da mens » 17 set 2008, 00:07

Rigel ha scritto:ora però dobbiamo assicurarci che il denominatore non sia multiplo di p, ciò avviene se $ g^n-1\equiv 0 \pmod p $, cioè se $ p-1|n $, ovvero se $ 4|n $. in questo caso $ g^k\equiv 1 \pmod p\quad\forall k $
Scusa ma non ho capito questa parte...:(
La realtà è solo una teoria. [i]John Wheeler[/i]

String
Messaggi: 225
Iscritto il: 01 giu 2008, 17:21

Messaggio da String » 17 set 2008, 13:32

mens ha scritto:
String ha scritto:Infatti $ $ \left(\frac {p-1}{2}\right)!^2 $ si può anche scrivere come $ (p-1)\cdot (p-2)\cdots 2\cdot 1 $ dato che $ p-1 $ è divisibile per 4.
Scusa ma se per esempio prendi $ p=5 $ quel fattoriale non è uguale alla produttoria che hai scritto...
Beh, stavo ragionando con le congruenze...intendevo dire che $ $ \left(\frac {p-1}{2}\right)!^2\equiv (p-1)\cdot (p-2)\cdots 2\cdot 1\pmod p $. Quindi se prendi 5 $ $ \left(\frac {p-1}{2}\right)!^2=4 $ che ovviamente è $ \equiv 4\pmod 5 $. Ma anche $ 4\cdot 3\cdot 2\cdot 1\equiv 4\pmod 5 $.
"fatti non foste a viver come bruti,
ma per seguir virtute e canoscenza"(Dante)

mens
Messaggi: 12
Iscritto il: 16 set 2008, 16:01

Messaggio da mens » 17 set 2008, 14:51

Ora ho capito e in effetti funziona. Ma da dove fai saltare fuori quell'uguaglianza in modulo?
La realtà è solo una teoria. [i]John Wheeler[/i]

String
Messaggi: 225
Iscritto il: 01 giu 2008, 17:21

Messaggio da String » 17 set 2008, 17:42

$ p-1 $ è pari. Quindi metà delle classi di resto modulo p sono $ [1]_p,[2]_p...\left[ \displaystyle \frac {p-1}{2}\right]_p $, mentre l'altra metà $ \left[ -\displaystyle \frac {p-1}{2}\right]_p ,...,[-2]_p,[-1]_p $. Essendo inoltre $ p-1 $ divisibile per quattro, entrambe le metà delle classi di resto sono in numero pari, perciò il prodotto fra le classi di resto negative è positivo. Quindi, moltiplicando fra loro tutte le classi di resto, è come se si moltiplicassero due volte fra loro le classi di resto positive, quindi $ $ \left( \frac {p-1}{2}\right)!^2\equiv 1\cdot 2\cdots (p-2)\cdot (p-1) $
Non so se sono stato abbastanza chiaro :roll:
"fatti non foste a viver come bruti,
ma per seguir virtute e canoscenza"(Dante)

mens
Messaggi: 12
Iscritto il: 16 set 2008, 16:01

Messaggio da mens » 18 set 2008, 11:04

Ora è tutto chiaro. Grazie mille per la spiegazione.
La realtà è solo una teoria. [i]John Wheeler[/i]

Rigel
Messaggi: 74
Iscritto il: 19 mag 2008, 17:33
Località: Sternatia

Messaggio da Rigel » 18 set 2008, 20:41

mens ha scritto:
Rigel ha scritto:ora però dobbiamo assicurarci che il denominatore non sia multiplo di p, ciò avviene se $ g^n-1\equiv 0 \pmod p $, cioè se $ p-1|n $, ovvero se $ 4|n $. in questo caso $ g^k\equiv 1 \pmod p\quad\forall k $
Scusa ma non ho capito questa parte...:(
In effetti quella cosa col k è tremendamente sbagliata e l'ho subito cancellata per la vergogna. :oops:
Comunque, una volta dimostrato che il numeratore è multiplio di p bisogna vedere quando lo è anche il denominatore (infatti se sia numeratore che denominatore sono multipli di p, la frazione potrebbe non esserlo). Quindi si verifica che quando $ 4|n $ la somma iniziale è congrua a $ -1 \pmod p $, mentre se 4 non divide n, allora il tutto è divisibile per p.
Spero di essere stato chiaro (almeno questa volta :) )
"Non ho particolari talenti, sono solo appassionatamente curioso." Albert Einstein

mens
Messaggi: 12
Iscritto il: 16 set 2008, 16:01

Messaggio da mens » 19 set 2008, 14:15

Chiarissimo, grazie!
La realtà è solo una teoria. [i]John Wheeler[/i]

Rispondi