127. 3 sistemi completi di residui
127. 3 sistemi completi di residui
Trova tutti i numeri naturali $n$ per i quali esiste una permutazione $(p_1,p_2,\dots,p_n)$ di numeri $(1,2,\dots,n)$ tale che gli insiemi formati dai numeri $p_i+i \quad \forall 1\leq i \leq n$ e $p_i-i \quad \forall 1\leq i \leq n$ sono sistemi completi di residui modulo $n$.
"Il bon ton è la grazia del saper vivere, la leggerezza dell' esistere." (Lina Sotis, perfidamente elegante)
Re: 127. 3 sistemi completi di residui
Definiamo $\sigma_1(i):=p_i+i$ and $\sigma_2(i):=p_i-i$ le due permutazioni di $i$, per ogni $i=1,2,\ldots,n$.
Dal momento che $\{\sigma_1(1),\sigma_1(2),\ldots,\sigma_1(n)\}$, $\{\sigma_2(1),\sigma_2(2),\ldots,\sigma_2(n)\}$ e $\{p_1,p_2,\ldots,p_n\}$ sono tre permutazioni di $\{1,2,\ldots,n\}$ allora $\displaystyle \sum_{i=1}^n{\sigma_1^2(i)+\sigma_2^2(i)} \equiv \sum_{i=1}^n{i^2+i^2}\pmod n$, cioè $\displaystyle 2\sum_{i=1}^n{p_i^2+i^2}\equiv \sum_{i=1}^n{i^2+i^2} \pmod n \implies n \mid 2\sum_{i=1}^n{p_i^2} \equiv \frac{1}{3}n(n+1)(2n+1)$: questo significa che $n$ non è multiplo di $3$.
Dal momento che $\{\sigma_2(1),\sigma_2(2),\ldots,\sigma_2(n)\}$ e' una permutazione di $\{1,2,\ldots,n\}$ allora $\displaystyle \sum_{i=1}^n{\sigma_2(i)} \equiv \sum_{i=1}^n{i} \pmod n$, cioè $n \mid \displaystyle \sum_{i=1}^n{p_i} \equiv \frac{1}{2}n(n+1)$: questo significa che $n$ deve essere dispari.
Assumiamo ora che $\text{gcd}(n,6)=1$ e poniamo $p_i\equiv 2i \pmod n$ per $i=1,2,\ldots,n$ (e' difatti una permutazione visto che $n$ e' dispari). Adesso $\sigma_1(i) \equiv 3i \pmod n$ (e' ancora una permutazione visto che $n$ non è multiplo di $3$) e banalmente $\sigma_2(i)= i$. []
Ps. Bell'esercizio
Dal momento che $\{\sigma_1(1),\sigma_1(2),\ldots,\sigma_1(n)\}$, $\{\sigma_2(1),\sigma_2(2),\ldots,\sigma_2(n)\}$ e $\{p_1,p_2,\ldots,p_n\}$ sono tre permutazioni di $\{1,2,\ldots,n\}$ allora $\displaystyle \sum_{i=1}^n{\sigma_1^2(i)+\sigma_2^2(i)} \equiv \sum_{i=1}^n{i^2+i^2}\pmod n$, cioè $\displaystyle 2\sum_{i=1}^n{p_i^2+i^2}\equiv \sum_{i=1}^n{i^2+i^2} \pmod n \implies n \mid 2\sum_{i=1}^n{p_i^2} \equiv \frac{1}{3}n(n+1)(2n+1)$: questo significa che $n$ non è multiplo di $3$.
Dal momento che $\{\sigma_2(1),\sigma_2(2),\ldots,\sigma_2(n)\}$ e' una permutazione di $\{1,2,\ldots,n\}$ allora $\displaystyle \sum_{i=1}^n{\sigma_2(i)} \equiv \sum_{i=1}^n{i} \pmod n$, cioè $n \mid \displaystyle \sum_{i=1}^n{p_i} \equiv \frac{1}{2}n(n+1)$: questo significa che $n$ deve essere dispari.
Assumiamo ora che $\text{gcd}(n,6)=1$ e poniamo $p_i\equiv 2i \pmod n$ per $i=1,2,\ldots,n$ (e' difatti una permutazione visto che $n$ e' dispari). Adesso $\sigma_1(i) \equiv 3i \pmod n$ (e' ancora una permutazione visto che $n$ non è multiplo di $3$) e banalmente $\sigma_2(i)= i$. []
Ps. Bell'esercizio
The only goal of science is the honor of the human spirit.