Matematyka.pl

... sprowadza się do układu równań diofantycznych:
\(\displaystyle{ \begin{cases} 2n-1=a^2 \\ 3n-2=b^2 \end{cases}}\)
co upraszcza się do:
\(\displaystyle{ n= \frac{a^2+1}{2}= \frac{b^2+2}{3}}\)
dając pellopodobne równanie:
\(\displaystyle{ 3a^2-2b^2=1}\)
Najmniejszą naturalną parą jest \(\displaystyle{ a_1=b_1=1}\) co pomaga w znalezieniu kolejnych rozwiązań:
\(\displaystyle{ a_i \sqrt{3}+b_i \sqrt{2}=( \sqrt{3} + \sqrt{2} )^{2i-1}}\)
stąd szukane \(\displaystyle{ n}\) są postaci:
\(\displaystyle{ n= \frac{1}{2}\left( \frac{1}{12}\left[( \sqrt{3} + \sqrt{2} )^{2i-1}+( \sqrt{3} - \sqrt{2} )^{2i-1} \right]^2 +1 \right)}\) dla \(\displaystyle{ i \in \NN \setminus \left\{ 0,1\right\}}\)
Wartości \(\displaystyle{ n}\) dla \(\displaystyle{ i \in \left\{ 2,..,10\right\}}\) to :
\(\displaystyle{ 41, 3961 , 388081 , 38027921 , 3726348121 , 365144087881 , 35780394264161, \\
3506113493799841, 7366416376406081}\)

Najpierw zauważmy, że jeżeli \(\displaystyle{ n}\) jest liczbą pierwszą, to spełnia warunki zadania.
Załóżmy więc, że \(\displaystyle{ n = pq}\), gdzie \(\displaystyle{ 1 < p, q < n}\).
Wtedy, z treści zadania, mamy podzielności
\(\displaystyle{ (p-1)|(pq-1)}\) i \(\displaystyle{ (q-1)|(pq-1)}\).
Z tych podzielności wnioskujemy, że
\(\displaystyle{ (p-1)|\left(pq-1 - q(p-1)\right)}\) i \(\displaystyle{ (q-1)|\left(pq-1 - p(q-1)\right)}\), więc
\(\displaystyle{ (p-1)|(q-1)}\) i \(\displaystyle{ (q-1)|(p-1)}\), zatem \(\displaystyle{ p-1 = q-1}\), więc \(\displaystyle{ p=q}\).
Skoro dowolne dwa dzielniki właściwe liczby \(\displaystyle{ n}\) są równe, to znaczy, że ma ona dokładnie jeden dzielnik właściwy, więc jest kwadratem liczby pierwszej.

Odpowiedź: \(\displaystyle{ n}\) jest liczbą pierwszą lub kwadratem liczby pierwszej.

Mamy \(\displaystyle{ S(n)\equiv n\pmod{9}}\) i \(\displaystyle{ 9|1989,}\) tym bardziej \(\displaystyle{ 9|1989^{1989}}\), toteż \(\displaystyle{ 9|S\left( S\left( S\left( 1989^{1989}\right) \right) \right) .}\)
Dowodzimy, że \(\displaystyle{ S(S(S(1989^{1989})}\) jest odpowiednio małą liczbą, stąd natychmiast wyniknie, że jest ona równa \(\displaystyle{ 9}\).
Jeśli \(\displaystyle{ n<10^{k}}\), to \(\displaystyle{ S(n)\le 9k}\), jest to raczej oczywiste, gdyż wówczas \(\displaystyle{ n}\) ma nie więcej niż \(\displaystyle{ k}\) cyfr i największa możliwa cyfra to \(\displaystyle{ 9}\).
Zauważmy, że \(\displaystyle{ 1989^{1989}<10^{6630}}\), gdyż \(\displaystyle{ 1989^3<2000^3<10^{10}}\). Stąd \(\displaystyle{ S\left( 1989^{1989}\right)\le 9\cdot 6630}\), czyli \(\displaystyle{ S\left( 1989^{1989}\right)}\) ma nie więcej niż \(\displaystyle{ 5}\) cyfr, tj. jest mniejsza niż \(\displaystyle{ 10^5}\).
Analogicznie \(\displaystyle{ S\left( S\left( 1989^{1989}\right) \right)\le 9\cdot 5=45}\).
Największa możliwa suma cyfr liczby całkowitej dodatniej nieprzekraczającej \(\displaystyle{ 45}\) to \(\displaystyle{ 12=3+9}\), co można sprawdzić na palcach. Zatem
\(\displaystyle{ S\left(S\left( S\left( 1989^{1989}\right) \right)\right)\le 12}\), a ponieważ
\(\displaystyle{ 9|S\left( S\left( S\left( 1989^{1989}\right) \right) \right)}\), więc
\(\displaystyle{ S\left( S\left( S\left( 1989^{1989}\right) \right) \right)=9.}\)

1)
\(\displaystyle{ 2^w!=2^{2^{w}-1} \cdot L}\)
gdzie \(\displaystyle{ L}\) to pewna liczba nieparzysta.

2)
\(\displaystyle{ 2 ^{n-1} \left(2 ^{n-1}+1 \right) \cdot ... \cdot \left( 2 ^{n}-2\right) \left( 2 ^{n}-1\right) = \frac{ \left( 2 ^{n}-1\right)! }{ \left( 2 ^{n-1}-1\right)! }= \frac{ \frac{2^n!}{2^n} }{ \frac{2 ^{n-1}!}{2 ^{n-1}} } =\\= \frac{2 ^{n}!}{2 ^{n-1}! \cdot 2}= \frac{2^{2^{n}-1} \cdot L_2}{2^{2^{n-1}-1} \cdot L_1 \cdot 2} =2^{2^{n-1}-1} \cdot L}\)

3)
Aby w równaniu
\(\displaystyle{ k!=2 ^{n-1} \left(2 ^{n-1}+1 \right) \cdot ... \cdot \left( 2 ^{n}-2\right) \left( 2 ^{n}-1\right)\\
k!= 2^{2^{n-1}-1} \cdot L}\)
zgadzała się liczba dwójek (w rozkładzie na czynniki pierwsze) po lewej i prawej stronie równania, to możliwe są tylko dwie sytuacje: \(\displaystyle{ k=2 ^{n-1} \vee k=2 ^{n-1}+1}\)

4)
Sprawdzając małe \(\displaystyle{ n}\) mam rozwiązania:
\(\displaystyle{ n=1 \wedge k=1\\
n=2 \wedge k=3}\)
Dla \(\displaystyle{ n=3}\) brak rozwiązania
Przy większych \(\displaystyle{ n}\) równania:
a) \(\displaystyle{ 2^{n-1}!=2 ^{n-1} \left(2 ^{n-1}+1 \right) \cdot ... \cdot \left( 2 ^{n}-2\right) \left( 2 ^{n}-1\right)}\)
b) \(\displaystyle{ \left( 2^{n-1}+1\right) !=2 ^{n-1} \left(2 ^{n-1}+1 \right) \cdot ... \cdot \left( 2 ^{n}-2\right) \left( 2 ^{n}-1\right)}\)
nie mają rozwiązań.
Można powołać się na istnienie liczby pierwszej w przedziale \(\displaystyle{ \left\{ 2 ^{n-1}, ..., 2 \cdot 2 ^{n-1}\right\}}\) lub uprościć równania do postaci:
a) \(\displaystyle{ \frac{2 ^{n-2}!}{2^{2^{n-2}-1}} =\left(2 ^{n-1}+1 \right) \left(2 ^{n-1}+3 \right) \cdot ... \cdot \left(2 ^{n}-1 \right)}\)
b) \(\displaystyle{ \frac{2 ^{n-2}!}{2^{2^{n-2}-1}} = \left(2 ^{n-1}+3 \right) \cdot ... \cdot \left(2 ^{n}-1 \right)}\)
Teraz obie strony równań są iloczynami liczb nieparzystych, jednak po prawej stronie jest ich więcej niż po lewej i każdy z czynników strony prawej jest większy od największego czynnika strony lewej.

Mamy
\(\displaystyle{ a=b\left( \frac{1}{p-1}+\frac{2}{p-2}+\ldots+\frac{p-1}{1}\right)}\),
toteż
\(\displaystyle{ a-b+bp=b\left( \frac{1}{p-1}+\frac{2}{p-2}+\ldots+\frac{p-1}{1}{\red +p-1}\right) \ (*)}\)
Ponadto z tej pierwszej równości wymnożonej przez \(\displaystyle{ (p-1)!}\) i z zasadniczego tw. arytmetyki (wszak \(\displaystyle{ (a,b)=1}\)) łatwo widać, że \(\displaystyle{ b}\) jest dzielnikiem \(\displaystyle{ (p-1)!}\), a w związku z tym \(\displaystyle{ (b,p)=1}\).
Równość \(\displaystyle{ (*)}\) mnożymy stronami przez \(\displaystyle{ (p-1)!}\) i mamy
\(\displaystyle{ (p-1)!(a-b+bp)=b \sum_{k=1}^{p-1} \frac{k\cdot (p-1)!}{p-k}}\).
Skoro zaś \(\displaystyle{ (b,p)=1}\) oraz oczywiście \(\displaystyle{ ((p-1)!, p)=1}\), więc potrzeba i wystarcza wykazać, że
\(\displaystyle{ (p-1)\cdot (p-1)!+\sum_{k=1}^{p-1} \frac{k\cdot (p-1)!}{p-k}\equiv 0\pmod{p^3}}\)
Mamy:
\(\displaystyle{ \frac{k\cdot (p-1)!}{p-k}= \frac{(k-p+p)\cdot (p-1)!}{p-k}=-(p-1)!+ \frac{p\cdot (p-1)!}{p-k}}\),
toteż sumując to wszystko, dostajemy
\(\displaystyle{ (p-1)\cdot (p-1)!+\sum_{k=1}^{p-1} \frac{k\cdot (p-1)!}{p-k}=p\cdot \sum_{k=1}^{p-1} \frac{(p-1)!}{p-k}}\)
A zatem wystarczy udowodnić, że \(\displaystyle{ p^2\bigg| \sum_{k=1}^{p-1} \frac{(p-1)!}{p-k}}\)
i będzie po zadaniu.
W tym celu dobieramy w pary składniki \(\displaystyle{ \frac{(p-1)!}{p-k}}\) i \(\displaystyle{ \frac{(p-1)!}{k}}\) dla \(\displaystyle{ k\in\left\{ 1,2 \ldots \frac{p-1}{2}\right\}}\).
Mamy \(\displaystyle{ \frac{(p-1)!}{p-k}+\frac{(p-k)!}{k}=k \frac{(p-1)!}{k(p-k)} +(p-k) \frac{(p-1)!}{k(p-k)}=p\cdot \frac{(p-1)!}{k(p-k)}}\)
Stąd \(\displaystyle{ \sum_{k=1}^{p-1} \frac{(p-1)!}{p-k}= \sum_{j=1}^{\frac{p-1}{2}}p\cdot \frac{(p-1)!}{j(p-j)}=p \sum_{j=1}^{ \frac{p-1}{2} } \frac{(p-1)!}{j(p-j)}}\)
Niech teraz
\(\displaystyle{ \frac{(p-1)!}{j(p-j)}\equiv r\pmod{p}}\)
Po pomnożeniu tej kongruencji stronami przez \(\displaystyle{ j(p-j)}\) mamy
\(\displaystyle{ (p-1)!\equiv j(p-j)r\pmod{p}}\)
czyli (tw. Wilsona):
\(\displaystyle{ -1\equiv -j^2 r\pmod{p}\\ j^2 r\equiv 1\pmod{p}}\)
Zatem \(\displaystyle{ r}\) jest elementem odwrotnym do \(\displaystyle{ j^2}\) w \(\displaystyle{ \ZZ_p^{*}}\), czyli w sposób oczywisty \(\displaystyle{ r=i^2}\), gdzie \(\displaystyle{ i}\) jest elementem odwrotnym do \(\displaystyle{ j}\) w \(\displaystyle{ \ZZ_p^{*}}\). Ale ponieważ w \(\displaystyle{ \ZZ_p^{*}}\) jest \(\displaystyle{ i^2=(p-i)^2}\) i dokładnie jedna z tych liczb będzie w zbiorze \(\displaystyle{ \left\{ 1,2\ldots \frac{p-1}{2}\right\}}\), więc bez rozwodzenia się możemy zapisać:
\(\displaystyle{ \sum_{j=1}^{ \frac{p-1}{2} } \frac{(p-1)!}{j(p-j)}\equiv \sum_{j=1}^{\frac{p-1}{2}}j^2\pmod{p}}\)
Tymczasem ze znanego wzoru na sumę kwadratów \(\displaystyle{ n}\) pierwszych liczb całkowitych dodatnich mamy
\(\displaystyle{ \sum_{j=1}^{\frac{p-1}{2}}j^2= \frac{p \cdot \frac{p-1}{2}\cdot \frac{p+1}{2} }{6} \\ \frac{p \cdot \frac{p-1}{2}\cdot \frac{p+1}{2} }{6} \equiv 0\pmod{p}}\)
a w związku z tym istotnie \(\displaystyle{ p^2\bigg| \sum_{k=1}^{p-1} \frac{(p-1)!}{p-k}}\),
co kończy dowód.

BTW jak dla mnie istotne jest tylko założenie, że liczba pierwsza \(\displaystyle{ p}\) spełnia \(\displaystyle{ p>3}\) (nie zaobserwowałem, by mój dowód psuł się dla piątki), ale może czegoś nie widzę.

\(\displaystyle{ a_n=\prod_{i=0}^{n-1}(2^n-2^i)=2^{ \frac{(n-1)n}{2} } \prod_{i=1}^{n}(2^i-1)}\)
Ponadto \(\displaystyle{ a_{n+1}=2^{n}(2^{n+1}-1)a_n}\)

Sprawdzam kilka początkowych \(\displaystyle{ n}\) :
\(\displaystyle{ \prod_{i=0}^{1-1}(2^1-2^i)=1=1! \\
\prod_{i=0}^{2-1}(2^2-2^i)=2 \cdot 3=3! \\
\prod_{i=0}^{3-1}(2^3-2^i)=...=4! \cdot 7 \\
\prod_{i=0}^{4-1}(2^4-2^i)=...=7! \cdot 2^2 \\
\prod_{i=0}^{5-1}(2^5-2^i)=...=8! \cdot 2^3 \cdot 31 \\
\prod_{i=0}^{6-1}(2^6-2^i)=...=9! \cdot 2^8 \cdot 7 \cdot 31 \\
\prod_{i=0}^{7-1}(2^7-2^i)=...=9! \cdot 2^{14} \cdot 7 \cdot 31 \cdot 127\\
\prod_{i=0}^{8-1}(2^8-2^i)=...=10! \cdot 2^{19} \cdot 3 \cdot 7 \cdot 17 \cdot 31}\)
Z kilku narzucających się wyjaśnień braku rozwiązania równania dla większych \(\displaystyle{ n}\) podam takie:
Ilość czynników równych 31 rośnie szybciej niż czynników równych 17, gdyż każdą kolejną 31 generuje czynnik \(\displaystyle{ 2^5-1}\) pojawiający się w tylko liczbach \(\displaystyle{ a_{5m}}\), a każdą kolejną 17 generuje czynnik \(\displaystyle{ 2^4+1}\) pojawiający się tylko w liczbach \(\displaystyle{ a_{8m}}\). Skoro w silni
jest odwrotnie (tam ilość czynników równych 17 rośnie szybciej niż czynników równych 31) to równanie nie będzie miało rozwiązania. Dodatkowo: pierwsza 19 pojawia się dopiero w \(\displaystyle{ a_{18}}\) które zawiera czynniki \(\displaystyle{ 31^3}\) i \(\displaystyle{ 17^2}\).

Jeśli oznaczymy dla \(\displaystyle{ a\in \NN^+, \ a>1, \ p\in \PP: v_p(a)=x\text{ gdy }p^x|a\wedge p^{x+1}\nmid a}\), to mamy
\(\displaystyle{ v_2\left( \prod_{i=0}^{n-1}(2^n-2^i) \right) = \frac{n(n-1)}{2}}\)
oraz ze wzoru Legendre'a:
\(\displaystyle{ v_2(k!)= \sum_{i=1}^{\infty}\left\lfloor \frac k {2^i}\right\rfloor< \sum_{i=1}^{\infty}\frac k{2^i} =k}\), zatem musi być
\(\displaystyle{ k>\frac{n(n-1)}{2}}\), aby miało szansę zajść \(\displaystyle{ k!= \prod_{i=0}^{n-1}(2^n-2^i)}\)
Z drugiej strony łatwo udowodnić indukcyjnie, że
\(\displaystyle{ k!>\left( \frac k 3\right)^k}\), czyli ma być spełniona nierówność
\(\displaystyle{ \prod_{i=0}^{n-1}(2^n-2^i)>\left( \frac k 3\right)^k}\)
a ciąg \(\displaystyle{ a_k=\left( \frac k 3\right)^k}\) dla \(\displaystyle{ k\ge 1}\) jest rosnący:
\(\displaystyle{ a_{k+1}>a_k \Leftrightarrow (k+1)\cdot \left( 1+\frac 1 k\right)^k>3}\), co jest oczywiste, wszak \(\displaystyle{ \left( 1+\frac 1 k\right)^k\ge 2}\)
Czyli z uwagi na \(\displaystyle{ k>\frac{n(n-1)}{2}}\) musimy mieć:
\(\displaystyle{ \prod_{i=0}^{n-1}(2^n-2^i)>\left( \frac{n(n-1)}{6}\right)^{\frac{n(n-1)}{2}}}\)
Ponadto \(\displaystyle{ 2^n-2^i\le 2^n-1}\), więc tym bardziej
\(\displaystyle{ \left( 2^n-1\right)^n>\left( \frac{n(n-1)}{6}\right)^{\frac{n(n-1)}{2}}\\2^n-1>\left( \frac{n(n-1)}{6} \right)^{\frac{n-1}{2}}}\),
stąd jeśli \(\displaystyle{ n\ge 6}\), to musi być też:
\(\displaystyle{ 2^n-1>(n-1)^{\frac{n-1}{2}}}\)
czyli tym bardziej
\(\displaystyle{ 4^n>(n-1)^{n-1}}\)
co jest fałszem dla \(\displaystyle{ n\ge 7}\)
(\(\displaystyle{ 6^6\ge 4^7 \Leftrightarrow 3^6\ge 2^8}\) co jest oczywiste, bo \(\displaystyle{ 3^6=729}\) i \(\displaystyle{ 2^8=256}\), dalej indukcja i w kroku indukcyjnym wystarcza nierówność \(\displaystyle{ \frac{n^n}{(n-1)^{n-1}}>4}\), która jest oczywista nawet dla \(\displaystyle{ n\ge 4}\)).

Sprawdzamy ręcznie możliwość zajścia równości \(\displaystyle{ k!=\prod_{i=0}^{n-1}(2^n-2^i)}\) dla \(\displaystyle{ n\in \left\{ 1,2,3,4,5, 6\right\}}\)
i dostajemy rozwiązania \(\displaystyle{ k=1, \ n=1}\) oraz \(\displaystyle{ k=3, \ n=2}\).

Przyjmijmy na początek, że liczby naturalne to całkowite dodatnie. Zrobię trochę od Dudy strony. Przypuśćmy, że istnieją granice właściwe \(\displaystyle{ a= \lim_{n \to \infty}a_n, \ b= \lim_{n \to \infty}b_n}\) (łatwo widać, że albo obie istnieją, albo obie nie istnieją). Oczywiście z zależności rekurencyjnych wynika, że musi być \(\displaystyle{ a\ge 0, \ b\ge 0}\). Korzystając z ciągłości pierwiastka kwadratowego i tw. o arytmetyce granic, przechodzimy do granicy w równaniach rekurencyjnych, otrzymując:
\(\displaystyle{ \begin{cases} a=\sqrt{k^2+k+1+b} \\ b=\sqrt{k^2+k+1-a}\end{cases}}\)
Teraz podnosimy obie te równości stronami do kwadratu i odejmujemy drugą od pierwszej stronami, co daje:
\(\displaystyle{ a^2-b^2=a+b\\(a+b)(a-b-1)=0}\)
Zatem mamy \(\displaystyle{ a+b=0}\) lub \(\displaystyle{ a=b+1}\). W tym pierwszym przypadku musi być \(\displaystyle{ a=b=0}\), ale to prowadzi do sprzeczności, gdyż jest \(\displaystyle{ \sqrt{k^2+k+1}>0}\).
Czyli pozostaje \(\displaystyle{ a=b+1}\) i podstawiając tę zależność w równości
\(\displaystyle{ a=\sqrt{k^2+k+1+b}}\) oraz podnosząc do kwadratu i redukując, mamy
\(\displaystyle{ b^2+b=k^2+k\\(b-k)(b+k+1)=0}\)
a stąd (wszak \(\displaystyle{ b\ge 0, \ k\ge 0}\)) natychmiast dostajemy \(\displaystyle{ b=k}\), a więc \(\displaystyle{ a=k+1}\).
Czyli jeśli istnieją granice właściwe
\(\displaystyle{ a= \lim_{n \to \infty}a_n, \ b= \lim_{n \to \infty}b_n}\), to jest \(\displaystyle{ a=k+1, \ b=k}\).
Ponadto mamy
\(\displaystyle{ a_{n+1}-(k+1)=\sqrt{k^2+k+1+b_n}-(k+1)= \frac{b_n-k}{\sqrt{k^2+k+1+b_n}+(k+1)}}\)
czyli
\(\displaystyle{ (1.) \ \left| a_{n+1}-(k+1)\right| = \frac{\left| b_n-k\right| }{\sqrt{k^2+k+1+b_n}+(k+1)}}\)
Analogicznie mamy
\(\displaystyle{ b_{n+1}-k=\sqrt{k^2+k+1-a_n}-k= \frac{k+1-a_n}{\sqrt{k^2+k+1-a_n}+k}}\)
a zatem
\(\displaystyle{ (2.) \ \left| b_{n+1}-k\right|= \frac{|a_n-(k+1)|}{\sqrt{k^2+k+1-a_n}+k}}\)
Łącząc równości \(\displaystyle{ (1.), \ (2.)}\) oraz korzystając z oczywistych nierówności
\(\displaystyle{ \sqrt{k^2+k+1+b_n}+(k+1)\ge k+1, \ \sqrt{k^2+k+1-a_n}+k\ge k}\)
otrzymujemy, że
\(\displaystyle{ |a_{n+1}-(k+1)|\le \frac{|b_n-k|}{k+1}\le \frac{|a_{n-1}-(k+1)|}{k(k+1)}}\)
a stąd przez prościutką indukcję dostajemy, że
\(\displaystyle{ |a_{2n+1}-(k+1)|\le \frac{|a_1-(k+1)|}{k^n(k+1)^n}\\ \left| a_{2n}-(k+1)\right|\le \frac{|a_0-(k+1)|}{k^n(k+1)^n}}\)
Stąd natychmiast otrzymujemy, że
\(\displaystyle{ \lim_{n \to \infty}a_n=k+1}\) (granice wskazanych powyżej podciągów istnieją i są równe \(\displaystyle{ k+1}\)),
a wtedy \(\displaystyle{ \lim_{n \to \infty}b_n=k}\).

Natomiast gdybyśmy dopuścili \(\displaystyle{ k=0}\), to nie wszystkie wyrazy ciągu \(\displaystyle{ (b_n)}\) będą poprawnie określone, więc tę możliwość pomijam.