Divisori della forma $n^2+1$

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
Talete
Messaggi: 655
Iscritto il: 05 giu 2014, 13:47
Località: Riva del Garda

Divisori della forma $n^2+1$

Messaggio da Talete » 28 apr 2017, 16:55

Tornando a casa oggi mi sono accorto che $10$ gode della seguente magica proprietà: i suoi divisori positivi infatti sono tutti numeri della forma $n^2+1$ per un certo $n$ intero: $1=0^2+1$, $2=1^2+1$, $5=2^2+1$ e $10=3^2+1$. Secondo voi, quanti numeri esistono con questa proprietà? Okay, c'è sicuramente l'$1$, il $2$, il $5$ ed il $10$, ma poi? Tutti i numeri primi della forma $n^2+1$, tipo $17$... boh, ve lo lascio così come curiosità, dato che non ho dimostrato niente ;)
Ultima modifica di Talete il 28 apr 2017, 18:16, modificato 1 volta in totale.
"Sei il Ballini della situazione" -- Nikkio
"Meriti la menzione di sdegno" -- troppa gente
"Sei arrivato 69esimo? Ottima posizione!" -- Andrea M. (che non è Andrea Monti, come certa gente pensa)
"Se ti interessa stanno inventando le baricentriche elettroniche, che dovrebbero aiutare a smettere..." -- Bernardo

Avatar utente
Sirio
Messaggi: 198
Iscritto il: 08 set 2016, 22:01

Re: Divisori della forma $n^2+1$

Messaggio da Sirio » 28 apr 2017, 18:04

Per come hai scritto il $10$ ti devi essere bevuto qualcosa di forte :lol:
Anche il $2$... Non è sbagliato ma dovevi far notare $1^2$ e non $1^1$
Senza offesa, eh?


Comunque, per quelli primi tipo $17$, i divisori sono solo sè stesso, per ipotesi esprimibile come $n^2+1$, e $1=0^2+1$, quindi sono in regola.

Per quelli non primi, non funziona per tutti (ti basta provare $26$ e vedere che non va), ma non ti so dire per quali...
シリオ
$T=\sqrt{\dfrac l g 12\pi}$

Talete
Messaggi: 655
Iscritto il: 05 giu 2014, 13:47
Località: Riva del Garda

Re: Divisori della forma $n^2+1$

Messaggio da Talete » 28 apr 2017, 18:15

Sirio ha scritto:
28 apr 2017, 18:04
Per come hai scritto il $10$ ti devi essere bevuto qualcosa di forte :lol:
Anche il $2$... Non è sbagliato ma dovevi far notare $1^2$ e non $1^1$
Senza offesa, eh?
Lol. Sistemo ;)
Sirio ha scritto:
28 apr 2017, 18:04
Comunque, per quelli primi tipo $17$, i divisori sono solo sè stesso, per ipotesi esprimibile come $n^2+1$, e $1=0^2+1$, quindi sono in regola.
Eh sì sì per quelli va tutto bene...
Sirio ha scritto:
28 apr 2017, 18:04
Per quelli non primi, non funziona per tutti (ti basta provare $26$ e vedere che non va), ma non ti so dire per quali...
Appunto, sono quelli non primi il problema. Eppure $10$ funziona e non è primo...
"Sei il Ballini della situazione" -- Nikkio
"Meriti la menzione di sdegno" -- troppa gente
"Sei arrivato 69esimo? Ottima posizione!" -- Andrea M. (che non è Andrea Monti, come certa gente pensa)
"Se ti interessa stanno inventando le baricentriche elettroniche, che dovrebbero aiutare a smettere..." -- Bernardo

Avatar utente
karlosson_sul_tetto
Messaggi: 1430
Iscritto il: 10 set 2009, 13:21
Località: Napoli

Re: Divisori della forma $n^2+1$

Messaggio da karlosson_sul_tetto » 29 apr 2017, 17:26

Stiamo cercando i numeri con tutti i divisori della forma $n^2+1$; siccome $0^2+1=1$ possiamo considerare $n>0$.


Caso 1: $n^2+1$ è primo
In questo caso internet ci dice che si congettura che tali primi siano infiniti; per ora non ci possiamo fare nulla e sperare in questo anche noi.

Caso 2: $n^2+1$ composto; in particolare ha almeno due divisori primi $p$ e $q$.
Tutti i fattori primi di $n^2+1$ devono essere della forma $x^2+1$, quindi $p=a^2+1$ e $q=b^2+1$ e $pq=c^2+1=(a^2+1)(b^2+1)$ perché $pq \mid n^2+1$. Se $p=q$, allora $c^2+1=(a^2+1)^2$ e gli unici quadrati a distanza $1$ sono $0,1$, quindi in questo caso non posso avere soluzioni. $n^2+1$ è dunque libero da quadrati.
E ora abbiamo $p\neq q$, ma non ci bastano i primi normali, perché da adesso usiamo i primi di gauss; probabilmente le cose che scriverò non saranno eccessivamente precise quindi ogni correzioni da maestri di tdn algebrica è ben desiderato.

Gli interi di gauss sono numeri complessi della forma $a+ib$ con $a,b\in \mathbb{Z}$; visto che $\mathbb{Z}$[$i$] è un dominio a fattorizzazione unica, gli irriducibili sono primi e i primi sono irriducibili.
traduzione: un numero è primo se è divisibile solo per se stesso e 1, tutto a meno di moltiplicare questi due numeri per uno tra $(1,i,-1,-i)$.

in particolare si ha che i primi di gauss (sempre a meno di moltiplicare per una delle 4 unità o fare il coniugato) sono
1) i primi congrui a $3 \mod 4$
2) i numeri della forma $a+bi$ con $a^2+b^2=$primo. (questo è un se e solo se: visto che $13=2^2+3^2$, si ha che $2+3i$ è un primo)

Dunque possiamo fattorizzare $c^2+1=(c+i)(c-i)$, e in particolare $(c+i)(c-i)=c^2+1=(a^2+1)(b^2+1)=(a+i)(a-i)(b+i)(b-i)$ dove i 4 fattori a destra sono tutti primi. Un fattore a destra dev'essere dunque combinazioni di questi primi, con una certa unità davanti. Noto che se uno tra $a,b=0$ ottengo che $(a+i)(a-i)=1$ che non è un numero primo, quindi $a,b\neq 0$. I casi sono:

$\begin{cases}c+i=i^k(a+i) \\
c-i=i^h(a-i)(b+i)(b-i) \end{cases}
\begin{cases}c+i=i^k(a-i) \\
c-i=i^h(a+i)(b+i)(b-i) \end{cases} \
\begin{cases}c+i=i^k(a+i)(b+i) \\
c-i= i^h(a-i)(b-i) \end{cases}
\begin{cases}c+i=i^k(a+i)(b-i) \\
c-i= i^h(a-i)(b+i) \end{cases}
$

$\begin{cases}c+i=i^k(a-i)(b-i) \\
c-i= i^h(a+i)(b+i) \end{cases}
\begin{cases}c+i=i^k(a+i)(b+i)(b-i) \\
c-i=i^h(a-i) \end{cases}
\begin{cases}c+i=i^k(a-i)(b+i)(b-i) \\
c-i=i^h(a+i) \end{cases} \
\begin{cases} c+i=i^k(a+i)(a-i)\\
c-i=i^h(b+i)(b-i)\end{cases}
$

$
\begin{cases}c+i=i^k \\
c-i=i^h\cdot (a+i)(a-i)(b+i)(b-i) \end{cases}
\begin{cases}c+i=i^k (a+i)(a-i)(b+i)(b-i) \\
c-i=i^h \end{cases} \
$

(dove $k+h\equiv 0 \pmod{4}$)

Gli ultimi tre si liquidano facilmente perché servirebbe $c=0$ e dunque anche $a=b=0$.
Nel primo, secondo, sesto e settimo si arriva a $c=\pm a$ e $(b+i)(b-i)=i^{\text{qualcosa}}$ che implica $b=0$, quindi ciaone.
Nel terzo, quarto e quinto svolgendo si arriva a:
$\begin{cases} c+i=i^k(ab-1+i(\pm a \pm b)) \\
c-i=i^k(ab-1-i(\pm a \pm b)) \end{cases}$
Se $i^k=1,-1$ si ottiene confrontando la parte immaginaria che $1=\pm a \pm b$; questo significa che a,b hanno parità diverse e quindi $a^2+1$ e $b^2+1$ hanno parità diverse. Questo è possibile solo se uno di questi due primi è 2, ovvero WLOG $b=1$. Questo significa che $a=\pm 1 \pm b=-2,0,2$ che portano all'unica soluzione con $a^2+1=5$ e quindi $c^2+1=10$.

Se $i^k=i$, allora sempre con la parte immaginaria si ottiene $1=ab-1$, ovvero $ab=2$ che da le soluzioni trovate prima (a meno di segno) $(1,2)$.
Se $i^k=-i$ allora $1=-(ab-1)=1-ab$, dunque $ab=0$ e quindi non ci sono soluzioni interessanti.



In conclusione: ci potrebbero essere infiniti primi della forma $n^2+1$ ma $10$ è l'unico composto con la proprietà cercata
"Inequality happens"
---
"Chissa se la fanno anche da asporto"

Talete
Messaggi: 655
Iscritto il: 05 giu 2014, 13:47
Località: Riva del Garda

Re: Divisori della forma $n^2+1$

Messaggio da Talete » 29 apr 2017, 19:27

Che potente Nikkio! Bella soluzione :)
"Sei il Ballini della situazione" -- Nikkio
"Meriti la menzione di sdegno" -- troppa gente
"Sei arrivato 69esimo? Ottima posizione!" -- Andrea M. (che non è Andrea Monti, come certa gente pensa)
"Se ti interessa stanno inventando le baricentriche elettroniche, che dovrebbero aiutare a smettere..." -- Bernardo

Avatar utente
Sirio
Messaggi: 198
Iscritto il: 08 set 2016, 22:01

Re: Divisori della forma $n^2+1$

Messaggio da Sirio » 29 apr 2017, 20:50

Urca! Ma quanto tempo ci hai messo?
シリオ
$T=\sqrt{\dfrac l g 12\pi}$

Giovanni_98
Messaggi: 69
Iscritto il: 10 apr 2015, 18:19

Re: Divisori della forma $n^2+1$

Messaggio da Giovanni_98 » 29 apr 2017, 21:41

Se non ho sbagliato niente (e vado di fretta, quindi leggere con attenzione), non servono strumenti "avanzati" per risolvere il problema (senza nulla togliere alla soluzione di Nikita). Ciò che mi presterò a dimostrare è che gli unici primi $p<q$ nella forma $n^2+1$ tali che $pq=m^2+1$ per qualche $m$ sono $2$ e $5$.

Impongo $(n^2+1)(m^2+1) = z^2+1$ con la condizione che entrambi i fattori dell'LHS sono numeri primi. Ora, WLOG $0 < n < m$ (il caso di uguaglianza come ha mostrato Nikkio è banale), quindi pongo $n=m-c$ ove $c$ è naturalmente un numero intero positivo. Facendo la sostituzione e svolgendo i calcoli ottengo la seguente equazione di secondo grado in $c$ $$c^2(m^2+1) - 2c(m^3+m) + m^4+2m^2-z^2=0$$
A questo punto il Delta dell'equazione in $c$ deve essere un quadrato perfetto. Abbiamo $$\Delta_c = 4m^2(m^2+1)^2 - 4(m^2+1)(m^4+2m^2-z^2) = 4(m^2+1)(z^2-m^2)$$

Ricordando che $m^2+1$ è un primo si ha che $z-m \equiv 0 \pmod {m^2+1}$ oppure $z+m \equiv 0 \pmod {m^2+1}$. Ora, se vale $z-m \equiv 0 \pmod {m^2+1}$ allora $z \ge m^2+1$ ma quindi $(m^2+1)^2+1=(n^2+1)(m^2+1) < (m^2+1)^2$ assurdo, quindi deve valere $z+m = r(m^2+1)$ per qualche $r$ intero positivo. Se $r \ge 2$ abbiamo che $z \ge 2m^2+2-m \ge m^2+2$ e quindi ragionando come prima riotteniamo un assurdo. Ne consegue banalmente che $z=m^2-m+1$. Da ciò si ottiene che $c=1$ oppure $c=2m-1$, ma chiaramente se $c=2m-1$ ottengo $n<0$, assurdo perchè lo abbiamo imposto positivo, quindi $c=1$. Ne segue che il più piccolo dei primi è pari da cui si ottiene banalmente $n=1$ poichè $n < m$ e quindi $m=2$ che porta alla conclusione che l'unico intero composto che soddisfa la caratteristica espressa nel testo è proprio $10$.

Rispondi

Chi c’è in linea

Visitano il forum: Nessuno e 5 ospiti