kongruencja, dowód z wielomianem
kongruencja, dowód z wielomianem
Pokazać, że jeśli f(a) jest wielomianem o współczynnikach całkowitych i \(\displaystyle{ f(a)\equiv k (\mod m)}\), to \(\displaystyle{ f(a + t m) \equiv k (\mod m)}\), gdzie k, t są liczbami całkowitymi.
- Justka
- Użytkownik
- Posty: 1680
- Rejestracja: 25 sty 2007, o 12:58
- Płeć: Kobieta
- Lokalizacja: Poznań
- Podziękował: 9 razy
- Pomógł: 579 razy
kongruencja, dowód z wielomianem
Niech naszym wielomianem będzie \(\displaystyle{ f(x)=\sum_{i=0}^{n} a_i x^i}\), gdzie \(\displaystyle{ a_n, ..., a_1,a_0 \in C}\)
Wiadomo, że \(\displaystyle{ f(x)=\sum_{i=0}^{n} a_i x^i \equiv k \ (\mod m)}\)
Rozważmy wielomian \(\displaystyle{ f(x+tm)=\sum_{i=0}^n a_i (x+tm)^i= \sum_{i=0}^{n} a_i (\sum_{i=0}^{n} {n \choose i} x^{n-i} (tm)^i)=\sum_{i=0}^{n} a_i x^i +\sum_{i=1}^{n}a_i {n \choose i} x^{n-i} (tm)^i}\), stąd ponieważ \(\displaystyle{ m|\sum_{i=1}^{n} a_i{n \choose i} x^{n-i} (tm)^i}\) to
\(\displaystyle{ f(x+tm)=\sum_{i=0}^n a_i (x+tm)^i \equiv k+0 \equiv k \ (\mod m)}\). QED.
ale pewności nie mam
Wiadomo, że \(\displaystyle{ f(x)=\sum_{i=0}^{n} a_i x^i \equiv k \ (\mod m)}\)
Rozważmy wielomian \(\displaystyle{ f(x+tm)=\sum_{i=0}^n a_i (x+tm)^i= \sum_{i=0}^{n} a_i (\sum_{i=0}^{n} {n \choose i} x^{n-i} (tm)^i)=\sum_{i=0}^{n} a_i x^i +\sum_{i=1}^{n}a_i {n \choose i} x^{n-i} (tm)^i}\), stąd ponieważ \(\displaystyle{ m|\sum_{i=1}^{n} a_i{n \choose i} x^{n-i} (tm)^i}\) to
\(\displaystyle{ f(x+tm)=\sum_{i=0}^n a_i (x+tm)^i \equiv k+0 \equiv k \ (\mod m)}\). QED.
ale pewności nie mam
- mm-aops
- Użytkownik
- Posty: 21
- Rejestracja: 4 kwie 2009, o 20:04
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Pomógł: 4 razy
kongruencja, dowód z wielomianem
dla kazdego i mamy
\(\displaystyle{ a_i x^i \equiv a_i (x+tm)^i}\) bo \(\displaystyle{ x+tm \equiv x}\) wszystko mod m oczywiscie
wiec\(\displaystyle{ \sum_{i=0}^{n} a_i x^i \equiv \sum_{i=0}^{n} a_i (x+tm)^i}\)
\(\displaystyle{ a_i x^i \equiv a_i (x+tm)^i}\) bo \(\displaystyle{ x+tm \equiv x}\) wszystko mod m oczywiscie
wiec\(\displaystyle{ \sum_{i=0}^{n} a_i x^i \equiv \sum_{i=0}^{n} a_i (x+tm)^i}\)