ELMO SL A1 + lemmini facili [L03]

[Rho33]

Ho risolto questo problema carino (sa poco di teoria dei numeri perché richiede solo divisibilità, ma comunque...). Baso il livello su quanto ci ho messo a risolverlo! Intanto due lemmini facili utili (di cui uno serve per la mia soluzione, quindi non aprite gli spoiler )

Lemma 1: Dati $x \geq 2,a,b$ interi positivi, dimostrare:

$$x^a -1 \mid x^b-1 \iff x \mid y \qquad ; \ \ x^a+1 \mid x^b+1 \iff x \mid y \wedge \ \ \dfrac {y}{x}=2k+1$$

Dimostrazione lemma 1:

Testo nascosto:

Iniziamo con il primo! Chiaramente $a<b$ quindi posso scrivere $b=qa+r$. Ora scriviamo:

$$x^a-1 \mid x^b-1 \iff x^a-1 \mid x^b-1-x^a+1 \iff x^a-1 \mid x^a (x^{b-a}-1) \iff x^a-1 \mid x^{b-a}-1$$

Ma allora reiterando la stessa sottrazione $q$ volte ottengo:

$$x^a-1 \mid x^{b-qa}-1 \iff x^a-1 \mid x^r-1$$

Ma dato che $0 \leq r <a$ si ottiene che $r=0$, ovvero:

$$x^a-1 \mid x^b-1 \iff x \mid y$$

Il secondo è quasi analogo:

$$x^a+1 \mid x^b+1 \iff x^a+1 \mid x^b+1-x^a-1 \iff x^a+1 \mid x^a(x^{b-a}-1) \iff x^a +1 \mid x^{b-a}-1$$

Stavolta aggiungiamo:

$$x^a+1 \mid x^{b-a}-1+x^a+1 \iff x^a+1 \mid x^a(b-2a)+1 \iff x^a+1 \mid x^{b-2a}+1$$

Quindi si prospettano due casi (reiterando il procedimento, ovviamente), a seconda della parità di $q$:

$\bullet \ \ q$ pari: $$x^a+1 \mid x^r+1$$

Ma quindi $r=0$ e dato che $x \geq 2$ per ipotesi, si ottiene un assurdo!

$\bullet \ \ q$ dispari: $$x^a+1 \mid x^r-1$$

Ma quindi $r=0$ ed otteniamo:

$$x^a+1 \mid x^b+1 \iff x \mid y \wedge \ \ q=2k+1$$

Lemma 2: Siano $x \geq 2 , a,b$ interi positivi. Dimostrare che:

$$(x^a-1,x^b-1)=x^{(a,b)}-1$$

Soluzione lemma 2:

Testo nascosto:

Chiamo $d$ il LHS. Dato che $(a,b) \mid a,b$ otteniamo per il lemma 1 che:

$$x^{(a,b)}-1 \mid x^a-1 \ \ \ ; \ \ \ \ x^{(a,b)}-1 \mid x^b-1 \iff x^{(a,b)}-1 \mid d$$

Inoltre sappiamo che:

$$x^a \equiv 1 \pmod d \iff \ \ \text{ord}_d(x) \mid a$$

$$x^b \equiv 1 \pmod d \iff \ \ \text{ord}_d(x) \mid b$$

Quindi :

$$\text{ord}_d(x) \mid (a,b) \iff x^{(a,b)} \equiv 1 \pmod d \iff d \mid x^{(a,b)}-1$$

Ma unito al risultato precedente otteniamo finalmente che:

$$d=x^{(a,b)}-1$$

Dopo questa digressione, ecco il problema:

Definiamo la successione $a_1=2$ e $a_n=2^{a_{n-1}}+2$ per tutti gli interi $\geq 2$. Dimostrare che:

$$a_{n-1} \mid a_n \qquad \forall n \geq 2$$



Btw, i lemmini di sopra sono molto carini ed utili, a mio parere! Ad esempio uno serve per il WC ammissione 2015 3 e per un altro problema che è uscito sul forum postato da Giovanni98 , che però non ho in mente in questo momento (ovviamente, io li ho usati nelle mie soluzioni, poi credo si faccia anche senza )