Sul numero massimo delle soluzioni all'equ. x^2 = p + n!

[Igor]

Proviamo a risolvere la questione...

Ammettiamo per ora $ p\geq 7 $

Innanzitutto deve essere $ n<2p $, altrimenti il membro di destra sarebbe divisibile una sola volta per $ p $, in contraddizione col fatto che a sinistra c'è un quadrato perfetto.

Distinguiamo ora due casi

A) $ p\leq n<2p $

Possiamo dunque porre

$ n=p+a $ con $ a=0,1,\ldots,p-1 $

L'equazione di partenza diventa

$ x^2=p\left(\frac{(p+a)!}{p}+1\right) $

Allora deve necessariamente essere

$ \left(\frac{(p+a)!}{p}+1\right)\equiv 0\bmod p $

$ -a!+1\equiv 0\bmod p\Rightarrow a!\equiv 1\bmod p $

Notiamo ora che se per un certo $ a\geq 2 $ abbiamo che

$ a!\equiv 1\bmod p $, allora

$ (a+1)!\not\equiv 1\bmod p $.

Abbiamo dunque che:

$ a=0 $ è soluzione

$ a=1 $ è soluzione

$ a=2 $ e $ a=3 $ non sono soluzioni in quanto abbiamo posto $ p\geq 7 $

$ a=p-2 $ è soluzione, quindi

$ a=p-1 $ e $ a=p-3 $ non sono soluzioni.

Restano da considerare i numeri da $ 4 $ a $ p-4 $:di questi al massimo $ \frac{p-7}{2} $ saranno soluzioni.

L'equazione di partenza, dunque, per $ p\leq n<2p $, possiede al massimo $ \frac{p-7}{2}+3=\frac{p-1}{2} $ soluzioni.


B)$ 1\leq n\leq p-1 $

Lavorando modulo $ p $ troviamo

$ x^2\equiv n!\bmod p $

Affinchè questa equazione modulare abbia soluzione, deve essere

$ \left(\frac{n!}{p}\right)=1 $.

o anche, per la moltiplicatività completa del simbolo di Legendre

$ \displaystyle\left(\frac{1}{p}\right)*\left(\frac{2}{p}\right)*\ldots *\left(\frac{n}{p}\right)=1\displaystyle $ (C)

Ora, dei numeri da $ 1 $ a $ p-1 $ esattamente $ \frac{p-1}{2} $ sono residui quadratici modulo $ p $,mentre gli altri $ \frac{p-1}{2} $ non lo sono.Dunque la (C) ha al massimo $ \left[\frac{p}{2}\right]+1 $ soluzioni, in quanto per almeno $ \left[\frac{p}{2}\right] $ valori di $ n $, abbiamo che $ \left(\frac{n!}{p}\right)=-1 $.

Ora, tra le soluzioni trovate per la (C), compare sicuramente $ n=1 $, in quanto $ \left(\frac{1!}{p}\right)=1 $.Notiamo tuttavia che l'equazione di partenza, per $ n=1 $, ammette soluzione solo se $ p=3 $.

Posto dunque $ p\geq 5 $, dobbiamo scartare la soluzione $ n=1 $ tra quelle trovate per la (C).

In definitiva, per $ p\geq 7 $ abbiamo al massimo:

$ \frac{p-1}{2} $ soluzioni per il caso A

$ \left[\frac{p}{2}\right]=\frac{p-1}{2} $ soluzioni per il caso B

In totale, dunque, il massimo numero di soluzioni è

$ p-1 $

La verifica diretta dei casi $ p=2 $, $ p=3 $ e $ p=5 $ conclude la dimostrazione(la verifica diretta è possibile grazie alla restrizione $ n<2p $).

[HiTLeuLeR]

Dunque la (C) ha al massimo $ \left[\frac{p}{2}\right]+1 $ soluzioni, in quanto per almeno $ \left[\frac{p}{2}\right] $ valori di $ n $, abbiamo che $ \left(\frac{n!}{p}\right)=-1 $.

L'idea è brava, ma purtroppo... Come HumanTorch, anche tu hai commesso - ahiahi! - una leggerezza di troppo, Igor! Il fatto è che purtroppo non c'è modo (un giorno, magari...) di prevedere la distribuzione dei non-residui quadratici $ \bmod p $ nell'insieme $ \{1, 2, \ldots, p-1\} $, e così (ad esempio) succede che, se $ n $ ed $ n+1 $ sono non-residui quadratici $ \bmod p $, per $ n = 1, 2, \ldots, p-2 $, allora: $ \displaystyle\left\lgroup\frac{n!}{p}\right\rgroup = \pm 1 $ sse $ \displaystyle\left\lgroup\frac{(n+1)!}{p}\right\rgroup = \mp 1 $. E questa osservazione, in tutta evidenza, fa sballare (sob!) i tuoi due conti... E se non ti dovesse bastare, allora... prova a considerare il caso $ p = 17 $. Scoprirai che, per $ n \in \{1, 2, \ldots, 16\} $: $ \displaystyle\left\lgroup\frac{n!}{p}\right\rgroup = -1 $ sse $ n \in \{3, 4, 6, 10, 12, 13\} $.

[moebius]

Comunque direi che ci è vicino, con la sua stima, per come l'ho capita io, si arriva ad un upper bound per il numero totale delle soluzioni di $ \displaystyle\frac{5}{4}\left(p-1\right) $

[HiTLeuLeR]

Sì, il tuo bound è quasi corretto, moebius. Se infatti $ p \equiv 1 \bmod 4 $, è chiaro che il caso più patologico si verifica quando i non-redisui quadratici $ \bmod p $ nell'insieme $ \{1, 2, \ldots, p-1\} $ - diciamo $ t_1, t_2, \ldots, t_{(p-1)/2} $ e ammettiamo $ t_1 < t_2 < \ldots < t_{(p-1)/2} $ - sono tali che, per ogni $ i=1, 2, \ldots, (p-1)/4 $: $ t_{2i} = 1 + t_{2i-1} $. E allora (visto tutto il precedente) $ \displaystyle v_p \leq 2(p - 1) - \frac{p-1}{2} - \frac{p-1}{4} = \frac{5(p-1)}{4} $. Certo gli argomenti di Igor migliorano il bound di HumanTorch, questo è innegabile, ma se vogliamo $ \displaystyle \frac{5}{4} \gg 1 $.

EDIT: corretto, in seguito alla segnalazione di moebius.

[moebius]

perchè $ \frac{1}{2} $?

[HiTLeuLeR]

...per via d'una momentanea infermità mentale, chiaramente...

[moebius]

Confesso di essere molto ignorante in materia di residui quadratici (e non solo). Ma non si riesce nemmeno a dimostrare che alcune sequenze residuo/non-residuo sono impossibili per gli interi da 1 a p-1?
Altrimenti ho paura che non le idee di Igor non possano essere spremute ulteriormente

[HiTLeuLeR]

Ma non si riesce nemmeno a dimostrare che alcune sequenze residuo/non-residuo sono impossibili per gli interi da 1 a p-1?

Sì, qualcosa si riesce a fare, ma è giusto qualcosa...

Altrimenti ho paura che non le idee di Igor non possano essere spremute ulteriormente

Lo temo anch'io...

And later...

Clicca qui, forse può aiutarti a rispondere alla tua domanda.