[Teoria liczb] Dzielniki n^2+1

[Swistak]

Hej, hej. Jest sobie takie o zadanko:
Udowodnij, że istnieje nieskończenie wiele liczb naturalnych \(\displaystyle{ n}\) takich, że \(\displaystyle{ n^2+1}\) nie ma dzielnika pierwszego większego od \(\displaystyle{ n}\).
Ile dowodów uda wam się wymyślić ? Ja wymyśliłem 1, przeczytałem wzorcówkę, a tam były jeszcze 2 inne . Dlatego zachęcam do wymyślenia jak największej liczby istotnie różnych dowodów ; p.

[KPR]

rozwiązanie 1:    

Każde \(\displaystyle{ n}\) postaci \(\displaystyle{ 4b^2+2b+1}\) (\(\displaystyle{ b\in\mathbb{N}}\)) spełnia warunki zadania. Wtedy \(\displaystyle{ n^2+1=(4b^2+2b+1)^2+1=16b^4+16a^3+12a^2+4a+2=2(4b^2+1)(2b^2+2b+1)}\). Ponieważ \(\displaystyle{ 2,\ 4b^2+1,\ 2b^2+2b+1}\) są mniejsze od \(\displaystyle{ n}\), to \(\displaystyle{ n^2+1}\) nie ma dzielnika pierwszego większego od \(\displaystyle{ n}\), c.n.d.

rozwiązanie 2:    

Niech \(\displaystyle{ n=2(5k+1)^2=50k^2+20k+2}\) (\(\displaystyle{ k\in\mathbb{N}}\)). Wtedy mamy \(\displaystyle{ n^2+1=4(5k+1)^4+1}\), co z tożsamości Sophie Germain wynosi \(\displaystyle{ (2(5k+1)^2+2(5k+1)+1)(2(5k+1)^2-2(5k+1)+1)= \\ =(50k^2+30k+5) (2(5k+1)^2-2(5k+1)+1)= \\ =5(10k^2+6+1)(2(5k+1)^2-2(5k+1)+1)}\)
Ponieważ \(\displaystyle{ 5,\ 10k^2+6+1,\ 2(5k+1)^2-2(5k+1)+1}\) są mniejsze od \(\displaystyle{ n}\), to \(\displaystyle{ n^2+1}\) nie ma dzielnika pierwszego większego od \(\displaystyle{ n}\), c.k.d.

[Damianito]

szkic rozwiązania 3.:    

Jeśli mamy różne liczby pierwsze \(\displaystyle{ p}\), \(\displaystyle{ q}\) postaci \(\displaystyle{ 4k+1}\) oraz \(\displaystyle{ 0<x\leq p}\) i \(\displaystyle{ 0<y\leq q}\) są takie, że \(\displaystyle{ p|x^2+1}\) oraz \(\displaystyle{ q|y^2+1}\) i weźmiemy z chińskiego tw. o resztach \(\displaystyle{ 0<n\leq pq}\) spełniające \(\displaystyle{ pq|n^2+1}\), to mamy \(\displaystyle{ n^2+1=pqM}\) z \(\displaystyle{ M<n}\). Żeby \(\displaystyle{ p}\) i \(\displaystyle{ q}\) nie były zbyt dużymi dzielnikami pierwszymi, wystarczy uzyskać \(\displaystyle{ n\neq x}\) i \(\displaystyle{ n\neq y}\), bo wtedy każda z nierówności \(\displaystyle{ 0<n\leq p}\), \(\displaystyle{ 0<n\leq q}\) prowadziłaby do sprzeczności.

[andkom]

Szkic rozwiązania 4:    

Niech \(\displaystyle{ n_1=1}\), \(\displaystyle{ n_2=7}\) oraz \(\displaystyle{ n_k=6n_{k-1}-n_{k-2}}\) dla k>2.
Podobnie niech \(\displaystyle{ m_1=1}\), \(\displaystyle{ m_2=5}\) oraz \(\displaystyle{ m_k=6m_{k-1}-m_{k-2}}\) dla k>2.
Łatwo pokazać (indukcja), że oba ciągi są rosnące, \(\displaystyle{ n_k>m_k}\) dla k>1 oraz \(\displaystyle{ n_k^2+1=2m_k^2}\).
To kończy sprawę, bo każdy dzielnik pierwszy \(\displaystyle{ n_k^2+1}\) jest dwójką lub dzielnikiem liczby \(\displaystyle{ m_k<n_k}\) (dla k>1).

I uwaga do tego rozwiązania:    

Podobnie można wyprodukować więcej rozwiązań rozważając inne równania Pella postaci \(\displaystyle{ n^2-\ell m^2=-1}\) (gdzie całkowite \(\displaystyle{ \ell>2}\) jest ustalone - ale nie każde jest dobre).