Dowód z NWD i liczbami względnie pierwszymi

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
Octothorp
Użytkownik
Użytkownik
Posty: 10
Rejestracja: 20 sie 2014, o 13:38
Płeć: Mężczyzna
Podziękował: 1 raz

Dowód z NWD i liczbami względnie pierwszymi

Post autor: Octothorp »

Witam, mam do zrobienia takie zadanko:
Udowodnij, że jeśli \(\displaystyle{ a>b}\) oraz \(\displaystyle{ a}\) i \(\displaystyle{ b}\) są względnie pierwsze, to dla \(\displaystyle{ 0 \le m < n}\) zachodzi:
\(\displaystyle{ \nwd (a^{n} - b^{n}, a^{m} - b^{m}) = a^{\nwd(m, n)} - b^{\nwd(m, n)}}\).
Siedzę nad tym i nie mogę nic wykombinować. Wiem tylko tyle, że skoro \(\displaystyle{ a}\) i \(\displaystyle{ b}\) są względnie pierwsze to \(\displaystyle{ \nwd(a, b) = 1}\). Nakierowałby mnie ktoś na dobrą drogę? Proszę.
porfirion
Użytkownik
Użytkownik
Posty: 319
Rejestracja: 6 gru 2011, o 20:54
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 11 razy
Pomógł: 26 razy

Dowód z NWD i liczbami względnie pierwszymi

Post autor: porfirion »

Wynika z LTE.
... rs/LTE.pdf
szymonides
Użytkownik
Użytkownik
Posty: 78
Rejestracja: 24 lis 2009, o 17:22
Płeć: Mężczyzna
Podziękował: 4 razy

Dowód z NWD i liczbami względnie pierwszymi

Post autor: szymonides »

@porfirion:
Mógłbyś wyjaśnić z czego dokładnie?
Octothorp
Użytkownik
Użytkownik
Posty: 10
Rejestracja: 20 sie 2014, o 13:38
Płeć: Mężczyzna
Podziękował: 1 raz

Dowód z NWD i liczbami względnie pierwszymi

Post autor: Octothorp »

Dołączam się do prośby.
Awatar użytkownika
Ponewor
Moderator
Moderator
Posty: 2218
Rejestracja: 30 sty 2012, o 21:05
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 70 razy
Pomógł: 297 razy

Dowód z NWD i liczbami względnie pierwszymi

Post autor: Ponewor »

Bez LTE: spróbójcie podzielić przez siebie wyrażenia których \(\displaystyle{ nwd}\) szukacie, w wykładnikach ma się dziać właśnie algorytm Euklidesa.

edit bardziej znana jest łatwiejsza wersja tego zadania z \(\displaystyle{ b=1}\), być może warto ją rozwiązać na początek.
porfirion
Użytkownik
Użytkownik
Posty: 319
Rejestracja: 6 gru 2011, o 20:54
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 11 razy
Pomógł: 26 razy

Dowód z NWD i liczbami względnie pierwszymi

Post autor: porfirion »

Mój naprawdę duży błąd, za co przepraszam. Wynika z LTE tylko dla takich pierwszych \(\displaystyle{ p}\), że \(\displaystyle{ p|a-b}\): Na mocy LTE: \(\displaystyle{ v_{p}(a^{m}- b^{m})= v_{p}(a-b)+ v_{p}(m)}\), a \(\displaystyle{ v_{p}(a^{n}- b^{n})= v_{p}(a-b)+ v_{p}(n)}\) skąd na mocy definicji NWD, zaproponowana liczba jest podzielna przez właściwą potęgę \(\displaystyle{ p}\).

Ale gdy \(\displaystyle{ a-b}\) nie jest podzielne przez \(\displaystyle{ p}\), a mimo to \(\displaystyle{ p|(a^{m}- b^{m})}\) i \(\displaystyle{ p|(a^{n}- b^{n})}\) to LTE nie da kompletnie nic

Co ciekawe, nawet w pdfie który podesłałem pada:
Note. The most common mistake in using LTE is when you don’t check the
\(\displaystyle{ p | x - y}\) condition, so always remember to check it. Otherwise your solution
will be completely wrong.
Octothorp
Użytkownik
Użytkownik
Posty: 10
Rejestracja: 20 sie 2014, o 13:38
Płeć: Mężczyzna
Podziękował: 1 raz

Dowód z NWD i liczbami względnie pierwszymi

Post autor: Octothorp »

Znalazłem coś takiego: , ale nie rozumiem, jak dojść do tego równania: \(\displaystyle{ a^n-b^n =(a^m-b^m)(a^{n-m}b^0+a^{n-2m}b^m+\cdots+a^{n\bmod m}b^{n-m-n\bmod m})+b^{m\lfloor n/m\rfloor}(a^{n\bmod m}-b^{n\bmod m})}\)
i dlaczego potem z \(\displaystyle{ \nwd}\) usuwamy \(\displaystyle{ b^{m\lfloor n/m\rfloor}}\).
Awatar użytkownika
Ponewor
Moderator
Moderator
Posty: 2218
Rejestracja: 30 sty 2012, o 21:05
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 70 razy
Pomógł: 297 razy

Dowód z NWD i liczbami względnie pierwszymi

Post autor: Ponewor »

W zasadzie, to powinna wystarczyć taka tożsamość: \(\displaystyle{ a^{n}-b^{n}-\left(a^{m}-b^{m}\right)\left(a^{n - m}+b^{n - m}\right)=a^{n-m}b^{m}-a^{m}b^{n-m}}\)
i to powinno dalej pójść tak samo.

A dlaczego usuwamy \(\displaystyle{ b^{costam}}\)? Bo \(\displaystyle{ b^{costam}}\) jest względnie pierwsze z \(\displaystyle{ nwd}\). Dlaczego? Załóżmy, że nie jest. Wtedy mamy dzielnik pierwszy \(\displaystyle{ p}\), który dzieli \(\displaystyle{ a^{n}-b^{n}}\), oraz dzieli \(\displaystyle{ b^{costam}}\), czyli dzieli \(\displaystyle{ b}\), czyli dzieli też \(\displaystyle{ a}\), a to przeczy założeniu o względnej pierwszości.
ODPOWIEDZ