Liczby Fibonacciego, NWD 2 liczb

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
PowerMan
Użytkownik
Użytkownik
Posty: 11
Rejestracja: 21 lis 2010, o 15:29
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 1 raz

Liczby Fibonacciego, NWD 2 liczb

Post autor: PowerMan »

Witam, mam 'problem' z dwoma zadaniami.
1. Przedstaw NWD(448,721) w postaci 448x + 721y czyli znajdź odpowiednie wartości liczb całkowitych x i y.
2. Wykaż, korzystając z algorytmu Euklidesa, że dwie kolejne liczby Fibonacciego są względnie pierwsze.


ad2. liczby są względnie pierwsze jeśli nwd wynosi 1. No tak, wynosi, ale to zapewnie nie wystarczy i trzeba to jakoś formalnie zapisać, i tu prosiłbym Was o pomoc.

ad1. wrzucamy 448 i 721 w alg. Euklidesa i wychodzi nam ze NWD=7, natomiast to nie o tą odpowiedź chodziło w zadaniu, więc jak trzeba to zrobić ?
hmm czy mamy tutaj użyć równania diofantycznego? byłoby 448x+721y=7 no ale jak teraz rozwiązać 1 równanie z 2ma niewiadomymi heh
Awatar użytkownika
Psiaczek
Użytkownik
Użytkownik
Posty: 1502
Rejestracja: 22 lis 2010, o 09:53
Płeć: Mężczyzna
Lokalizacja: Polska, Warmia, Olsztyn :)
Podziękował: 1 raz
Pomógł: 475 razy

Liczby Fibonacciego, NWD 2 liczb

Post autor: Psiaczek »

Ad.1 Pokaże ci na mniejszych liczbach, bo twojego sadystycznego przykładu gdzie jest osiem linijek przekształceń mi się nie chce

weźmy do algorytmu euklidesa liczby 23, 16 . Mamy

\(\displaystyle{ 23=1 \cdot 16+7, 16=2 \cdot 7+2, 7=3 \cdot 2+1,2=2 \cdot 1}\)

czyli wyszedł NWD=1 , chcielibyśmy znaleźć x,y takie ,że \(\displaystyle{ 23x+16y=1}\)

bierzesz linijkę algorytmu z ostatnią niezerową resztę i się cofasz, czyli:

\(\displaystyle{ 7=3 \cdot 2+1}\)

podstawiasz za 2 tutaj, 2 wyliczoną z poprzedniej linijki \(\displaystyle{ 16=2 \cdot 7+2}\), czyli \(\displaystyle{ 2=16-2 \cdot 7}\) i otrzymujesz:

\(\displaystyle{ 7=3 \cdot (16-2 \cdot 7)+1, 7=3 \cdot 16 -6 \cdot 7+1}\)

teraz z pierwszej linii \(\displaystyle{ 23=1 \cdot 16+7}\) bierzesz \(\displaystyle{ 7=23-1 \cdot 16}\) i wstawiasz wszędzie


otrzymujesz na końcu po przekształceniach \(\displaystyle{ 7 \cdot 23-10 \cdot 16=1}\)

czyli szukane współczynniki to \(\displaystyle{ x=7,y=-10}\)
PowerMan
Użytkownik
Użytkownik
Posty: 11
Rejestracja: 21 lis 2010, o 15:29
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 1 raz

Liczby Fibonacciego, NWD 2 liczb

Post autor: PowerMan »

Czyli dla 23 i 6 kolejne podstawienia są takie:
23x+16y=1
7=2*1+1
7=3*(16-2*7)+1
7=3*16-6*7+1
7=3*16-6*(23-1*16)+1
7=3*16-6*23+6*16+1

hmm i tu się gubię
Awatar użytkownika
Psiaczek
Użytkownik
Użytkownik
Posty: 1502
Rejestracja: 22 lis 2010, o 09:53
Płeć: Mężczyzna
Lokalizacja: Polska, Warmia, Olsztyn :)
Podziękował: 1 raz
Pomógł: 475 razy

Liczby Fibonacciego, NWD 2 liczb

Post autor: Psiaczek »

Sądząc po twojej odpowiedzi nic nie czaisz
jeszcze jeden przykład , krótszy niż poprzedni

liczby to:26,21


\(\displaystyle{ 26=1 \cdot 21+5}\)

\(\displaystyle{ 21=4 \cdot 5+1}\)

\(\displaystyle{ 5=5 \cdot 1}\)

szukamy a,b takich że \(\displaystyle{ 26a+21b=1}\)

wychodzimy od linijki gdzie ostatnia niezerowa reszta i wykorzystujemy wyższe linijki jeszcze raz ci mówię.

czyli do \(\displaystyle{ 21=4 \cdot 5+1}\) podstawiasz przekształconą pierwszą linijkę :

\(\displaystyle{ 5=26-1 \cdot 21}\)

otrzymujesz po przekszt.
\(\displaystyle{ 5 \cdot 21-4 \cdot 26=1}\)

znaleziono więc \(\displaystyle{ a=5, b=-4}\)
ODPOWIEDZ