Tutti dentro $S$

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
Rho33
Messaggi: 89
Iscritto il: 16 set 2014, 13:15

Tutti dentro $S$

Messaggio da Rho33 » 07 ago 2016, 20:18

Propongo un esercizio che ho trovato molto bello, ci ho pensato quasi tutto il pomeriggio prima di avere l'idea giusta ( :oops: ), 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$.

Avatar utente
karlosson_sul_tetto
Messaggi: 1436
Iscritto il: 10 set 2009, 13:21
Località: Napoli

Re: Tutti dentro $S$

Messaggio da karlosson_sul_tetto » 08 ago 2016, 12:10

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à?
"Inequality happens"
---
"Chissa se la fanno anche da asporto"

Rho33
Messaggi: 89
Iscritto il: 16 set 2014, 13:15

Re: Tutti dentro $S$

Messaggio da Rho33 » 08 ago 2016, 23:34

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! :D )

bern-1-16-4-13
Messaggi: 72
Iscritto il: 23 mag 2015, 18:27

Re: Tutti dentro $S$

Messaggio da bern-1-16-4-13 » 13 ago 2016, 14:06

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
Messaggi: 90
Iscritto il: 11 apr 2014, 01:08

Re: Tutti dentro $S$

Messaggio da MATHia » 14 ago 2016, 11:36

bern-1-16-4-13 ha scritto: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
Messaggi: 72
Iscritto il: 23 mag 2015, 18:27

Re: Tutti dentro $S$

Messaggio da bern-1-16-4-13 » 14 ago 2016, 18:30

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
Messaggi: 89
Iscritto il: 16 set 2014, 13:15

Re: Tutti dentro $S$

Messaggio da Rho33 » 16 ago 2016, 12:32

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! :D

Rispondi