Somme simmetriche e congruenze modulo p

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
Avatar utente
Anér
Messaggi: 720
Iscritto il: 03 giu 2008, 21:16
Località: Sabaudia

Somme simmetriche e congruenze modulo p

Messaggio da Anér » 26 giu 2009, 12:02

Penso sia un lemma già famoso perciò, come ho già detto una volta, scrivete la soluzione solo se non sapete risolvere il problema.

Data una $ n $-upla $ (a_1; \cdots ; a_n) $, e un intero $ 1\leq k\leq n $, definiamo (come fa il Gobbino a pag. 25 delle Schede Olimpiche)

$ \[c_k=\sum_{1\leq i_1<\cdots<i_k\leq n} \prod_{j=1}^{k} a_{i_j}\] $, ovvero $ c_k $ è la somma di tutti i possibili prodotti di $ k $ fattori scelti tra $ a_1, \cdots , a_n $.

Sia ora $ p $ un primo e prendiamo la $ (p-1) $-upla (che bel neologismo!) $ (1; \cdots ; p-1) $; dimostrare che:

1) $ c_{p-1}=(p-1)!\equiv -1 \pmod{p} $ , noto anche come teorema di Wilson;

2) $ c_k\equiv 0 \pmod{p} \qquad \forall 1\leq k <p-1 $

BQ: se al posto di $ p $ primo prendiamo $ n $ generico, e come $ \phi(n) $-upla prendiamo quella composta dai numeri minori e coprimi con $ n $, il punto 2 rimane vero?
Sono il cuoco della nazionale!

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Re: Somme simmetriche e congruenze modulo p

Messaggio da jordan » 26 giu 2009, 13:40

Anér ha scritto:... scrivete la soluzione solo se non sapete risolvere il problema...
:? :o :lol:


$ \phi_n(x) $ :o
The only goal of science is the honor of the human spirit.

Avatar utente
Anér
Messaggi: 720
Iscritto il: 03 giu 2008, 21:16
Località: Sabaudia

Messaggio da Anér » 27 giu 2009, 09:52

La prima parte del messaggio mi è chiara, ma cosa significa la seconda?

$ \phi_n(x) $ :o


Comunque scherzavo (il significato della frase notata da jordan era "scrivete la soluzione solo se avete svolto un consistente lavoro per risolvere il problema e siete soddisfatti del lavoro svolto"), se qualcuno ha una soluzione può postarla!
Sono il cuoco della nazionale!

travelsga
Messaggi: 39
Iscritto il: 30 giu 2008, 13:40
Località: Carrara

Messaggio da travelsga » 27 giu 2009, 11:36

Hint: p(x)=x^{\phi(n)}-1 ha le stesse radici del polinomio (x-a_1)...(x-a_{\phi(n)}) in Z_n

Avatar utente
kn
Messaggi: 508
Iscritto il: 23 lug 2007, 22:28
Località: Sestri Levante (Genova)
Contatta:

Messaggio da kn » 27 giu 2009, 13:09

Ancora meglio: x^{\phi(n)}-1 ha le stesse radici del polinomio (x+a_1)...(x+a_{\phi(n)}) in Z_n
Viviamo intorno a un mare come rane intorno a uno stagno. (Socrate)

Rispondi