edit: ora ha più senso in effetti...
esponenziale un po strana
esponenziale un po strana
non so se è già stato postato o no comunque: dimostrare che,se $ n>=3 $ allora $ 1989|n^{n^{n^{n}}}-n^{n^{n}} $ io sono arrivato a dimostrare la divisibilità per 9 ma poi mi sono arenato..
edit: ora ha più senso in effetti...
edit: ora ha più senso in effetti...
Ultima modifica di drago90 il 05 mag 2009, 14:52, modificato 1 volta in totale.
-
Simo_the_wolf
- Moderatore
- Messaggi: 1053
- Iscritto il: 01 gen 1970, 01:00
- Località: Pescara
).
Bonus question.
Siano $ b \ge 1 $ un intero e $ \{a_i\}_{i \in \mathbb{N}} $ la successione a valori in $ \mathbb{N} $ definita assumendo $ a_0 = b $ e $ a_{i+1} = b^{a_i} $, per ogni $ i \in \mathbb{N} $.
Provare che, comunque sia scelto $ n \in \mathbb{N}_0 $, esiste $ k \in \mathbb{N} $ tale che $ n \mid (a_{k+2009}-a_k) $.
(Salvatore Tringali)
Siano $ b \ge 1 $ un intero e $ \{a_i\}_{i \in \mathbb{N}} $ la successione a valori in $ \mathbb{N} $ definita assumendo $ a_0 = b $ e $ a_{i+1} = b^{a_i} $, per ogni $ i \in \mathbb{N} $.
Provare che, comunque sia scelto $ n \in \mathbb{N}_0 $, esiste $ k \in \mathbb{N} $ tale che $ n \mid (a_{k+2009}-a_k) $.
(Salvatore Tringali)
The only goal of science is the honor of the human spirit.
Bonus question...
Lemma: la successione $ b,b^b,b^{b^b},... $ diventa costante modulo $ n $ da un certo punto in poi.
Dimostrazione: sia $ m=(b,n)\rightarrow b=md $ e sia $ \displaystyle M=\prod_{p_i|m , p_i^{a_i}||n}{p_i^{a_i}}\rightarrow n=dM $, la tesi risulta verificata se la successione $ \{b_i^{e_i}\}_{i\in\mathbb{N}} $
è costante modulo M e modulo d.
Chiaramente la successione diviene costante prima o poi modulo M avendo b gli stessi primi di M nella sua fattorizzazione. Modulo d si ha $ (b,d)=1 $,
considero pertanto la successione $ \{e_i\}_{i\in\mathbb{N}} $ degli esponenti modulo $ \phi(d) $; ad un certo punto si avrà $ \displaystyle e_{j+1}-e_j\equiv 0\pmod{\phi(d)}\rightarrow e_{j+2}-e_{j+1}\equiv b^{e_{j+1}}-b^{e_j}\equiv 0 \pmod{\phi(d)} $
ovvero gli esponenti sono costanti modulo $ \phi(d) $ da quel punto in poi (induzione), ma allora $ b^{e_{j+1}}\equiv b^{e_j+k\phi(d)}\equiv b^{e_j}(b^{\phi(d)})^k\equiv b^{e_j}\pmod d $
quindi la successione è costante modulo d da quel punto in poi (induzione).
Ne consegue che $ \{b_i^{e_i}\}_{i\in\mathbb{N}} $ deve, prima o poi, diventare costante modulo n.
Segue la tesi.
Lemma: la successione $ b,b^b,b^{b^b},... $ diventa costante modulo $ n $ da un certo punto in poi.
Dimostrazione: sia $ m=(b,n)\rightarrow b=md $ e sia $ \displaystyle M=\prod_{p_i|m , p_i^{a_i}||n}{p_i^{a_i}}\rightarrow n=dM $, la tesi risulta verificata se la successione $ \{b_i^{e_i}\}_{i\in\mathbb{N}} $
è costante modulo M e modulo d.
Chiaramente la successione diviene costante prima o poi modulo M avendo b gli stessi primi di M nella sua fattorizzazione. Modulo d si ha $ (b,d)=1 $,
considero pertanto la successione $ \{e_i\}_{i\in\mathbb{N}} $ degli esponenti modulo $ \phi(d) $; ad un certo punto si avrà $ \displaystyle e_{j+1}-e_j\equiv 0\pmod{\phi(d)}\rightarrow e_{j+2}-e_{j+1}\equiv b^{e_{j+1}}-b^{e_j}\equiv 0 \pmod{\phi(d)} $
ovvero gli esponenti sono costanti modulo $ \phi(d) $ da quel punto in poi (induzione), ma allora $ b^{e_{j+1}}\equiv b^{e_j+k\phi(d)}\equiv b^{e_j}(b^{\phi(d)})^k\equiv b^{e_j}\pmod d $
quindi la successione è costante modulo d da quel punto in poi (induzione).
Ne consegue che $ \{b_i^{e_i}\}_{i\in\mathbb{N}} $ deve, prima o poi, diventare costante modulo n.
Segue la tesi.
Ultima modifica di travelsga il 12 mag 2009, 18:04, modificato 1 volta in totale.
Bravi, ottimi cazzeggi teorici, ma nessuno dei due ha davvero risposto al problema. Infatti, a livello teorico, servirebbero 6 passi alla successione per stabilizzarsi modulo 1989, mentre il testo ne concede solo 4.
Allora, tanto per dare qualche hint a drago90:
1) se vuoi che valga $ n^a-n^b\equiv 0 \mod m $ per ogni n maggiore di un certo numero (ad esempio 3), devi avere che $ a-b\equiv 0 \mod \varphi(m) $, dove $ \varphi(m) $ è la funzione di eulero; però nel nostro caso a e b dipendono da n, quindi il se e solo se non è più vero. Certo, rimane una condizione sufficiente.
2) tu vuoi che la relazione sopra valga per m=1989, ovvero, grazie al teorema cinese del resto, che valga per m=9,13,17; per m=9 è tutto più facile perché:
$ n^{n^{n^n}}-n^{n^n}\equiv 0 \mod 9 $
se
$ n^{n^n}-n^n\equiv 0 \mod \varphi(9)=6 $
se
$ n^n-n\equiv 0\mod \varphi(6)=2 $
che è sempre vero.
3) per 13, ad esempio, ti viene che tutto funziona per n dispari:
se $ n-1\equiv 0 \mod 2 $ allora
$ n^n-n\equiv 0\mod 4 $ e dunque
$ n^{n^n}-n^n\equiv 0 \mod 12 $ da cui
$ n^{n^{n^n}}-n^{n^n}\equiv 0 \mod 13 $
e per gli n pari?
4) considera che la relazione $ n^a-n^b\equiv 0 \mod m $ può anche essere vera non per condizioni sugli esponenti, ma sulle basi, ad esempio, se entrambe le basi sono 0 o sono 1, oppure, avendo condizioni sulla base, si possono fare richieste meno restrittive sugli esponenti: per farti un esempio,
$ 2^a\equiv 2^b \mod 15 $ vale ogni volta che $ a\equiv b \mod 4 $ anche se $ \varphi(15)=8 $.
Utilizzando le osservazioni del punto 4, puoi provare almeno a concludere il caso di 13.
Allora, tanto per dare qualche hint a drago90:
1) se vuoi che valga $ n^a-n^b\equiv 0 \mod m $ per ogni n maggiore di un certo numero (ad esempio 3), devi avere che $ a-b\equiv 0 \mod \varphi(m) $, dove $ \varphi(m) $ è la funzione di eulero; però nel nostro caso a e b dipendono da n, quindi il se e solo se non è più vero. Certo, rimane una condizione sufficiente.
2) tu vuoi che la relazione sopra valga per m=1989, ovvero, grazie al teorema cinese del resto, che valga per m=9,13,17; per m=9 è tutto più facile perché:
$ n^{n^{n^n}}-n^{n^n}\equiv 0 \mod 9 $
se
$ n^{n^n}-n^n\equiv 0 \mod \varphi(9)=6 $
se
$ n^n-n\equiv 0\mod \varphi(6)=2 $
che è sempre vero.
3) per 13, ad esempio, ti viene che tutto funziona per n dispari:
se $ n-1\equiv 0 \mod 2 $ allora
$ n^n-n\equiv 0\mod 4 $ e dunque
$ n^{n^n}-n^n\equiv 0 \mod 12 $ da cui
$ n^{n^{n^n}}-n^{n^n}\equiv 0 \mod 13 $
e per gli n pari?
4) considera che la relazione $ n^a-n^b\equiv 0 \mod m $ può anche essere vera non per condizioni sugli esponenti, ma sulle basi, ad esempio, se entrambe le basi sono 0 o sono 1, oppure, avendo condizioni sulla base, si possono fare richieste meno restrittive sugli esponenti: per farti un esempio,
$ 2^a\equiv 2^b \mod 15 $ vale ogni volta che $ a\equiv b \mod 4 $ anche se $ \varphi(15)=8 $.
Utilizzando le osservazioni del punto 4, puoi provare almeno a concludere il caso di 13.