Own (easy). Sia p>1 un intero positivo dispari, mostrare che $ \ln(p)<\text{ord}_p(2)<p2^{1-\omega(p)} $.
Nb. Come sempre $ \omega(\cdot) $ è il numero di fattori primi, l'ordine è il piu piccolo intero positivo h tale che $ p|2^h-1 $.
Bound stupido su ord_p(2)
Bound stupido su ord_p(2)
The only goal of science is the honor of the human spirit.
Provo...
Lemma (a)$ $ a|b-1\Rightarrow a<b $ non penso ci voglia dimostrazione.
Alur prima di tutto l'ultimo "elemento" è chiaramente p dato che w(p)=1.
Quindi bisogna dimostrare:
$ $ln(p)<Ord_p(2)<p $
L'ultima disuguaglianza deriva da (a) dato che $ $Ord_p(2)|p-1 $.
Per dimostrare l'altra noto che $ $ \ln(p)<\log_2(p) $ quindi rinforzo la tesi con:
$ \log_2(p)<Ord_p(2) $
Ora elevo 2 a quei due valori ottenendo una disuguaglianza equivalente:
$ p<2^{Ord_p(2)} $
Che è vera per (a) dato che $ $p|2^{Ord_p(2)}-1 $.
p.s. Jordan secondo me è meglio se non metti i TAG sulla difficoltà dell'esercizio... prima di tutto perchè è abbastanza soggettivo (io questo non l'ho trovato easy) e poi perchè è anche più figo tentare di risolvere un problema senza sapere neanche se si ha qualche speranza di riuscirci xD Invece quell' "easy" da una sicurezza che leva tutto il divertimento xD
Lemma (a)$ $ a|b-1\Rightarrow a<b $ non penso ci voglia dimostrazione.
Alur prima di tutto l'ultimo "elemento" è chiaramente p dato che w(p)=1.
Quindi bisogna dimostrare:
$ $ln(p)<Ord_p(2)<p $
L'ultima disuguaglianza deriva da (a) dato che $ $Ord_p(2)|p-1 $.
Per dimostrare l'altra noto che $ $ \ln(p)<\log_2(p) $ quindi rinforzo la tesi con:
$ \log_2(p)<Ord_p(2) $
Ora elevo 2 a quei due valori ottenendo una disuguaglianza equivalente:
$ p<2^{Ord_p(2)} $
Che è vera per (a) dato che $ $p|2^{Ord_p(2)}-1 $.
p.s. Jordan secondo me è meglio se non metti i TAG sulla difficoltà dell'esercizio... prima di tutto perchè è abbastanza soggettivo (io questo non l'ho trovato easy) e poi perchè è anche più figo tentare di risolvere un problema senza sapere neanche se si ha qualche speranza di riuscirci xD Invece quell' "easy" da una sicurezza che leva tutto il divertimento xD
...tristezza ed ottimismo... ed ironia...
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai
Ups sono un demente... pensandoci poi sotto la doccia mi era venuto in mente che forse non c'era l'obbligo che fosse primo...
Comunque per risolvere noto che (con x primo):
$ $Ord_{x^n}(2) $ se è pari è minore di $ $p^n $, se è dispari è minore di $ $\frac{p^n}{2} $
Fattorizzo p:
$ $p=\prod p_i^{a_i} $
In particolare:
$ $Ord_p(2)=lcm(Ord_{p_1^{a_1}}(2), Ord_{p_2^{a_2}}(2),\ \dots) $
Dato un p considero i vari ordini modulo i suoi fattori (elevati alla relativa potenza), prima di tutto cerco se ne è presente uno pari... se non è presente allora tutti gli ordini sono minori della metà del fattore (elevato alla relativa potenza) quindi:
$ $Ord_p(2)<\prod_{1\le i\le \omega(p)}p_i^{a_i}/2=\frac{p}{2^{\omega(p)}} $ che è anche più forte della tesi.
Se è presente un ordine pari il relativo fattore lo assumo "completo" (quindi coprimo con gli altri) ma tutti gli altri ordini perdono il "valore" del loro fattore 2 (se pari) perchè cerchiamo lcm di tutti. In particolare quindi anche gli ordini pari conteranno come se fossero dispari perchè nel lcm complessivo "rappresentano" meno di metà del loro modulo.
Quindi ottengo:
$ $Ord_p(2)<p_1^{a_1}\cdot \prod_{2\le i\le \omega(p)}p_i^a_i/2=\frac{p}{2^{\omega(p)-1}} $ che è la tesi.
Sono stato un po contorto ma spero si capisca... e soprattutto spero di non aver detto boiate xD
Comunque per risolvere noto che (con x primo):
$ $Ord_{x^n}(2) $ se è pari è minore di $ $p^n $, se è dispari è minore di $ $\frac{p^n}{2} $
Fattorizzo p:
$ $p=\prod p_i^{a_i} $
In particolare:
$ $Ord_p(2)=lcm(Ord_{p_1^{a_1}}(2), Ord_{p_2^{a_2}}(2),\ \dots) $
Dato un p considero i vari ordini modulo i suoi fattori (elevati alla relativa potenza), prima di tutto cerco se ne è presente uno pari... se non è presente allora tutti gli ordini sono minori della metà del fattore (elevato alla relativa potenza) quindi:
$ $Ord_p(2)<\prod_{1\le i\le \omega(p)}p_i^{a_i}/2=\frac{p}{2^{\omega(p)}} $ che è anche più forte della tesi.
Se è presente un ordine pari il relativo fattore lo assumo "completo" (quindi coprimo con gli altri) ma tutti gli altri ordini perdono il "valore" del loro fattore 2 (se pari) perchè cerchiamo lcm di tutti. In particolare quindi anche gli ordini pari conteranno come se fossero dispari perchè nel lcm complessivo "rappresentano" meno di metà del loro modulo.
Quindi ottengo:
$ $Ord_p(2)<p_1^{a_1}\cdot \prod_{2\le i\le \omega(p)}p_i^a_i/2=\frac{p}{2^{\omega(p)-1}} $ che è la tesi.
Sono stato un po contorto ma spero si capisca... e soprattutto spero di non aver detto boiate xD
...tristezza ed ottimismo... ed ironia...
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai