OliForum Matematico

No, calmi tutti.

NESSUNO CHE PROVI A POSTARE UNA SOLUZIONE, UN'IDEA DI SOLUZIONE, UN COMMENTO AD UNA SOLUZIONE, UNA DOMANDA SUL PROBLEMA STA FACENDO SPAM.

Questo non è un archivio con le soluzioni più belle, è un forum e in quanto tale deve e vuole ospitare discussioni; tutti possono postare il loro contributo e l'aiutare e indirizzare i neofiti dovrebbe essere sentito come un dovere morale dagli utenti più esperti. Non denigrarli per le soluzioni sbagliate o insultarli per gli errori commessi, ma semplicemente guidarli alla soluzione ed evidenziarne le mancanze con un minimo di senso didattico.
Si impara a camminare provandoci e cadendo, non rimanendo seduti fin quando non ci si sente in grado di far la maratona.

Concludendo, mi auguro di non vedere più inviti a non postare soluzioni che non siano più che perfette, se non nei casi in cui evidentemente chi posta vuole solo far perdere tempo al prossimo. Inoltre, rendendomi conto che questo intervento era off topic (ma ritenendolo indispensabile), prego chiunque volesse rispondermi su queste osservazioni di non farlo in questo thread: ci sono i messaggi privati o altre parti del forum.

A leggerti così, più che un moderatore sembri una maestrina assai zelante, caro Ev...

EvaristeG ha scritto:Inoltre, rendendomi conto che questo intervento era off topic (ma ritenendolo indispensabile), prego chiunque volesse rispondermi su queste osservazioni di non farlo in questo thread: ci sono i messaggi privati o altre parti del forum.

Lo so che a lezione non abbiamo ancora finito tutto l'abbecedario, ma non mi sembrava che fosse così difficile da leggere, questo passaggio...

Nell'eroico tentativo disperato di rilanciare le sorti del thread: "dimostrare che, per ogni $ k\in\mathbb{N} $, esiste $ n\in\mathbb{N} $ tale che $ 3^k \mid (5^n - 2) $."

Provo a dimostrare qualcosa di più forte.
Sia g un generatore modulo $ ~ 3^k, k \ge 2 $. Allora g è un generatore anche modulo $ ~ 3^n, n \ge k $.

Dimostrazione (per induzione).
Sappiamo che (modulo $ ~ 3^{k+1} $) abbiamo $ ~ \phi(\phi(3^{k+1})) = \phi(2 \cdot 3^k) = \phi(2) \cdot \phi(3^k) = 2 \cdot 3^{k-1} $ generatori.
Se a è un generatore modulo $ ~ 3^{k+1} $, allora a deve anche essere un generatore modulo 3^k. (*)

D'altra parte, l'insieme G dei generatori $ ~ \pmod {3^k} $ ha $ ~ 2 \cdot 3^{k-2} $ elementi. L'insieme degli elementi x tali che $ ~ x \equiv g \pmod {3^{k+1}} $ per un elemento $ ~ g \in G $ ha $ ~ 3 \cdot |G| = 3^{k-1} $ elementi (infatti, preso un elemento di g, posso aggiungere $ ~ 0, 3^k, 2\cdot 3^k $).
Quindi tutti e soli i generatori di G, traslati di $ ~ 0, 3^k, 2\cdot 3^k $ per ottenere dei resti $ ~ \pmod {3^{k+1}} $, sono generatori $ ~ \pmod {3^{k+1}} $.


5 è un generatore modulo 3 e 9, quindi per ogni k esisterà un n tale che:
$ ~ 5^n \equiv 2 \pmod {3^k} $, e by the way anche 2 è sempre un generatore.

(*): Se $ ~ a^n \equiv 1 \pmod {3^k} $ allora il resto di a modulo $ ~ 3^{k+1} $ può essere $ ~ 1, 3^k+1, 2 \cdot 3^k +1 $. Ma $ ~ (3^k+1)^3 = 3^{3k} + 3^{2k+1} + 3^{k+1} + 1 \equiv 3 1 \pmod {3^{k+1}} $ e allo stesso modo $ ~ (2 \cdot 3^k + 1)^3 \equiv 1 \pmod {3^{k+1}} $.
Quindi questo implicherebbe che $ ~ a^{3n} \equiv 1 \pmod {3^{k+1}} $, cioè $ 2 \cdot 3^k \mid 3n $, che implica $ 2 \cdot 3^{k-1} \mid n $... quindi a è un generatore.

edriv ha scritto:Provo a dimostrare qualcosa di più forte.
Sia g un generatore modulo $ ~ 3^k, k \ge 2 $. Allora g è un generatore anche modulo $ ~ 3^n, n \ge k $.

Oh, bene! Ma adesso il problema originale.