Względna pierwszość

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
Bran
Użytkownik
Użytkownik
Posty: 421
Rejestracja: 19 lut 2019, o 19:30
Płeć: Mężczyzna
Lokalizacja: Polska
Podziękował: 163 razy
Pomógł: 16 razy

Względna pierwszość

Post autor: Bran »

Udowodnić, że jeśli \(\displaystyle{ NWD(a,b) = 1}\), to \(\displaystyle{ NWD(a+b,b) = 1}\), gdzie \(\displaystyle{ a,b \in \NN_+}\).
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: Względna pierwszość

Post autor: Premislav »

Wskazówka: algorytm Euklidesa.
Awatar użytkownika
Janusz Tracz
Użytkownik
Użytkownik
Posty: 4060
Rejestracja: 13 sie 2016, o 15:01
Płeć: Mężczyzna
Lokalizacja: hrubielowo
Podziękował: 79 razy
Pomógł: 1391 razy

Re: Względna pierwszość

Post autor: Janusz Tracz »

Albo (choć jest to nietrywialna własność) skorzystamy z

Kod: Zaznacz cały

https://pl.wikipedia.org/wiki/To%C5%BCsamo%C5%9B%C4%87_B%C3%A9zouta
. Założenie \(\displaystyle{ \NWD (a,b)=1}\) na jej gruncie oznacza, że \(\displaystyle{ \left( \exists x,y\in\ZZ\right)ax+by=1 }\) a pokazać mamy, że \(\displaystyle{ \left( \exists x',y'\in\ZZ\right)(a+b)x'+by'=1}\). A to można pokazać poprzez wskazanie palcem \(\displaystyle{ x'=x}\) oraz \(\displaystyle{ y'=y-x}\) (oczywiście zadbaliśmy o to by \(\displaystyle{ x',y'\in\ZZ}\)). Istnienie \(\displaystyle{ x',y'}\) które wykazaliśmy przez ich pokazania jest równoważne (znów tożsamości Bézouta) z \(\displaystyle{ \NWD (a+b,b)=1}\).
a4karo
Użytkownik
Użytkownik
Posty: 22173
Rejestracja: 15 maja 2011, o 20:55
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 38 razy
Pomógł: 3748 razy

Re: Względna pierwszość

Post autor: a4karo »

O rany?
A może tak: jeżeli `1<c=NWD(a+b,b)` to `c|a+b` i `c|b` więc `c|(a+b)-b=a` a stąd `NWD(a,b)\ge c`
Bran
Użytkownik
Użytkownik
Posty: 421
Rejestracja: 19 lut 2019, o 19:30
Płeć: Mężczyzna
Lokalizacja: Polska
Podziękował: 163 razy
Pomógł: 16 razy

Re: Względna pierwszość

Post autor: Bran »

a4karo pisze: 25 sty 2020, o 10:45 O rany?
A może tak: jeżeli `1<c=NWD(a+b,b)` to `c|a+b` i `c|b` więc `c|(a+b)-b=a` a stąd `NWD(a,b)\ge c`
Wydaje mi się, że udowodniłeś implikację w drugą stronę - czego nie zrozumiałem?

Premislav pisze: 25 sty 2020, o 04:45 Wskazówka: algorytm Euklidesa.
Liczymy NWD liczb \(\displaystyle{ a+b}\) i \(\displaystyle{ b}\)
Odejmując je dostajemy nową parę
\(\displaystyle{ b}\) i \(\displaystyle{ a}\)

\(\displaystyle{ a}\) i \(\displaystyle{ b}\) są względnie pierwsze z założenia. Tylko jeszcze nie wiem za bardzo dlaczego z tego wynika, że w poprzednim kroku też mieliśmy do czynienia z liczbami względnie pierwszymi. :(
Znaczy ja to widzę, ale na oko, to chłop w szpitalu umarł... Nie mam pomysłu jak to wykazać ponad wszelką wątpliwość.
a4karo
Użytkownik
Użytkownik
Posty: 22173
Rejestracja: 15 maja 2011, o 20:55
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 38 razy
Pomógł: 3748 razy

Re: Względna pierwszość

Post autor: a4karo »

Nie. Zrobiłem dowód nie wprost.
Ostatnio zmieniony 25 sty 2020, o 16:09 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości: nie wprost.
Awatar użytkownika
Janusz Tracz
Użytkownik
Użytkownik
Posty: 4060
Rejestracja: 13 sie 2016, o 15:01
Płeć: Mężczyzna
Lokalizacja: hrubielowo
Podziękował: 79 razy
Pomógł: 1391 razy

Re: Względna pierwszość

Post autor: Janusz Tracz »

Znaczy ja to widzę, ale na oko, to chłop w szpitalu umarł... Nie mam pomysłu jak to wykazać ponad wszelką wątpliwość.
Rozważ dwa zbiory \(\displaystyle{ \left\{ d\in\NN: d|a \wedge d|b\right\} }\) oraz \(\displaystyle{ \left\{ d\in\NN: d|(a+b) \wedge d|b\right\} }\) pokaż, że te zbiory są równe (z definicji). Skoro są równe to najmniejsze \(\displaystyle{ d}\) z pierwszego to jest tym samym \(\displaystyle{ d}\) z drugiego (a to najmniejsze \(\displaystyle{ d}\) dzielące te liczby umawiamy się nazywać \(\displaystyle{ \NWD}\)).
w jedną stronę:    
Bran
Użytkownik
Użytkownik
Posty: 421
Rejestracja: 19 lut 2019, o 19:30
Płeć: Mężczyzna
Lokalizacja: Polska
Podziękował: 163 razy
Pomógł: 16 razy

Re: Względna pierwszość

Post autor: Bran »

Janusz Tracz pisze: 26 sty 2020, o 12:41 Ustalmy \(\displaystyle{ d\in\left\{ d\in\NN: d|(a+b) \wedge d|b\right\} }\) czyli takie, że \(\displaystyle{ d|(a+b)}\) oraz \(\displaystyle{ d|b}\). Więc \(\displaystyle{ d|(a+b)-b}\) czyli \(\displaystyle{ d|a}\) zatem \(\displaystyle{ d\in\left\{ d\in\NN: d|a \wedge d|b\right\}}\). Tym samym pokazaliśmy, że \(\displaystyle{ \left\{ d\in\NN: d|a \wedge d|b\right\} \subseteq \left\{ d\in\NN: d|(a+b) \wedge d|b\right\}}\).
Tylko, ze właśnie to rozumowanie jest dla mnie najmniej zrozumiałe. Dlaczego jeśli jest podzielna przez dwie liczby to jest podzielna przez ich różnicę (a w drugą stronę sumę).
Awatar użytkownika
Janusz Tracz
Użytkownik
Użytkownik
Posty: 4060
Rejestracja: 13 sie 2016, o 15:01
Płeć: Mężczyzna
Lokalizacja: hrubielowo
Podziękował: 79 razy
Pomógł: 1391 razy

Re: Względna pierwszość

Post autor: Janusz Tracz »

A czy rozumiesz (nawet nieformalnie i intuicyjnie) czym jest \(\displaystyle{ |}\) i co oznacza zapis \(\displaystyle{ d|a}\). Oznacza to, że \(\displaystyle{ \frac{a}{d} }\) jest całkowite, więc jeśli również \(\displaystyle{ d|b}\) to \(\displaystyle{ \frac{b}{d} }\) też jest całkowite. A suma \(\displaystyle{ \frac{a}{d} + \frac{b}{d} = \frac{a+b}{d} }\) i różnica \(\displaystyle{ \frac{a}{d} - \frac{b}{d} = \frac{a-b}{d} }\) liczb całkowitych jest całkowita czyli \(\displaystyle{ d}\) dzieli sumę i różnicę.
Bran
Użytkownik
Użytkownik
Posty: 421
Rejestracja: 19 lut 2019, o 19:30
Płeć: Mężczyzna
Lokalizacja: Polska
Podziękował: 163 razy
Pomógł: 16 razy

Re: Względna pierwszość

Post autor: Bran »

Dziękuję :)
Tak tylko się upewnię:
Janusz Tracz pisze: 26 sty 2020, o 12:41 Skoro są równe to najmniejsze \(\displaystyle{ d}\) z pierwszego to jest tym samym \(\displaystyle{ d}\) z drugiego (a to najmniejsze \(\displaystyle{ d}\) dzielące te liczby umawiamy się nazywać \(\displaystyle{ \NWD}\)).
Czy tu nie powinno być największe \(\displaystyle{ d}\)?
Awatar użytkownika
Janusz Tracz
Użytkownik
Użytkownik
Posty: 4060
Rejestracja: 13 sie 2016, o 15:01
Płeć: Mężczyzna
Lokalizacja: hrubielowo
Podziękował: 79 razy
Pomógł: 1391 razy

Re: Względna pierwszość

Post autor: Janusz Tracz »

Czy tu nie powinno być największe \(\displaystyle{ d}\)
Tak oczywiście :oops:
ODPOWIEDZ