Liczby są względnie pierwsze udowodnij
- Niepokonana
- Użytkownik
- Posty: 1548
- Rejestracja: 4 sie 2019, o 11:12
- Płeć: Kobieta
- Lokalizacja: Polska
- Podziękował: 337 razy
- Pomógł: 20 razy
Liczby są względnie pierwsze udowodnij
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ę?
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ę?
-
- Użytkownik
- Posty: 23496
- Rejestracja: 8 kwie 2008, o 22:04
- Płeć: Mężczyzna
- Lokalizacja: piaski
- Podziękował: 1 raz
- Pomógł: 3264 razy
Re: Liczby są względnie pierwsze udowodnij
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ć.
Było to już tu na forum - możesz poszukać.
- Janusz Tracz
- Użytkownik
- Posty: 4071
- Rejestracja: 13 sie 2016, o 15:01
- Płeć: Mężczyzna
- Lokalizacja: hrubielowo
- Podziękował: 80 razy
- Pomógł: 1393 razy
Re: Liczby są względnie pierwsze udowodnij
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.
- Niepokonana
- Użytkownik
- Posty: 1548
- Rejestracja: 4 sie 2019, o 11:12
- Płeć: Kobieta
- Lokalizacja: Polska
- Podziękował: 337 razy
- Pomógł: 20 razy
- Janusz Tracz
- Użytkownik
- Posty: 4071
- Rejestracja: 13 sie 2016, o 15:01
- Płeć: Mężczyzna
- Lokalizacja: hrubielowo
- Podziękował: 80 razy
- Pomógł: 1393 razy
Re: Liczby są względnie pierwsze udowodnij
Rozważania nad parzystością i nieparzystością są nierozstrzygające (przynajmniej ja nie wiedzę sensownej kontynuacji ale może istnieje...). Ale:
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)}\)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ę?
- Niepokonana
- Użytkownik
- Posty: 1548
- Rejestracja: 4 sie 2019, o 11:12
- Płeć: Kobieta
- Lokalizacja: Polska
- Podziękował: 337 razy
- Pomógł: 20 razy
Re: Liczby są względnie pierwsze udowodnij
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ć?
i \(\displaystyle{ d|21n+4+14n+3=35n+7}\) Ale co z tym zrobić?
- Janusz Tracz
- Użytkownik
- Posty: 4071
- Rejestracja: 13 sie 2016, o 15:01
- Płeć: Mężczyzna
- Lokalizacja: hrubielowo
- Podziękował: 80 razy
- Pomógł: 1393 razy
Re: Liczby są względnie pierwsze udowodnij
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}\)
\(\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}\)
- 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
Re: Liczby są względnie pierwsze udowodnij
jak już się upierasz przy tym sposobie , z tego co piszesz wynika dalej: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ć?
\(\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...
- Niepokonana
- Użytkownik
- Posty: 1548
- Rejestracja: 4 sie 2019, o 11:12
- Płeć: Kobieta
- Lokalizacja: Polska
- Podziękował: 337 razy
- Pomógł: 20 razy
Re: Liczby są względnie pierwsze udowodnij
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
Nieważne