Generatori vietati
Generatori vietati
Mostrare che per ogni $ \displaystyle~x\in\mathbb{N}_0 $ esistono infiniti primi $ \displaystyle~p $ tali che nessun numero tra $ \displaystyle~1 $ e $ \displaystyle~x $ è generatore modulo $ \displaystyle~p $.
Viviamo intorno a un mare come rane intorno a uno stagno. (Socrate)
Una dimostrazione un po' cannoneggiante (chi ne conosce una che non usi dirichlet?)
Lemma: se a è residuo quadratico, allora non è generatore
Infatti le potenze di un residuo quadratico sono residui quadratici anch'esse e quindi sono al massimo $ \frac{p-1}2<p-1 $
Sia $ \displaystyle P=\prod_{q\in\mathbb{P}\cap[3,x]}q $. Considero tutti i numeri primi della forma 8kP+1 con k intero. Per il teorema di Dirichlet questi primi sono infiniti. Voglio ora dimostrare che se $ p\equiv1\pmod{8kP} $ allora i numeri da 1 a x sono residui quadratici, che implica la tesi.
Dato che un prodotto di residui quadratici è un residuo, mi basta dimostrare che i primi minori di x sono residui. Che 2 sia residuo quadratico mod $ p\equiv1\pmod8 $ è stato mostrato altrove da kn (non riesco a ritrovare il link).
Sia invece q un primo dispari. $ \left(\frac qp\right)=\left(\frac pq\right)\cdot(-1)^{\frac{p-1}2\frac{q-1}2} $. Ma visto che $ p\equiv1\pmod4 $ e che $ p\equiv1\pmod q $, dato che 1 è residuo quadratico modulo qualsiasi numero, RHS=1 e quindi $ \left(\frac qp\right)=1 $, cioè q è residuo quadratico modulo p. Da questo segue che tutti i numeri tra 1 e x sono residui quadratici modulo p e quindi non sono generatori.
Lemma: se a è residuo quadratico, allora non è generatore
Infatti le potenze di un residuo quadratico sono residui quadratici anch'esse e quindi sono al massimo $ \frac{p-1}2<p-1 $
Sia $ \displaystyle P=\prod_{q\in\mathbb{P}\cap[3,x]}q $. Considero tutti i numeri primi della forma 8kP+1 con k intero. Per il teorema di Dirichlet questi primi sono infiniti. Voglio ora dimostrare che se $ p\equiv1\pmod{8kP} $ allora i numeri da 1 a x sono residui quadratici, che implica la tesi.
Dato che un prodotto di residui quadratici è un residuo, mi basta dimostrare che i primi minori di x sono residui. Che 2 sia residuo quadratico mod $ p\equiv1\pmod8 $ è stato mostrato altrove da kn (non riesco a ritrovare il link).
Sia invece q un primo dispari. $ \left(\frac qp\right)=\left(\frac pq\right)\cdot(-1)^{\frac{p-1}2\frac{q-1}2} $. Ma visto che $ p\equiv1\pmod4 $ e che $ p\equiv1\pmod q $, dato che 1 è residuo quadratico modulo qualsiasi numero, RHS=1 e quindi $ \left(\frac qp\right)=1 $, cioè q è residuo quadratico modulo p. Da questo segue che tutti i numeri tra 1 e x sono residui quadratici modulo p e quindi non sono generatori.
Sì tutto giusto 
Btw,
Btw,
usi una versione debole di Dirichlet (provata qua usando solo i polinomi ciclotomici; qua un problema di lilceng più forte)Veluca ha scritto:chi ne conosce una che non usi dirichlet?
eccoloVeluca ha scritto:Che 2 sia residuo quadratico mod $ p\equiv1\pmod8 $ è stato mostrato altrove da kn (non riesco a ritrovare il link).
Viviamo intorno a un mare come rane intorno a uno stagno. (Socrate)
-
Tibor Gallai
- Messaggi: 1776
- Iscritto il: 17 nov 2007, 19:12
