OliForum Matematico

Problema: determinare il più piccolo intero $ n > 0 $ tale che, per ogni altro intero $ a > 1 $ e dispari: $ 2^{1989} \mid (a^n - 1) $.

Conclusione

$ n=2^{1987} $

Dimostrazione

Se non è altrimenti specificato, le variabili introdotte appartengono a $ \mathbb{Z} $

Il problema chiede, in pratica, di calcolare $ \min\{\exp_{2^{1989}}(a)\} $ con $ a $ variabile in $ \mathbb{N}_0-P $ dove $ P $ sono i numeri pari.

Lemma 1 (noto)

$ \exp_{2^{1989}}(a)|\phi(2^{1989})=2^{1988} $ quindi $ \exp_{2^{1989}}(a)=2^k $ con $ k\in \mathbb{N},k<1989 $


Lemma 2 (abbastanza noto, ma lo dimostro)

Se $ n\in \mathbb{N}_0, n\ge3 $ allora, se $ a $ è dispari, $ a^{\phi(2^n)/2}\equiv 1 \medskip \mod 2^n $

Induzione su $ n $
il caso $ 3 $ a mano

Poniamo funzioni per $ n $

$ a^{\phi(2^n)/2}=z*2^n+1 $
elevando al quadrato
$ a^{\phi(2^n)}=z^2*2^{2n}+1+z*2^{n+1} $
poichè, nel nostro dominio $ 2n>n+1 $ si avrà che
$ a^{\phi(2^n)}=a^{\phi(2^{n+1})/2}\equiv 1 \medskip \mod 2^{n+1} $


EDIT: Il finale fra due post

Boll ha scritto:Step 1 Si vuole dimostrare che, se $ a\not\equiv 1 \bmod 2^{1989} $, allora: $ a^{2^k}\equiv 1 \medskip \mod 2^{1989} $, con $ k\in \mathbb{N}, k<1989\mbox{ }\Longrightarrow $ $ k $ è il numero da noi cercato.

Poniamo per un attimo che tu abbia ragione, Bollo... Allora potremmo assumere $ k = 1988 $, siccome $ a^{\varphi(2^{1989})} \equiv 1 \bmod 2^{1989} $ e $ \varphi(2^{1989}) = 2^{1988} $, quando $ a\in\mathbb{Z} $ e $ a \equiv 1 \bmod 2 $. Dunque $ 1988 $ dovrebbe essere l'esponente minimo cercato...

Boll ha scritto:Conclusione $ n=2^{1987} $

...senonché le tue conclusioni lasciano intendere diversamente... Tu come te lo spieghi, caro?!? Davvero mi spiace, ma i tuoi argomenti, come spesso accade, son piuttosto sommari! Questa volta, tuttavia, lascerò volentieri che sia tu a individuare la falla che ti sta portando lentamente a fondo... E' fatto per il tuo bene, ovvio! Ché dirti poi dove sta l'errore, sarebbe del tutto equivalente a risolvere per te il problema, quindi... Dunque mi limito a farti notare, con un argomento indiretto, che l'errore c'è di certo. Dove sia tocca a te stabilirlo, ghgh...

Hitleuler ha scritto:$ \varphi(2^{1989}) = 1988 $

Uh, davvero?

Mettiamo qui le conclusioni.

Si vuol dimostrare che $ 3^{2^n}-1 $ è uno zero modulo $ 2^{n+2} $ ma non modulo $ 2^{n+3} $

Scriviamo

$ 3^{2^n}-1=(3-1)(3+1)(3^2+1)\dots(3^{2^{n-1}}+1) $
$ 3^{2^n}-1=2^3*(3^2+1)(3^{2^2}+1)\dots(3^{2^{n-1}}+1) $
poichè
$ 3^2\equiv 1 \medskip \mod 4 $
$ 3^{2^k}\equiv 1\medskip \mod 4 $
$ 3^{2^k}+1\equiv 2\medskip \mod 4 $

avremo che

$ 3^{2^n}-1=2^3*2^{n-1}*r $ dove $ r $ è un intero dispari, che è la nostra tesi e chiude il problema

Bene, Boll, adesso è tutto a posto...

Mi sono accorto dopo aver concluso "cambiando strada" che il Lemma 2 poteva essere dimostrato semplicemente osservando che, per a dispari

$ n\ge 3 $
$ a^{2^n}-1=(a-1)(a^{2^0}+1)(a^{2^1}+1)\dots (a^{2^{n-1}}+1) $
e che quindi poichè fra $ a-1 $ e $ a+1 $ c'è uno zero modulo 4 e tutti i fattori del prodotto sono pari
$ a^{2^n}-1=2^{n+2}*k $

Inoltre si ha come corollario che se $ a\neq m*2^{j}\pm 1 $ con $ m\in \mathbb{N},j>2 $, $ 2^{n+2}||(a^{2^n}-1) $