Podzielność modulo
- mortan517
- Użytkownik
- Posty: 3359
- Rejestracja: 6 lis 2011, o 15:38
- Płeć: Mężczyzna
- Lokalizacja: Krk
- Podziękował: 112 razy
- Pomógł: 662 razy
Podzielność modulo
Witam, mam pewien problem przy implementacji kodu. Muszę policzyć resztę z pewnego wyrażenia. Generalnie działanie postaci \(\displaystyle{ (x-1)^n \mod x^2}\). Czy da się to zrobić jakoś prościej, to znaczy nie podnosząc na starcie do n-tej potęgi?
- Premislav
- Użytkownik
- Posty: 15688
- Rejestracja: 17 sie 2012, o 13:12
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 196 razy
- Pomógł: 5221 razy
Re: Podzielność modulo
Na programowaniu się nie znam, mimo że niby chodziłem na programowanie obiektowe, nawet zdałem, natomiast rzeczywiście można to chyba nieco uprościć. Ze wzoru dwumianowego Newtona mamy
\(\displaystyle{ (x-1)^n= \sum_{k=0}^{n} {n \choose k}x^{k}(-1)^{n-k}}\)
i zauważmy, że wszystkie wyrazy tego rozwinięcia prócz dwóch pierwszych dzielą się przez \(\displaystyle{ x^2}\), zatem
\(\displaystyle{ (x-1)^n\equiv (-1)^n+nx(-1)^{n-1}\pmod{x^2}}\)
Jak \(\displaystyle{ n}\) jest ustalone (czy choćby ustalonej parzystości), zaś \(\displaystyle{ x}\) się zmienia, to jest z tego jakaś korzyść... Ale nie wiem, czy konkretnie coś to daje.
\(\displaystyle{ (x-1)^n= \sum_{k=0}^{n} {n \choose k}x^{k}(-1)^{n-k}}\)
i zauważmy, że wszystkie wyrazy tego rozwinięcia prócz dwóch pierwszych dzielą się przez \(\displaystyle{ x^2}\), zatem
\(\displaystyle{ (x-1)^n\equiv (-1)^n+nx(-1)^{n-1}\pmod{x^2}}\)
Jak \(\displaystyle{ n}\) jest ustalone (czy choćby ustalonej parzystości), zaś \(\displaystyle{ x}\) się zmienia, to jest z tego jakaś korzyść... Ale nie wiem, czy konkretnie coś to daje.
- mortan517
- Użytkownik
- Posty: 3359
- Rejestracja: 6 lis 2011, o 15:38
- Płeć: Mężczyzna
- Lokalizacja: Krk
- Podziękował: 112 razy
- Pomógł: 662 razy
Re: Podzielność modulo
Zatrzymałem się na zapisaniu sumy, nie wywnioskowałem, że faktycznie tylko 2 wyrazy będą resztą. Dokładnie o to mi chodziło. Dzięki za pomoc.