Tutti dentro $S$

[Rho33]

Propongo un esercizio che ho trovato molto bello, ci ho pensato quasi tutto il pomeriggio prima di avere l'idea giusta ( ), ma garantisco che appena si trova, diventa quasi banale!

Una sequenza di interi positivi $a_1, \dots , a_n$ ha la proprietà che ogni termine è una potenza di $2$ distinta dalle altre. Consideriamo il seguente insieme:

$$ \displaystyle S= \left \{ \left ( \prod _{k=i}^{j}a_k \right ) -1 \ \ \mid \ \ i \leq j \right \}$$

Supponiamo che $S$ non abbia nessun elemento multiplo di $n+2$. Determinare tutti gli $n$ per cui sia valida questa proprietà di $S$.

[karlosson_sul_tetto]

Bisogna trovare tutti gli n tali che esista una sequenza $a_1,\ldots, a_n$ tale che $S$ soddisfi la proprietà o che per ogni sequenza $a_1,\ldots, a_n$, $S$ soddisfi la proprietà?

[Rho33]

La prima che hai detto: tutti gli $n$ tali che esista una sequenza $a_1, \dots , a_n$ tale che $S$ soddisfi la proprietà! D'altronde, la seconda richiesta secondo me è molto più immediata della prima (chi vuole, faccia pure la seconda interpretazione di karlosson, potrebbe servire per capire meglio la prima! )

[bern-1-16-4-13]

Per $n$ Parisi vede subito che una qualsiasi$n$-upla con tutte potenze di due diverse da $1$ soddisfa per discorsi di parità. Quindi supponiamo $n$ dispari.
Usiamo la notazione $\Pi_k=\prod_{i=1}^ka_i$.
Notiamo innanzitutto che $\Pi_k\not\equiv \Pi_h\pmod{n+2}\ \ \forall k<h$ perché altrimenti $$\Pi_h-\Pi_k=\prod_{i=1}^ka_i\left(\prod_{j=k+1}^h-1\right)=2^s\left(\prod_{j=k+1}^h-1\right)\equiv 0\pmod{n+2},$$che è assurdo poiché essendo $n+2$ dispari vorrebbe dire che $\left(\prod_{j=k+1}^h-1\right)\equiv 0\pmod{n+2}$.
Quindi i $\Pi_i$ appartengono a $n$ classi di resto differenti modulo $n+2$. Per ipotesi non possono essere congrui $1$ e tantomeno congrui $0$ essendo $n+2$ dispari e diverso da $1$. Quindi devono coprire tutte le altre classi di resto modulo $n+2$. Questo chiaramente non accade se $n+2$ non è primo, e se $2$ non genera modulo $n+2$. Se invece $n+2$ è un primo con $2$ generatore, si vede facilmente che la $n$-upla $\{2,2,...,2\}$ soddisfa.
La risposta al problema è quindi tutti gli $n$ pari e tutti gli $n$ tali che $n+2$ è un primo che ha $2$ come generatore.

[MATHia]

Se invece $n+2$ è un primo con $2$ generatore, si vede facilmente che la $n$-upla $\{2,2,...,2\}$ soddisfa.

La $n$-upla non doveva avere tutte potenze di 2 distinte?

[bern-1-16-4-13]

Già hai ragione, mi era sfuggito, però se non sbaglio in questo caso per ovviare il problema basta scegliere tutti gli esponenti congrui $1$ modulo $\phi(n+2)=n+1$.

[Rho33]

Ok, bene tutto corretto dopo l'osservazione di MATHia! In particolare, tutte le potenze di due nella forma $2^{k \cdot (n+1)+1}$ soddisfano!