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
Liczby Fibonacciego, NWD 2 liczb
- Psiaczek
- 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
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}\)
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}\)
-
- 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
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ę
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ę
- Psiaczek
- 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
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}\)
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}\)