Generatori vietati

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
Avatar utente
kn
Messaggi: 508
Iscritto il: 23 lug 2007, 22:28
Località: Sestri Levante (Genova)
Contatta:

Generatori vietati

Messaggio da kn » 09 lug 2010, 22:40

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)

lilceng
Messaggi: 12
Iscritto il: 03 giu 2010, 04:25

Messaggio da lilceng » 10 lug 2010, 13:16

Idea: scontata, ma chissà se porta alla soluzione: un generatore non è un residuo quadratico :o

ps. postato da hitleuler se non erro.

ps2. oltre che infiniti, si potrebbe aggiungere che anche la somma dei reciproci di questi diverge :shock:

Veluca
Messaggi: 185
Iscritto il: 27 dic 2008, 01:08
Località: Chiavari (Genova)

Messaggio da Veluca » 11 lug 2010, 15:07

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.

Avatar utente
kn
Messaggi: 508
Iscritto il: 23 lug 2007, 22:28
Località: Sestri Levante (Genova)
Contatta:

Messaggio da kn » 11 lug 2010, 15:44

Sì tutto giusto :wink: Btw,
Veluca ha scritto:chi ne conosce una che non usi dirichlet?
usi una versione debole di Dirichlet (provata qua usando solo i polinomi ciclotomici; qua un problema di lilceng più forte)
Veluca ha scritto:Che 2 sia residuo quadratico mod $ p\equiv1\pmod8 $ è stato mostrato altrove da kn (non riesco a ritrovare il link).
eccolo
Viviamo intorno a un mare come rane intorno a uno stagno. (Socrate)

lilceng
Messaggi: 12
Iscritto il: 03 giu 2010, 04:25

Messaggio da lilceng » 11 lug 2010, 17:53

kn ha scritto:... qua un problema di lilceng più forte...
Jordan non scrive più su questo forum.

Tibor Gallai
Messaggi: 1776
Iscritto il: 17 nov 2007, 19:12

Messaggio da Tibor Gallai » 11 lug 2010, 18:12

Ma sono sicuro che prima o poi tornerà. Magari in questo momento sta proprio leggendo questo thread.
[quote="Pigkappa"]Penso che faresti un favore al mondo se aprissi un bel topic di bestemmie da qualche parte in modo che ti bannino subito.[/quote]

Avatar utente
kn
Messaggi: 508
Iscritto il: 23 lug 2007, 22:28
Località: Sestri Levante (Genova)
Contatta:

Messaggio da kn » 11 lug 2010, 20:42

lilceng ha scritto:Jordan non scrive più su questo forum.
Si scusa era un lapsus.. :oops:
Viviamo intorno a un mare come rane intorno a uno stagno. (Socrate)

Rispondi