LVI OM - II - Zadanie 1

Zawody matematyczne:

LVI OM, 2004-2005

Etap:

Wyznaczyć wszystkie dodatnie liczby całkowite $n$ , dla których

$ n^n+1\ \textrm{oraz}\ (2n)^{2n}+1 $

są liczbami pierwszymi.

Rozwiązanie

Niech $a\geq 2$ , $m\geq 1$ będą liczbami całkowitymi. Wykażemy najpierw, że jeśli liczba $m$ ma dzielnik nieparzysty większy od 1, to liczba $a^m+1$ jest złożona. Istotnie: jeśli $l$ jest dzielnikiem nieparzystym liczby $m$ to $m=ld$ dla pewnej liczby całkowitej $d$ dodatniej oraz

$ a^{m}+1=(a^{d})^{l}+1=(a^{d}+1)\cdot((a^{d})^{l-1}-(a^{d})^{l-2}+\ldots-a^{d}+1). $

Z powyższego wzoru wynika, że liczba $a^{d}+1$ jest dzielnikiem liczby $a^{m}+1$ . Dla $l>1$ dzielnik ten jest większy od 1 i mniejszy od $a^{m}+1$ . Zatem liczba $a^{m}+1$ jest złożona.

Liczba $n=1$ spełnia warunki zadania: liczby $1^1+1=2$ , $2^{2}+1=5$ są liczbami pierwszymi. Załóżmy więc w dalszej części rozumowania, że $n\geq 2$ .

Jeśli liczba $n^{n}+1$ jest liczbą pierwszą, to $n$ nie ma dzielników nieparzystych większych od 1. Stąd wynika, że $n=2^k$ dla pewnej liczby całkowitej dodatniej $k$ . Wówczas

$ (1)\qquad n^{n}+1=2^{k\cdot 2^{k}}+1\ \text{oraz}\ (2n)^{2n}+1=2^{(k+1)\cdot 2^{k+1}}+1. $

Dla $k\geq 2$ co najmniej jedna z liczb $k\cdot 2^{k}$ , $(k+1)\cdot 2^{k+1}$ ma dzielnik nieparzysty większy od 1, a więc co najmniej jedna z liczb (1) jest złożona. Wobec tego musi być $k=1$ , czyli $n=2$ .

Pozostało upewnić się, że liczba $n=2$ spełnia warunki zadania: liczby $2^2+1=5$ oraz $4^4+1=257$ są liczbami pierwszymi.

Odpowiedź: $n=1$ lub $n=2$ .