Algorytm Euklidesa,zastosowanie

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
Awatar użytkownika
xxDorianxx
Użytkownik
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

Post autor: xxDorianxx »

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 ;/
Ostatnio zmieniony 3 lip 2018, o 00:42 przez xxDorianxx, łącznie zmieniany 1 raz.
Awatar użytkownika
Premislav
Użytkownik
Użytkownik
Posty: 15685
Rejestracja: 17 sie 2012, o 13:12
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 195 razy
Pomógł: 5219 razy

Re: Algorytm Euklidesa,zastosowanie

Post autor: Premislav »

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
Awatar użytkownika
xxDorianxx
Użytkownik
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

Post autor: xxDorianxx »

Czy mógłbyś mi to wytłumaczyć dokładniej, nie wiem skąd to \(\displaystyle{ (3, 3x+4)=1}\)
Awatar użytkownika
Premislav
Użytkownik
Użytkownik
Posty: 15685
Rejestracja: 17 sie 2012, o 13:12
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 195 razy
Pomógł: 5219 razy

Re: Algorytm Euklidesa,zastosowanie

Post autor: Premislav »

\(\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)}\)
Awatar użytkownika
xxDorianxx
Użytkownik
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

Post autor: xxDorianxx »

I wszystko jasne,dzięki
ODPOWIEDZ