Liczby są względnie pierwsze udowodnij

Oddzielone od teorii liczb, proste problemy dotyczące zasad dzielenia itp.
Awatar użytkownika
Niepokonana
Użytkownik
Użytkownik
Posty: 1546
Rejestracja: 4 sie 2019, o 11:12
Płeć: Kobieta
Lokalizacja: Polska
Podziękował: 335 razy
Pomógł: 20 razy

Liczby są względnie pierwsze udowodnij

Post autor: Niepokonana »

Witam
Jest takie zadanie udowodnij, że \(\displaystyle{ 14n+3}\) i \(\displaystyle{ 21n+4}\) są liczbami względnie pierwszymi, gdzie \(\displaystyle{ n}\) jest liczbą naturalną. No to ja muszę wykazać, że ich największym wspólnym dzielnikiem jest \(\displaystyle{ 1}\).

Dla \(\displaystyle{ n}\) nieparzystego obie liczby są nieparzyste, czyli ich największy wspólny dzielnik to jest jakaś liczba nieparzysta \(\displaystyle{ d}\). W przypadku n parzystego jedna liczba jest nieparzysta, druga parzysta, co znowu daje \(\displaystyle{ d}\) nieparzyste.
Teraz zasadnicze pytanie co dalej. Skoro największy wspólny dzielnik \(\displaystyle{ d}\) dzieli obie te liczby, to powinien dzielić także ich różnicę i sumę. Dobrze myślę?
piasek101
Użytkownik
Użytkownik
Posty: 23493
Rejestracja: 8 kwie 2008, o 22:04
Płeć: Mężczyzna
Lokalizacja: piaski
Podziękował: 1 raz
Pomógł: 3263 razy

Re: Liczby są względnie pierwsze udowodnij

Post autor: piasek101 »

Opiera się na tym aby wykazać, że NWD tych liczb to 1. Czyli pokazaniu nieskracalności ułamka z nich zbudowanego.
Było to już tu na forum - możesz poszukać.
Awatar użytkownika
Janusz Tracz
Użytkownik
Użytkownik
Posty: 4054
Rejestracja: 13 sie 2016, o 15:01
Płeć: Mężczyzna
Lokalizacja: hrubielowo
Podziękował: 79 razy
Pomógł: 1389 razy

Re: Liczby są względnie pierwsze udowodnij

Post autor: Janusz Tracz »

Ustalmy \(\displaystyle{ n\in\NN}\), oraz rozważmy równanie diofantyczne \(\displaystyle{ x(14n+3)+y(21n+4)=1}\) aby takie równanie miało rozwiązanie konieczne jest by \(\displaystyle{ \NWD\left( 14n+3, 21n+4\right)|1 }\). Oczywiście \(\displaystyle{ \NWD\left( 14n+3, 21n+4\right)>0}\) więc jeśli ma zajść taka podzielność to musi zajść \(\displaystyle{ \NWD\left( 14n+3, 21n+4\right)=1}\). Jest to warunek konieczny istnienia rozwiązań rozważanego równania. Ale rozwiązania można podać \(\displaystyle{ x=3, y=-2}\) są dobre (wyznaczyłem się porównując wielomiany zmiennej \(\displaystyle{ n}\)). Warunek konieczny jest spełniony co dowodzi tezy.
Awatar użytkownika
Niepokonana
Użytkownik
Użytkownik
Posty: 1546
Rejestracja: 4 sie 2019, o 11:12
Płeć: Kobieta
Lokalizacja: Polska
Podziękował: 335 razy
Pomógł: 20 razy

Re: Liczby są względnie pierwsze udowodnij

Post autor: Niepokonana »

Ale ja chcę to sama zrobić, a nie przeczytać.
Awatar użytkownika
Janusz Tracz
Użytkownik
Użytkownik
Posty: 4054
Rejestracja: 13 sie 2016, o 15:01
Płeć: Mężczyzna
Lokalizacja: hrubielowo
Podziękował: 79 razy
Pomógł: 1389 razy

Re: Liczby są względnie pierwsze udowodnij

Post autor: Janusz Tracz »

Rozważania nad parzystością i nieparzystością są nierozstrzygające (przynajmniej ja nie wiedzę sensownej kontynuacji ale może istnieje...). Ale:
Skoro największy wspólny dzielnik \(\displaystyle{ d}\)
dzieli obie te liczby, to powinien dzielić także ich różnicę i sumę. Dobrze myślę?
to bardzo dobry trop (algorytm Euklidesa opisałaś). Zastosuj takie iteracyjne rozumowanie. Korzystać będziesz z wzoru \(\displaystyle{ \NWD(x,y)=\NWD(x,y+kx)}\)
Awatar użytkownika
Niepokonana
Użytkownik
Użytkownik
Posty: 1546
Rejestracja: 4 sie 2019, o 11:12
Płeć: Kobieta
Lokalizacja: Polska
Podziękował: 335 razy
Pomógł: 20 razy

Re: Liczby są względnie pierwsze udowodnij

Post autor: Niepokonana »

Ja sobie myślałam, że \(\displaystyle{ d|21n+4-14n-3=7n+1}\)
i \(\displaystyle{ d|21n+4+14n+3=35n+7}\) Ale co z tym zrobić?
Awatar użytkownika
Janusz Tracz
Użytkownik
Użytkownik
Posty: 4054
Rejestracja: 13 sie 2016, o 15:01
Płeć: Mężczyzna
Lokalizacja: hrubielowo
Podziękował: 79 razy
Pomógł: 1389 razy

Re: Liczby są względnie pierwsze udowodnij

Post autor: Janusz Tracz »

Trzeba trochę subtelniej dobierać sumy i różnice tak by prowadziło to do tego co chcemy. Rozważ implikacje:

\(\displaystyle{ 1)}\) \(\displaystyle{ d| 14n+3 \Rightarrow d| 3(14n+3) }\)

\(\displaystyle{ 2)}\) \(\displaystyle{ d| 21n+4 \Rightarrow d| -2(21n+4) }\)

\(\displaystyle{ 3)}\) Wynika z \(\displaystyle{ 1),2)}\), że \(\displaystyle{ d|3(14n+3)-2(21n+4)}\) co daje, że \(\displaystyle{ d|1}\)
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

Re: Liczby są względnie pierwsze udowodnij

Post autor: Psiaczek »

Niepokonana pisze: 18 gru 2019, o 21:43 Ja sobie myślałam, że \(\displaystyle{ d|21n+4-14n-3=7n+1}\)
i \(\displaystyle{ d|21n+4+14n+3=35n+7}\) Ale co z tym zrobić?
jak już się upierasz przy tym sposobie , z tego co piszesz wynika dalej:

\(\displaystyle{ d|5 \cdot (7n+1)=35n+5}\)

\(\displaystyle{ d|(35n+7)-(35n+5)=2}\)

stąd \(\displaystyle{ d=1}\) lub \(\displaystyle{ d=2}\) ale \(\displaystyle{ 14n+3}\) jest zawsze nieparzyste, zatem...
Awatar użytkownika
Niepokonana
Użytkownik
Użytkownik
Posty: 1546
Rejestracja: 4 sie 2019, o 11:12
Płeć: Kobieta
Lokalizacja: Polska
Podziękował: 335 razy
Pomógł: 20 razy

Re: Liczby są względnie pierwsze udowodnij

Post autor: Niepokonana »

Dziękuję Psiaczek, że zrobiłeś to za mnie zaraz po tym, jak napisałam, że chcę to zrobić sama ale z pomocą.

Nieważne
ODPOWIEDZ