Se n | (b^q - 1), per ogni intero b t.c. gcd(b,n) = 1

[HiTLeuLeR]

Fissato un intero q > 1, sia $ n \in \mathbb{N} $ tale che $ b^q \equiv 1 \bmod n $, per ogni $ b \in \mathbb{Z} $ tale che gcd(b,n) = 1. Dimostrare allora che $ n \le 4q(2^q - 1) $.

[jordan]

Fissato un intero q > 1, sia $ n \in \mathbb{N} $ tale che $ b^q \equiv 1 \bmod n $, per ogni $ b \in \mathbb{Z} $ tale che gcd(b,n) = 1. Dimostrare allora che $ n \le 4q(2^q - 1) $.

[Edit] Vedi qui

[dario2994]

Uh che bello ho appena mostrato qui che $n\le 4q^2$ xD

Se pongo $n=3\cdot5\cdot7\cdot13$ e $q=12$ le ipotesi sono rispettate e mi pare che $n\le 4q^2$ non valga. (l'errore nel pdf è nella 10 quando assumi implicitamente che i $p_i-1$ siano coprimi tra loro)

[jordan]

...(l'errore nel pdf è nella 10 quando assumi implicitamente che i $p_i-1$ siano coprimi tra loro)

Chi si rivede
No l'errore non è quello, ma quello di aver assunto $p_i \mid p_i^{\alpha_i-1} \mid q$ cioè $\alpha_i \ge 2$
Grazie della correzione, vedro' di rimediare appena possibile

[jordan]

Ok, ho aggiustato la soluzione, ora dovrebbe funzionare, grazie ancora a Dario2994 che ha avuto la pazienza di leggersela

Qui e' mostrata una tesi sempre piu' forte dell'originale, i.e. $n \mid 4q(2^q-1)$
http://bboyjordan.files.wordpress.com/2012/08/blog2.pdf

Una domanda interessante potrebbe essere quello di trovare un bound asintoticamente migliore per $n$, ma ci pensero' piu' tardi..

[jordan]

..ma ci pensero' piu' tardi

Volendo, la discussione può continuare qui

[dario2994]

Io dovrei avere questo:
Dato $\epsilon>0$ esiste $K$ tale che:
$\displaystyle\ln{n}\le \left(\frac{3}{2}+\epsilon\right)\sqrt{q}+K$

p.s. non mi sono messo a ricontrollare mille volte e potrebbe essere sbagliato... diciamo che ho qualcosa che assomiglia a questo...

[dario2994]

Forse ho anche $4q^{\sqrt{\frac{q}2}+1}\ge n$.

[jordan]

Io dovrei avere questo:
Dato $\epsilon>0$ esiste $K$ tale che:
$\displaystyle\ln{n}\le \left(\frac{3}{2}+\epsilon\right)\sqrt{q}+K$

Se questa e' vera, allora e' asintoticamente migliore dell'ultima, no?

[dario2994]

Forse ho pure:
Per ogni $ \epsilon>0 $ esiste $ K $ tale che:
$ \ln n< q^\epsilon+K $

P.s. è vero che era meglio la prima stima della seconda... non mi ero accorto e forse la prima come l'avevo dimostrata era sbagliato.