Metoda podstawiania i zależnosci

[mctl]

Mam problem ze znalezieniem wzoru ogólnego równania \(\displaystyle{ l_{n}=l_{n-1} * l_{n-2}}\) dla \(\displaystyle{ n>2}\) i \(\displaystyle{ l_{1}=l_{2}=2}\). Koniecznie metodą podstawiania.

Oraz... wykaż prawdziwość następujących zależności(wszystkie liczby m,x,y,z są całkowite);
(a) \(\displaystyle{ xz \equiv yz od{mz} x \equiv y od {m}}\) dla \(\displaystyle{ z \not = 0}\)

(b) \(\displaystyle{ xz \equiv yz od{m} x \equiv y od {m/gcd(z,m)}}\)

(c) \(\displaystyle{ x \equiv y od{mz} x \equiv y od {m}}\)

[Sir George]

Ba,... nie jest to metoda podstawiania, ale zauważ, że logarytmując stronami dostajesz, że \(\displaystyle{ \lg_2l_n}\) to n-ta liczba Fibonacci'ego

Co do zależności, to wynikają wprost z równoważnego zapisu:
\(\displaystyle{ a\equiv b\ (\mod c)\qquad \Leftrightarrow \qquad c|a-b}\)
tzn. c dzieli różnicę a-b

[mctl]

Ba,... nie jest to metoda podstawiania, ale zauważ, że logarytmując stronami dostajesz, że \(\displaystyle{ \lg_2l_n}\) to n-ta liczba Fibonacci'ego

hm można jaśniej to rozpisać? bo nie widze tego jakos...

[max]

Mamy:
\(\displaystyle{ \lg l_{n} = \lg (l_{n - 1}\cdot l_{n - 2})\\
\lg l_{n} = \lg l_{n - 1} + \lg l_{n - 2}}\)
oraz
\(\displaystyle{ \lg l_{1} = \lg l_{2} = \lg 2 = 1}\)
Już widać?

[mctl]

Hm ok no to wracając do tych kongruencji, w przykładzie (a) będziemy mieli:
\(\displaystyle{ mz|xz-yz m|x-y}\)
czyli\(\displaystyle{ mz|z(x-y) m|x-y}\) co jak widać jest oczywiste bo jeśli jakaś liczba m dzieli liczbę x-y to w szczególności zachodzi to dla tych liczb pomnożonych przez ten sam czynnik.(Czyli to mniej więcej mam )

Przykład (c):
Jeśli \(\displaystyle{ mz|x-y}\) to \(\displaystyle{ m|x-y}\). To też proste bo jeśli wiemy że liczba (x-y) dzieli się przez iloczyn liczb m i z to (chyba) oczywistym jest, że dzieli się również przez jedną z tych liczb.

...no i podpunkt b:
\(\displaystyle{ \frac{m}{gcd(z,m)}|x-y m|z(x-y)}\)
no i tu troche gorzej z uzasadnieniem, mogłby ktoś pomóc?

[max]

\(\displaystyle{ \gcd(z, m)| z}\)

[mctl]

Ale w tym drugim jak podstawimy z=42 i m=36 to ich gcd=6, wiec mamy gcd((36/6),42) czyli gcd(6,42) a to sie chyba 6 równa oO
W sumie nie kumam też w czym ten 1 wzorek ma pomóc

[max]

no oczywiście bzdurę napisałem...
powinno w drugim być:
\(\displaystyle{ \gcd\left(\frac{m}{\gcd(m, z)}, \frac{z}{\gcd(m, z)}\right) = 1}\)

a to pierwsze się przyda:
\(\displaystyle{ \frac{m}{\gcd(m, z)} \ \bigg| \ x - y\\
z\cdot \frac{m}{\gcd(m, z)} \ \bigg| \ z(x - y)}\)
więc:
\(\displaystyle{ \frac{m}{\gcd(m, z)}\cdot \gcd(m, z) \ \bigg| \ z(x - y)\\
m | z(x - y)}\)

i w drugą stronę:
\(\displaystyle{ m | z(x - y)\\
\frac{m}{\gcd(m, z)} \ \bigg| \ \frac{z}{\gcd(m, z)}\cdot (x - y)}\)
i z 'tego drugiego':
\(\displaystyle{ \frac{m}{\gcd(m, z)} \bigg| \ x - y}\)