esponenziale un po strana

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
drago90
Messaggi: 53
Iscritto il: 02 gen 2009, 16:06
Località: siena

esponenziale un po strana

Messaggio da drago90 » 05 mag 2009, 00:08

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...
Ultima modifica di drago90 il 05 mag 2009, 14:52, modificato 1 volta in totale.

Simo_the_wolf
Moderatore
Messaggi: 1030
Iscritto il: 01 gen 1970, 01:00
Località: Pescara

Messaggio da Simo_the_wolf » 05 mag 2009, 00:38

Penso le parentesi siano nell'altro modo cioè $ 1989 | n^{(n^{(n^n)})}-n^{(n^n)} $ altrimenti scazza quando ad esempio $ n \equiv 3 \pmod{4} $ ed è anche un generatore modulo 17 (a voi i conti e capire il perchè... :P).

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Messaggio da jordan » 11 mag 2009, 12:13

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)
The only goal of science is the honor of the human spirit.

travelsga
Messaggi: 39
Iscritto il: 30 giu 2008, 13:40
Località: Carrara

Messaggio da travelsga » 12 mag 2009, 17:04

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.
Ultima modifica di travelsga il 12 mag 2009, 18:04, modificato 1 volta in totale.

EvaristeG
Site Admin
Messaggi: 4771
Iscritto il: 01 gen 1970, 01:00
Località: Roma
Contatta:

Messaggio da EvaristeG » 12 mag 2009, 17:45

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.

drago90
Messaggi: 53
Iscritto il: 02 gen 2009, 16:06
Località: siena

Messaggio da drago90 » 13 mag 2009, 12:53

grazie molto per aiuto,ora proverò a continuare; spero di riuscire a postare la soluzione..ma la vedo dura...

Rispondi