OliForum Matematico

Dimostrare che, dato a>1, se esistono m>n>0 tali che $ a^n-1 $ e $ a^m-1 $ hanno gli stessi primi (cioè un numero primo divide uno sse divide anche l'altro) allora $ a+1 $ è una potenza di 2. (naturalmente $ a,m,n $ sono interi).

Hint (per che lo vuole): provare preliminarmente il caso n=1

Per continuare la serie "riesumiamo i problemi di simo_the_wolf":

Farò uso dei due noti lemmi:
$ ~ (a^m-1,a^n-1) = a^{(m,n)} - 1 $, come interi
$ ~ (a-1,\frac{a^n-1}{a-1}) \mid n $, sempre come interi
Indico con rad(n) il prodotto dei primi che dividono n, e lo chiamerò anche radicale di n, è abbastanza comodo.

Per il lemma 1 posso supporre che m | n. Infatti $ ~ rad(a^m-1) = rad(a^n-1) $, quindi $ ~ rad(a^{(m,n)} - 1 = rad(a^n-1) $.

Mettiamo che m = kn, e faccio la sostituzione $ ~ a \rightarrow a^k $. Quindi so che $ ~ a-1, a^n-1 $ hanno lo stesso radicale. Sia p un primo che divide n. Allora $ ~ a-1, a^n-1,a^p-1 $ hanno ancora lo stesso radicale, perchè $ ~ a-1 \mid a^p-1 \mid a^n-1 $.
Quindi c'è anche una soluzione con n primo, e per chiarezza n lo chiamiamo p.
Siccome $ ~ (a-1, a^p-1) \mid p $ (lemma 2), il radicale di entrambi è p, quindi entrambi sono potenze di p. Ma sempre per questo gcd, non possono avere entrambi un esponente maggiore di 1. Quindi a-1 è proprio p (ricordiamo che a > 1).

Allora abbiamo $ ~ p^k = (p+1)^p - 1 = {p \choose p} p^p + \ldots + {p \choose 2}p^2 + {p \choose 1} p $. Ma se p>2, allora $ ~ p \choose 2 $ è multiplo di p, quindi quella somma è divisibile esattamente per $ ~ p^2 $. Ma quindi è esattamente p^2, ma allora è troppo grande per esserlo!
Quindi p = 2, da cui a = 3 e a+1 = 4, una potenza di 2!

Tornando alla "a" dell'inizio problema, sappiamo che $ ~ a^k = 3 $, quindi non c'è molta via di scampo.

Però mi sa che ho sbagliato qualcosa, visto che le potenze di 2 che becco son solamente il 4

edriv ha scritto: Siccome $ ~ (a-1, a^p-1) \mid p $ (lemma 2), il radicale di entrambi è p, quindi entrambi sono potenze di p. Ma sempre per questo gcd, non possono avere entrambi un esponente maggiore di 1. Quindi a-1 è proprio p (ricordiamo che a > 1).

Uhm qui c'è qualcosa che non va... diciamo che era $ ~ (a-1, \frac{a^p-1}{a-1}) \mid p $

Ok, diciamo che il lemma era così!

Quindi, continuando da quel punto, so che se un primo divide $ ~ a^{p-1} + a^{p-2} + \ldots + a + 1 $ allora divide anche $ ~ a-1 $ e quindi divide anche il loro mcd, che è proprio p. Concludiamo che $ ~ a^{p-1} + a^{p-2} + \ldots + a + 1 $ è una potenza di p (e ad occhio, visto che se a=1 il problema è stupido, una potenza con esponente almeno 2). Ma allora $ ~ p^2 \mid a-1 $ (sempre per il fatto dell'mcd), quindi possiamo scrivere a=kp+1 con k non multiplo di p.
Ora sostituiamo a = kp+1 in quest'espressione: $ ~ a^{p-1} + a^{p-2} + \ldots + a + 1 $, sviluppiamo coi binomiali, e ragioniamo modulo $ ~ p^2 $. Resta una roba del tipo:
$ ~ pk(p-1) + 1 + pk(p-2) + 1 + \ldots + pk2 + 1 + pk + 1 + 1 = p + pk\cdot \frac{p(p-1)}2 $. (notiamo che la frazione ha senso solo con p dispari).
Ma quindi quella roba della forma $ ~ p + p^2r $ non può essere divisibile per $ ~ p^2 $, assurdo (altrimenti a sarebbe 1). Quindi p = 2.

Ma allora abbiamo $ ~ a-1,a^2-1 $ con gli stessi fattori primi. Sia q un primo che $ ~ q \mid a+1 $. Allora $ ~ q \mid a^2-1 $, quindi $ ~ q \mid a-1 $, quindi $ ~ q \mid (a+1) - (a-1) = 2 $, quindi q = 2.

Concludiamo che a è una potenza di 2.

Questo per il caso del problema iniziale con n=1.
Concludiamo che (sempre con le lettere del problema iniziale) $ ~ a^{(m,n)} + 1 = 2^c $. Ma tu volevi a+1 una potenza di 2. Però questo mi suona strano... sei sicuro?

vuoi vedere che se $ a^k+1 = 2^c $ allora $ a+1 $ è una potenza di $ 2 $ ???