Matematyka.pl

Niech \(\displaystyle{ w(m)}\) będzie największym nieparzystym dzielnikiem \(\displaystyle{ m}\). Udowodnić, że jeśli \(\displaystyle{ a}\) i \(\displaystyle{ b}\) są względnie pierwsze i \(\displaystyle{ a+w(b+1)}\) i \(\displaystyle{ b+ w(a+1)}\) są potęgami dwójki, to \(\displaystyle{ a+1}\) i \(\displaystyle{ b+1}\) też są potęgami dwójki.

W tym zadaniu trzeba zastosować rekurencję, wiemy, że: \(\displaystyle{ (a,b)=1}\)

\(\displaystyle{ a \wedge b}\) liczby nieparzyste... jedziemy:

z warunków zadania:

(*) \(\displaystyle{ a+1= 2^ra_{1}}\)

(**) \(\displaystyle{ b+1= 2^sb_{1}}\)

jeżeli założymy, że: \(\displaystyle{ a_{1}, b_{1}=1}\) to teza spełniona więc niech będą większe od jeden...

z warunków zadania mamy:

\(\displaystyle{ a+b_{1}=2^x}\)

\(\displaystyle{ b+a_{1}=2^y}\)

jak widać można iść dalej:

\(\displaystyle{ a_{1}-1=2^sa_{2} }\)

\(\displaystyle{ b_{1}-1=2^rb_{2} }\)

po podstawieniu do: (*) i (**) otrzymamy:

\(\displaystyle{ 2^ra_{1}+b_{1}-1=2^x }\)

\(\displaystyle{ 2^sb_{1}+a_{1}-1=2^y }\)

raz plus, raz minus raz r, raz s (dla n - parzystych inaczej, dla nieparzystych jeszcze inaczej)

Z obserwacji zapiszmy jak to będzie wyglądać po n krokach:

\(\displaystyle{ 2^ra_{2n+1}+b_{2n+1} -1=2^{x-n(r+s)}}\)

\(\displaystyle{ 2^sb_{2n+1}+a_{2n+1} -1=2^{y-n(r+s)}}\)

teraz dla parzystych nietrudno:

(x) \(\displaystyle{ 2^sa_{2n+2}+b_{2n+2} +1=2^{x-n(r+s)-r}}\)

(xx) \(\displaystyle{ 2^rb_{2n+2}+a_{2n+2} +1=2^{y-n(r+s)-s}}\)

teraz jedźmy rekurencję inaczej:

zauważmy, że:

\(\displaystyle{ a=2^ra_{1}-1}\)

\(\displaystyle{ a_{1}=2^sa_{2}+1}\)

niech jeszcze: \(\displaystyle{ a_{0}=a , b_{0}=b }\)

łatwo teraz wydedukować, że:

\(\displaystyle{ a_{2n+1}=2^sa_{2n+2}+1}\)

\(\displaystyle{ a_{2n}=2^sa_{2n+1}-1=2^r\left( 2^sa_{2n+2}+1\right)-1 }\)

Z tego mamy:

\(\displaystyle{ a_{2n}=2^{r+s}a_{2n+2}+2^r-1 }\)

lub:

\(\displaystyle{ a_{2n+2}= \frac{a_{2n}-2^r+1}{2^{r+s}} }\)

przez absolutną analogię otrzymamy:

\(\displaystyle{ b_{2n}=2^{r+s}b_{2n+2}+2^s-1 }\)

lub:

\(\displaystyle{ b_{2n+2}= \frac{b_{2n}-2^s+1}{2^{r+s}} }\)


teraz te powyższe podstawmy do: (x) i (xx) , po podstawieniu i skróceniu ładnie się skróci i otrzymamy:

\(\displaystyle{ 2^sa_{2n}+b_{2n}+1=2^{x-n(r+s)+r+s}}\)

oraz:

\(\displaystyle{ 2^rb_{2n}+a_{2n}+1=2^{y-n(r+s)+r+s}}\)

teraz weźmy równania z nieparzystymi indeksami:

\(\displaystyle{ 2^ra_{2n+1}+b_{2n+1} -1=2^{x-n(r+s)}}\)

\(\displaystyle{ 2^sb_{2n+1}+a_{2n+1} -1=2^{y-n(r+s)}}\)

zauważmy teraz, że dla pewnego: \(\displaystyle{ n=N }\)

\(\displaystyle{ a_{2N+1}=b_{2N+1}=1}\) - bo ten ciąg musi się kiedyś skończyć, więc będzie:

\(\displaystyle{ 2^r=2^{x-n(r+s)}}\)

\(\displaystyle{ 2^s=2^{y-n(r+s)}}\)

z tego mamy:

\(\displaystyle{ x=N(r+s)+r \wedge y=N(r+s)+s}\)

weźmy teraz te dwa równania:

\(\displaystyle{ 2^sa_{2n}+b_{2n}+1=2^{x-n(r+s)+r+s}}\)

oraz:

\(\displaystyle{ 2^rb_{2n}+a_{2n}+1=2^{y-n(r+s)+r+s}}\)

Podstawmy:

\(\displaystyle{ x=N(r+s)+r , y=N(r+s)+s , n=0 , a_{0}=a , b_{0}=b}\)

otrzymamy:

\(\displaystyle{ 2^sa+b+1=2^{N(r+s)+r+s}}\)

\(\displaystyle{ 2^rb+a+1=2^{N(r+s)+r+s}}\)


Wyliczmy z tego układu równań: \(\displaystyle{ a \wedge b}\)

bez rachunków napiszę wyniki:

\(\displaystyle{ a= \frac{2^{(N+1)(r+s)}-1}{2^{r+s}-1} \cdot \left( 2^r-1\right) =A \left( 2^r-1\right) }\)

\(\displaystyle{ b= \frac{2^{(N+1)(r+s)}-1}{2^{r+s}-1} \cdot \left( 2^s-1\right) =A \left( 2^s-1\right) }\)

ponieważ z założenia zadania: \(\displaystyle{ (a,b)=1 \Rightarrow A=1 \Rightarrow N=0 }\)

otrzymamy ostatecznie:

\(\displaystyle{ a=2^r-1}\)

\(\displaystyle{ b=2^s-1}\)

lub:

\(\displaystyle{ a+1=2^r}\)

\(\displaystyle{ b+1=2^s}\)

Cały każdy ciąg w tym zadaniu ma długość jeden...

cnd...