Witam wszystkich mam problem z następującym zadaniem.
Znajdź wszystkie liczby całkowite \(\displaystyle{ x}\), dla których wyrażenie \(\displaystyle{ \frac{7x+1}{3x+4}}\) ma wartość całkowitą.
Jak takie zadanie rozwiązać algorytmem Euklidesa?
Wiem jak działa i ja robiłem to tak:
\(\displaystyle{ NWD (7x+1,3x+4)=NWD(4x,3x+4)=NWD(x-4,2x+8)=NWD(x-4,x+12)=NWD(x-4,16)}\)
I nie wiem co dalej ;/
Algorytm Euklidesa,zastosowanie
- xxDorianxx
- Użytkownik
- Posty: 413
- Rejestracja: 1 paź 2016, o 17:06
- Płeć: Mężczyzna
- Lokalizacja: Rybnik
- Podziękował: 88 razy
- Pomógł: 22 razy
Algorytm Euklidesa,zastosowanie
Ostatnio zmieniony 3 lip 2018, o 00:42 przez xxDorianxx, łącznie zmieniany 1 raz.
- Premislav
- Użytkownik
- Posty: 15687
- Rejestracja: 17 sie 2012, o 13:12
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 196 razy
- Pomógł: 5220 razy
Re: Algorytm Euklidesa,zastosowanie
A ja robiłem to tak:
ponieważ \(\displaystyle{ (3, 3x+4)=1}\), więc
\(\displaystyle{ (7x+1, 3x+4)=(21x+3, 3x+4)=(3x-21,3x+4)=(-25, 3x+4)}\)
Z drugiej strony skoro ma być \(\displaystyle{ \frac{7x+1}{3x+4}\in \ZZ}\), to
\(\displaystyle{ (7x+1, 3+4)=3x+4}\), czyli \(\displaystyle{ 3x+4}\) dzieli \(\displaystyle{ -25=-1\cdot 5^2}\), a zatem nietrudno wywnioskować, że \(\displaystyle{ 3x+4=25 \vee 3x+4=-5}\)
i otrzymujemy dwa rozwiązania:
\(\displaystyle{ x=-3, \ x=7}\)
Z Bogiem, KW
ponieważ \(\displaystyle{ (3, 3x+4)=1}\), więc
\(\displaystyle{ (7x+1, 3x+4)=(21x+3, 3x+4)=(3x-21,3x+4)=(-25, 3x+4)}\)
Z drugiej strony skoro ma być \(\displaystyle{ \frac{7x+1}{3x+4}\in \ZZ}\), to
\(\displaystyle{ (7x+1, 3+4)=3x+4}\), czyli \(\displaystyle{ 3x+4}\) dzieli \(\displaystyle{ -25=-1\cdot 5^2}\), a zatem nietrudno wywnioskować, że \(\displaystyle{ 3x+4=25 \vee 3x+4=-5}\)
i otrzymujemy dwa rozwiązania:
\(\displaystyle{ x=-3, \ x=7}\)
Z Bogiem, KW
- xxDorianxx
- Użytkownik
- Posty: 413
- Rejestracja: 1 paź 2016, o 17:06
- Płeć: Mężczyzna
- Lokalizacja: Rybnik
- Podziękował: 88 razy
- Pomógł: 22 razy
Re: Algorytm Euklidesa,zastosowanie
Czy mógłbyś mi to wytłumaczyć dokładniej, nie wiem skąd to \(\displaystyle{ (3, 3x+4)=1}\)
- Premislav
- Użytkownik
- Posty: 15687
- Rejestracja: 17 sie 2012, o 13:12
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 196 razy
- Pomógł: 5220 razy
Re: Algorytm Euklidesa,zastosowanie
\(\displaystyle{ (a,b)}\) to skrótowy zapis \(\displaystyle{ \NWD(a,b)}\). Dla dowolnego \(\displaystyle{ x\in \ZZ}\) liczba \(\displaystyle{ 3x+4}\) daje resztę \(\displaystyle{ 1}\) z dzielenia przez \(\displaystyle{ 3}\), czyli nie dzieli się przez \(\displaystyle{ 3}\), a więc, z uwagi na to, że \(\displaystyle{ 3}\) jest liczbą pierwszą, dla dowolnego \(\displaystyle{ x\in \ZZ}\) jest \(\displaystyle{ (3, 3x+4)=1}\). Dalej skorzystałem z takiego prostego faktu:
jeśli \(\displaystyle{ (a,b)=1}\), to \(\displaystyle{ (c,b)=(ac, b)}\).
Stąd właśnie wziąłem \(\displaystyle{ (7x+1, 3x+4)=(21x+3, 3x+4)}\)
jeśli \(\displaystyle{ (a,b)=1}\), to \(\displaystyle{ (c,b)=(ac, b)}\).
Stąd właśnie wziąłem \(\displaystyle{ (7x+1, 3x+4)=(21x+3, 3x+4)}\)
- xxDorianxx
- Użytkownik
- Posty: 413
- Rejestracja: 1 paź 2016, o 17:06
- Płeć: Mężczyzna
- Lokalizacja: Rybnik
- Podziękował: 88 razy
- Pomógł: 22 razy