149. Bastano $n$ residui $n$-esimi

[Troleito br00tal]

Sia $p$ un numero primo e sia $c$ un intero positivo fissato.

Dimostrare che, per ogni $n \ge 1$, esistono $n$ numeri $x_1;x_2;...;x_n$ tali che:

\begin{equation}
p|x_1^n+x_2^n+x_3^n+...+x_n^n+c
\end{equation}

Ah, tanto per fare il figo: own

[Troleito br00tal]

Ovviamente $n$ è intero.

[Troleito br00tal]

E anche i vari $x_i$

[jordan]

Problema interessante!

Metto la soluzione per $n=2$ (made by giove): i residui quadratici sono $\frac{1}{2}(p+1)$, così anche i residui della forma $-x^2-c$ ne sono $\frac{1}{2}(p+1)$: per il principio dei cassetti, due di essi dovranno essere uguali, e abbiamo la tesi. Grazie all'esistenza di $\varphi(\varphi(p))$ radici primitive, sappiamo che la tesi è vera anche se $\text{gcd}(n,p-1)=1$. Mancano gli altri casi, e qui credo inizi il problema

[kalu]

own

Mi prostro. Perdonate la spam.

[<enigma>]

Non troppo own...

Testo nascosto:

basta dare il giusto polinomio in pasto al Nullstellensatz combinatorio!

[Chuck Schuldiner]

Non troppo own...

Testo nascosto:

basta dare il giusto polinomio in pasto al Nullstellensatz combinatorio!

Questa volta quello che vuoi dire son riuscito a capirlo anch'io \m/

Testo nascosto:

Volendo è un corollario di Cauchy-Davenport (la probabilità che abbia scritto bene sto nome è uguale a quella che ci siano le balkan quest'anno).

[kalu]

Ma che poi in realtà una dimostrazione elementare forse esiste.

Innanzitutto notiamo che basta dimostrare la tesi per $n\mid p-1$.
Infatti, preso $n\mid p-1$ e $k$ tale che $(k, \frac{p-1}{n})=1$, si ha che i residui $n$-esimi sono uguali ai resuidi $nk$-esimi, perciò se $n$ va bene per $nk$ basta prendere gli $n$ resuidi buoni e aggiungere $n(k-1)$ termini nulli.

Supponiamo quindi $n\mid p-1$, e sia $g$ un generatore modulo $p$.
Dimostreremo che, per qualsiasi $a \in [0, p-1[$, è possibile ottenere $g^a$ come somma di al più $n$ residui $n$-esimi.
Definiamo $A_i=\{g^a : a\equiv i \pmod{n}\} \ \forall \ 0\leq i <n$.
Procediamo per induzione.
Gli elementi di $A_0$ sono residui $n$-esimi e quindi sono immediatamente ottenibili.
Per qualche $1\leq m<n$, supponiamo che esista una $m$-upla di interi distinti $\{r_i\}_1^m$ con $r_i \in[0,n[ \ \forall \ i$ tale che, per ogni $i$, tutti gli elementi di $A_{r_i}$ siano ottenibili come somma di al più $m$ residui $n$-esimi.
Il fatto che $1 \in A_0$ implica che esista almeno un $a\in \cup_1^mA_{r_i}$ tale che $a+1\in A_{r_{m+1}}$ per qualche $r_{m+1}\in [0, n[$ distinto dagli altri $r_i$.
Allora possiamo ottenere tutti gli elementi di $A_{r_{m+1}}$ con somme del tipo $g^{in}(a+1)$, facendo variare $i$ in $\bigl[0, \frac{p-1}{n}\bigl[$.
Infatti è banale verificare che $a+1\in A_{r_{m+1}} \to g^{in}(a+1) \in A_{r_{m+1}} \ \forall \ i$, e che $i\neq j \pmod{\frac{p-1}{n}} \to g^{in}(a+1)\neq g^{jn}(a+1) \pmod{p}$.
Inoltre se $a$ è ottenibile come somma di al più $m$ residui $n$-esimi allora $g^{in}(a+1)$ è ottenibile come somma di al più $m+1$ residui $n$-esimi.
Si conclude che tutti gli elementi di tutti gli $A_i$ sono ottenibili come somma di al più $n$ residui $n$-esimi.

[Troleito br00tal]

Ma che poi in realtà una dimostrazione elementare forse esiste.

Innanzitutto notiamo che basta dimostrare la tesi per $n\mid p-1$.
Infatti, preso $n\mid p-1$ e $k$ tale che $(k, p-1)=1$, si ha che i residui $n$-esimi sono uguali ai resuidi $nk$-esimi, perciò se $n$ va bene per $nk$ basta prendere gli $n$ resuidi buoni e aggiungere $n(k-1)$ termini nulli.

Supponiamo quindi $n\mid p-1$, e sia $g$ un generatore modulo $p$.
Dimostreremo che, per qualsiasi $a \in [0, p-1[$, è possibile ottenere $g^a$ come somma di al più $n$ residui $n$-esimi.
Definiamo $A_i=\{g^a : a\equiv i \pmod{n}\} \ \forall \ 0\leq i <n$.
Procediamo per induzione.
Gli elementi di $A_0$ sono residui $n$-esimi e quindi sono immediatamente ottenibili.
Per qualche $1\leq m<n$, supponiamo che esista una $m$-upla di interi distinti $\{r_i\}_1^m$ con $r_i \in[0,n[ \ \forall \ i$ tale che, per ogni $i$, tutti gli elementi di $A_{r_i}$ siano ottenibili come somma di al più $m$ residui $n$-esimi.
Il fatto che $1 \in A_0$ implica che esista almeno un $a\in \cup_1^mA_{r_i}$ tale che $a+1\in A_{r_{m+1}}$ per qualche $r_{m+1}\in [0, n[$ distinto dagli altri $r_i$.
Allora possiamo ottenere tutti gli elementi di $A_{r_{m+1}}$ con somme del tipo $g^{in}(a+1)$, facendo variare $i$ in $\bigl[0, \frac{p-1}{n}\bigl]$.
Infatti è banale verificare che $a+1\in A_{r_{m+1}} \to g^{in}(a+1) \in A_{r_{m+1}} \ \forall \ i$, e che $i\neq j \pmod{\frac{p-1}{n}} \to g^{in}(a+1)\neq g^{jn}(a+1) \pmod{p}$.
Inoltre se $a$ è ottenibile come somma di al più $m$ residui $n$-esimi allora $g^{in}(a+1)$ è ottenibile come somma di al più $m+1$ residui $n$-esimi.
Si conclude che tutti gli elementi di tutti gli $A_i$ sono ottenibili come somma di al più $n$ residui $n$-esimi.

Bene! Uguale alla mia!

Forse era meglio se non facevo il figo... però vabbé, 'ste cose non le conoscevo, quindi vabbé.

Avanti

[Gottinger95]

Comunque notevole il teorema di Cauchy-Davenport! Ma da dove le tirate fuori queste cose? xD