Matematyka.pl

Dane są liczby całkowite \(\displaystyle{ k>0, l>1, m \neq 0}\). Udowodnij, że zbiór dzielników pierwszych liczb postaci \(\displaystyle{ k\cdot l^n +m}\) jest nieskończony.

P.S. Następujący problem postawiłem sobie sam, a zmotywowała mnie do tego dyskusja w temacie "Trudna teoria liczb" oraz zadanie bodajże 31 ze Zwardonia 07 ; p. Wersja Zwardoniowa była "trochę" słabsza, bo tam było \(\displaystyle{ k=1}\) i \(\displaystyle{ m=-1}\), a dla \(\displaystyle{ l=2}\) i \(\displaystyle{ m=1}\) jest to twierdzenie dowodzące nieprawdziwości tego, co chciało być przepchnięte we wspomnianym wyżej temacie ).
EDIT: Dobra, źle zapamiętałem treść zad. 33 ze Zwardonia 07 . Tam teza była istotnie mocniejsza niż teza tego zadania dla \(\displaystyle{ k=1}\) i \(\displaystyle{ m=-1}\) .

Wygodne oznaczenia: (powiedzmy, że m jest ustalone przez całe zadanie, będzie krócej)
\(\displaystyle{ T(k,a) = \left\{ ka^n + m:n \in N \right\}}\)
\(\displaystyle{ P(X) = \left\{ p \in P: \exists x \in X, p|x \right\}}\)
Zachodzą oczywiste związki
\(\displaystyle{ T(ka^m,a^n) \subset T(k,a)}\) dla dowolnych m i n, oraz
\(\displaystyle{ X \subset Y \Rightarrow P(X) \subset P(Y)}\)
Możemy oczywiście założyć, że m i k są względnie pierwsze oraz m i a są względnie pierwsze.
Załóżmy wbrew tezie, że \(\displaystyle{ P(T(k,a)) = \left\{ p_1,p_2,...p_n \right\}}\).
Łatwo zauważyć, że \(\displaystyle{ a}\) nie może być podzielne przez \(\displaystyle{ p_i}\) dla żadnego \(\displaystyle{ i}\).
Niech \(\displaystyle{ v_{p_1}(ka+m) = s}\). Wtedy \(\displaystyle{ 0 \not\equiv ka+m \equiv ka(a^{l( \varphi (p_1^{s+1}))}) + m \ (mod \ p_1^{s+1}) (*)}\).
Liczby postaci \(\displaystyle{ ka(a^{l( \varphi (p_1^{s+1}))}) + m}\) to oczywiście \(\displaystyle{ T(ka,a^{ \varphi (p_1^{s+1})})}\), wobec tego \(\displaystyle{ P(T(ka,a^{ \varphi (p_1^{s+1})})) \subset P(T(k,a))}\), a z \(\displaystyle{ (*)}\) wynika, że wszystkie elementy \(\displaystyle{ T(ka,a^{ \varphi (p_1^{s+1})})}\) dzielą się przez \(\displaystyle{ p_1}\) w potędze najwyżej \(\displaystyle{ s}\). Powtarzając jeszcze \(\displaystyle{ (n-1)}\)-krotnie podobne rozumowanie, otrzymamy nieskończony podzbiór \(\displaystyle{ A}\) zbioru \(\displaystyle{ T(k,a)}\), spełniający następujący warunek: dla dowolnego \(\displaystyle{ i}\), istnieje takie \(\displaystyle{ w_i}\), że dla dowolnego elementu \(\displaystyle{ z \in A}\), \(\displaystyle{ v_{p_i}(z) \le w_i}\). Oznacza to jednak, że dowolny element \(\displaystyle{ z \in A}\) spełnia nierówność \(\displaystyle{ z \le \prod_{i=1}^{n} p_i ^{w_i}}\), co jest niedorzecznością. Sprzeczność kończy dowód.

Spoko rozwiązanie. Moje jest raczej istotnie różne, więc też je zaprezentuję.
Popatrzmy jak zachowuje się \(\displaystyle{ NWD(kl^n,m)}\) dla coraz większych \(\displaystyle{ n}\). To jest tak, że do pewnego momentu rośnie i dalej już przestaje (bo wiemy, że \(\displaystyle{ m\neq 0}\)). Oznaczmy je przez \(\displaystyle{ d}\) i niech pierwszy raz będzie osiągane dla wykładnika równego \(\displaystyle{ n_1}\). Udowodnimy, że zbiór liczb pierwszych, które nie dzielą \(\displaystyle{ d}\) i są dzielnikami liczb \(\displaystyle{ kl^n+m}\), gdzie \(\displaystyle{ n \geq n_1}\) jest nieskończony. Załóżmy przeciwnie, że jest on skończony i niech to będzie \(\displaystyle{ p_1, ..., p_r}\). Wtedy oczywiście jedynymi dzielnikami pierwszymi naszej liczby mogą być dzielniki pierwsze \(\displaystyle{ d}\) (i ich iloczyn nie przekracza \(\displaystyle{ d}\)) i liczby pierwsze z tego właśnie zbioru. Weźmy sobie jakąś bardzo dużą liczbę \(\displaystyle{ c}\) (jak duża nam będzie potrzebna, to się okaże później) i taką liczbę \(\displaystyle{ n_2}\), że \(\displaystyle{ kl^{n_2}+m>d(p_1p_2...p_r)^{c-1}}\). Rozpatrzmy liczby \(\displaystyle{ kl^{n_2}+m, kl^{n_2+1}+m, ..., kl^{n_2+r}+m}\). Na mocy naszej nierówności, dla każdej z tych liczb pewna liczba ze zbioru \(\displaystyle{ p_1, ..., p_r}\) musi ją dzielić w potędze równej co najmniej \(\displaystyle{ c}\). A skoro wzięliśmy sobie \(\displaystyle{ r+1}\) liczb, a interesujących nas liczb pierwszych mamy \(\displaystyle{ r}\), to istnieje takie \(\displaystyle{ i}\), że \(\displaystyle{ p_i^c}\) dzieli co najmniej 2 z tych liczb. Oznaczmy je przez \(\displaystyle{ kl^{n_2+x_1}+m}\) oraz \(\displaystyle{ kl^{n_2+x_2}+m}\) i niech \(\displaystyle{ x_2>x_1}\). Mamy wtedy \(\displaystyle{ p_i^c|kl^{n_1+x_2}-kl^{n_1+x_1}=kl^{n_1+x_1}(l^{x_2-x_1}-1)}\). Ale my wiemy, że \(\displaystyle{ p_i}\) nie dzieli \(\displaystyle{ kl^{n_1+x_1}}\), zatem \(\displaystyle{ p_i^c|l^{x_2-x_1}-1}\) z czego otrzymujemy \(\displaystyle{ p_i^c \leq l^{x_2-x_1}-1}\), ale w dodatku \(\displaystyle{ x_2-x_1 \leq r}\), zatem \(\displaystyle{ p_i^c \leq l^r-1}\), co jest oczywistą sprzecznością, gdyż możemy sobie wybrać dowolnie duże \(\displaystyle{ c}\).