I numeri di Cullen

[HiTLeuLeR]

Wow!!! Anzi, che dico?!? Uau... Il nuovo forum è proprio una figata!!! Direi ch'è giusto il caso d'iniziare a imbrattarlo un po'...

Per ogni $ n\in\mathbb{N} $, si assuma $ C_n := n \cdot 2^n + 1 $. L'intero $ C_n $ così definito si dice l'$ n $-esimo numero di Cullen. Un numero di Cullen che sia primo in $ \mathbb{N} $ si dice, senz'altro aggiungere, un primo di Cullen.

Non è noto se esistano o meno infiniti primi di Cullen, ma vabbe'... di questo (quasi) nessuno si stupisce! Ben più sorprendente è invece il fatto che, sulla base delle "evidenze sperimentali", $ C_n $ sembrerebbe composito per ogni $ n\in\mathfrak{P} $. Ciò premesso, ecco la questione...

Problema #1: sia $ n\in\mathfrak{P} $. E allora $ C_n $ è un primo di Cullen sse: $ 3^{2^{n-1} n} \equiv -1 \bmod C_n $.

[HiTLeuLeR]

Beh, fortuna che c'è Whirl... Ciao, caro!!! Giusto perché qualcuno me l'ha già chiesto, preciso che $ \mathfrak{P} $ (sarebbe una "P" gotica, si può stamparla a video usando il tag tex "\mathfrak{P}") denota qui l'insieme dei numeri primi di $ \mathbb{N} $. Spero che adesso sia tutto chiaro!

[HiTLeuLeR]

Ne aggiungo un altro, decisamente più facile!!! Questo non è originale, l'altro 'nvece sì, per quanto ne so...

Problema #2: si dimostri che, se $ n\in\mathbb{N}_0 $ e $ 2n - 1 $ è un numero primo (in $ \mathbb{N} $) della forma $ 8k\pm 3 $, allora $ C_n $ è necessariamente composito.

[Simo_the_wolf]

Faccio il 2° (vi dispiace se uso Legendre?)

Dunque, abbiamo che
$ C_n=C_{\frac{p+1}2}=\frac{p+1}22^{\frac{p+1}2}+1\equiv 2^{\frac{p-1}2}+1 \pmod p $
Ma, indicando con $ ( \frac pq ) $ il simbolo di Legendre noi sappiamo che:

$ 2^{\frac{p-1}2}\equiv \left( \frac 2p \right)\equiv(-1)^{\frac{p^2-1}8} \pmod p $

Ma se p è della forma $ p=8k\pm3 $ allora avremo $ \frac{p^2-1}8\equiv1 \pmod p $ e quindi

$ C_n \equiv \left( \frac 2p \right) + 1 \equiv0\pmod p $

i.e. $ p|C_n $ (ovviamente $ C_n > p $) e quindi $ C_n $ è composto

[HiTLeuLeR]

E perché mai dovrebbe dispiacere a qualcuno? Le congruenze quadratiche non sono forse un topic da olimpiade? Credo proprio di sì! E allora mi si lasci aggiungere che, senza conoscere le proprietà elementari del simbolo di Legendre, non si può andare certo molto lontano, muovendosi in quella direzione lì, per cui...

i.e. $ p|C_n $ (ovviamente $ C_n \geq p $) e quindi $ C_n $ è composto

Lì ci va un segno di "maggiore stretto", altrimenti la deduzione non regge. Per il resto, non v'è nulla da eccepire. Adesso il problema #1, va'. Questo era giusto per il riscaldamento...

EDIT: Simo, visto che non lo si legge da nessuna parte nel corso del tuo intervento, debbo supporre che tu abbia definito $ p := 2n - 1 $. Magari scriverlo, la prossima volta... Come?!? Dici che l'inchiostro è diventato troppo caro? Boh, sarà colpa delle brusche impennate del prezzo del petrolio, cosa voj che ti dica...

[Simo_the_wolf]

Per il primo problema mi sono bloccato. Si riesce a dimostrare che $ 2^n|\varphi (C_n) $ ma non so se da qui si può concludere...

[HiTLeuLeR]

Per il primo problema mi sono bloccato. Si riesce a dimostrare che $ 2^n|\phivar(C_n) $ ma non so se da qui si può concludere...

Prova a correggere il tuo codice LaTeX, Simo. Probabilmente intendevi scriverci "\varphi(C_n)", e non "\phivar(C_n)"... Quando ne avrò la certezza, conoscerai i miei commenti!

[jordan]

Problema #1: sia $ n\in\mathfrak{P} $. E allora $ C_n $ è un primo di Cullen sse: $ 3^{2^{n-1} n} \equiv -1 \bmod C_n $.

Se $ n \in \mathfrak{P} $ e $ n \le 3 $ allora $ C_n \not \in \mathfrak{P} $, inoltre $ 3|n-1,n \in \mathfrak{P} \implies 3|C_n $, per cui d'ora in poi wlog $ 3|n+1 $.
Se $ n \in \mathfrak{P} $ e $ C_n\in \mathfrak{P} $ allora $ 3^{n2^{n-1}} = 3^{\frac{C_n-1}{2}} \equiv (\frac{3}{C_n}) = (\frac{C_n}{3})= (\frac{-1}{3}) = -1 \pmod{C_n} $.
Viceversa, $ 3^{\frac{C_n-1}{2}}\equiv -1 \pmod {C_n} \implies C_n-1|\varphi(C_n) \implies C_n \in \mathfrak{P} $.

[piever]

Uhm, visto che non so fare quella buffa P gotica, elimino l'ipotesi che n sia primo, e claimo allegramente che:

$ C_n $ è primo se $ 3^{2^{n-1} n} \equiv -1 \pmod{C_n} $

Dimostrazione:

Se $ 3^{2^{n-1} n} \equiv -1 \pmod{C_n} $ allora chiaramente, se p è un divisore primo di $ C_n $, $ 2^n |ord_{p}(3) $ da cui $ 2^n|p-1 $ e quindi $ p\ge 2^n+1 $
Supponiamo per assurdo che $ C_n $ sia composito. Allora esistono p e q primi tali che $ pq|C_n $, ma per quanto detto sopra $ p\ge 2^n+1 $ e $ q\ge 2^n+1 $, da cui $ (2^n+1)^2\le C_n=n2^n+1 $, assurdo.

[piever]

$ 3^{\frac{C_n-1}{2}}\equiv -1 \pmod {C_n} \implies C_n-1|\varphi(C_n) $.

Uhm, sei convinto che questo passaggio torni? Se sì, come lo giustifichi?

[jordan]

Eh si ho fatto proprio quello che stai pensando