Il più piccolo n tale che 2^1989 divida a^n - 1
Il più piccolo n tale che 2^1989 divida a^n - 1
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
$ 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
Ultima modifica di Boll il 25 ago 2005, 16:01, modificato 3 volte in totale.
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: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.
...senonché le tue conclusioni lasciano intendere diversamente...Boll ha scritto:Conclusione $ n=2^{1987} $
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...
Ultima modifica di HiTLeuLeR il 25 ago 2005, 16:15, modificato 1 volta in totale.
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
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
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) $
$ 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) $