Forum matematyczne: miliony postów, setki tysięcy tematów, dziesiątki tysięcy użytkowników - pomożemy rozwiązać każde zadanie z matematyki https://matematyka.pl/
Niech P będzie wielomianem unormowanym stopnia 10 o współczynnikach całkowitych. Rozstrzygnąć, czy liczby P(0), P(1), ... P(100) mogą dawać parami różne reszty z dzielenia przez 101.
[Rozgrzewka OM][MIX][Teoria liczb] Teoria liczb
: 5 gru 2010, o 16:35
autor: arek1357
Na mój chłopski rozum chyba to nieprawda bo wyszedłby nam układ równań taki:
P(0)=a1
P(1)=a2
P(2)=a3
.............
P(100)=a101
gdzie a1 to reszty z dzielenia przez 101 czyli permutacja zbioru {0,1,2,3...100}
100 równań i tylko dziesięć niewiadomych: "współczynniki wielomianu P(x)"
Gdzieś po drodze by się to pożarło chyba...
[Rozgrzewka OM][MIX][Teoria liczb] Teoria liczb
: 5 gru 2010, o 16:59
autor: Ahhaa
mamy 101 liczb i 101 różnych reszt z dzielenia przez 101. Zakładamy, że liczby P(0),...,P(100) mogą dawać parami różne reszty z dzielenia przez 101. Musi więc być \(\displaystyle{ 101 | P(x)}\) dla pewnego \(\displaystyle{ x \in {0,1,...,100}}\). Stąd \(\displaystyle{ P(x)=101k ,k \in N}\) Korzystając z faktu, że dla dowolnych \(\displaystyle{ a,b \in N}\) zachodzi \(\displaystyle{ a-b|P(a)-P(b)}\) mielibyśmy: \(\displaystyle{ 101k | P(x)-P(0)}\) Jednak skoro \(\displaystyle{ P(x)}\) jest podzielne przez 101, to \(\displaystyle{ P(0)}\) nie jest (mieliśmy mieć różne reszty). Musi więc być \(\displaystyle{ x=0}\).
Czyli \(\displaystyle{ 101| P(0)}\) Wyraz wolny wielomianu nie wpływa więc na resztę z dzielenia przez 101.
ponieważ \(\displaystyle{ 100 \equiv -1 \pmod{101}}\) \(\displaystyle{ P(100) \equiv (-1)^{10}+(-1)^{9}+...+(-1)^1 \equiv 0 \pmod{101}}\)
Mamy więc \(\displaystyle{ P(100) \equiv P(0) \pmod{101}}\) sprzeczność z tezą.
Jeżeli ktoś potwierdzi, że rozwiązanie jest poprawne to wrzucę kolejne zadanie.
[Rozgrzewka OM][MIX][Teoria liczb] Teoria liczb
: 5 gru 2010, o 17:41
autor: timon92
Ahhaa pisze:\(\displaystyle{ 101k | P(x)-P(0)}\)
nieprawda
[Rozgrzewka OM][MIX][Teoria liczb] Teoria liczb
: 5 gru 2010, o 19:27
autor: MateuszL
To jest pierwszy błąd, ale nawet jakbyś wyratował swój wniosek, to dalej i tak zakładasz, że wszystkie współczynniki równe są 1, co jest dość odważnym założeniem.
[Rozgrzewka OM][MIX][Teoria liczb] Teoria liczb
: 5 gru 2010, o 19:40
autor: Ahhaa
Racja, bzdury nawypisywałem. Chętnie zobaczę poprawne rozwiązanie : D
[Rozgrzewka OM][MIX][Teoria liczb] Teoria liczb
: 6 gru 2010, o 21:15
autor: XMaS11
arek1357 pisze:Na mój chłopski rozum chyba to nieprawda bo wyszedłby nam układ równań taki:
P(0)=a1
P(1)=a2
P(2)=a3
.............
P(100)=a101
gdzie a1 to reszty z dzielenia przez 101 czyli permutacja zbioru {0,1,2,3...100}
100 równań i tylko dziesięć niewiadomych: "współczynniki wielomianu P(x)"
Gdzieś po drodze by się to pożarło chyba...
To mnie przekonuje, wrzucajcie następne zadania.
[Rozgrzewka OM][MIX][Teoria liczb] Teoria liczb
: 7 gru 2010, o 11:46
autor: Kartezjusz
Dokładnie,tylko na tym etapie też trzeba to dowieść...
[Rozgrzewka OM][MIX][Teoria liczb] Teoria liczb
: 7 gru 2010, o 16:59
autor: Prastaruszek
Ukryta treść:
Wszystkie równości modulo p=101.
LEMAT.Jakie wartości może przyjmowac wyrażenie: \(\displaystyle{ 1 ^{k}+...+100 ^{k}}\)? dla k=p-1 oczywiście z MTF jest to p-1. Dla k<p-2 niech q będzie generatorem dla p. Wówczas \(\displaystyle{ (q ^{k}-1 )(1 ^{k}+... +100 ^{k})=(q ^{k}-1)(1+q ^{k}+...q ^{(p-2)k})=q ^{(p-1)k}-1=0}\) Ostatnia równość z MTF. Tak więc, jako że q jest generatorem, q ^{k} jest różne od 1. Tak więc dla k<p-1 \(\displaystyle{ 1 ^{k}+...+100 ^{k}=0}\)
Załóżmy teraz, że istnieje taki wielomian P . Niech y takie że P(y)=0. Wówczas
P(0)+...+P(100)-P(y)= 1+2+...+100=101*50=0. Z drugiej strony Jak popatrzymy na tą sumę to jest to suma wyrażeń postaci \(\displaystyle{ a _{n} (1 ^{n}+...+100 ^{n})}\) [gdzie a _{n} jest odpowiednim współczynnikiem w wielomianie], oraz liczby \(\displaystyle{ 100a _{0}}\). Więc na mocy lematu mamy \(\displaystyle{ 100a _{0}=0}\), więc \(\displaystyle{ a _{0}=0}\). Tak więc wielomian P nie ma wyrazu wolnego. Zauważmy, że liczby P(P(0)), P(P(1)),...,P(P(100)) też musza być parami różne (gdyż operacja P(x) jest permutacją) tak więc P(P(0))+...+P(P(100))=1+...+100=0, a z drugiej strony ta suma to suma wyrażeń postaci \(\displaystyle{ b _{n} (1 ^{n} +...+100 ^{n})}\) [gdzie \(\displaystyle{ b _{n}}\) to odpowiednie współczynniki w wielomianie P(P(x))] Wyrazu wolnego nie było w P(x), więc w P(P(x)) też nie ma. Jest to unormowany wielomian stopnia 100, czyli p-1-szego. Na mocy lematu ta suma wynosi p-1+0+0+....+0=p-1. Tak więc
p-1=0. Sprzeczność.
Udowodnij, że liczb pierwszych jest nieskończenie wiele (najlepiej z Likenów).
[Rozgrzewka OM][MIX][Teoria liczb] Teoria liczb
: 7 gru 2010, o 17:12
autor: timon92
Prastaruszek pisze:Jak popatrzymy na tą sumę to jest to suma wyrażeń postaci \(\displaystyle{ a _{n} (1 ^{n}+...+100 ^{n})}\) [gdzie a _{n} jest odpowiednim współczynnikiem w wielomianie], oraz liczby \(\displaystyle{ 100a _{0}}\)
Nieprawda, \(\displaystyle{ a_0}\) jest 101
[Rozgrzewka OM][MIX][Teoria liczb] Teoria liczb
: 7 gru 2010, o 22:30
autor: Leszczu21
Nieprawda, że nieprawda, bo odejmowano P(y), gdzie P(y)=0 (mod 101). 101-1=100.
Chociaż, nieprawda, że nieprawda, że nieprawda, bo jeżeli odejmowano P(y), to ta suma jest (1^n +2^n +... +(y-1)^n+(y+1)^n+...+100^n). Chyba tak. Czy nie?
BTW. Co to likeny?
[Rozgrzewka OM][MIX][Teoria liczb] Teoria liczb
: 7 gru 2010, o 22:41
autor: smigol
Leszczu21, spytaj pana Edwarda Tutaja.
[Rozgrzewka OM][MIX][Teoria liczb] Teoria liczb
: 8 gru 2010, o 08:21
autor: Kartezjusz
Leszczu21 pisze:Nieprawda, że nieprawda, bo odejmowano P(y), gdzie P(y)=0 (mod 101). 101-1=100.
Chociaż, nieprawda, że nieprawda, że nieprawda, bo jeżeli odejmowano P(y), to ta suma jest (1^n +2^n +... +(y-1)^n+(y+1)^n+...+100^n). Chyba tak. Czy nie?
BTW. Co to likeny?
Rany julek zmień dilera! O czym teraz mówisz?
[Rozgrzewka OM][MIX][Teoria liczb] Teoria liczb
: 8 gru 2010, o 10:41
autor: Prastaruszek
Wiecie co, to jest prawda jak dokładniej pomyślicie. Ale nawet jakby nie była, to ta częśc dowodu jest bezużyteczna Potem z niej w praktyce nie korzystam, bo nawet jak zalożę że wyraz wolny mi się nie kasuje, to po zsumowaniu tych dwukrotnych złożeń dostaniemy jeszcze dodatkowo \(\displaystyle{ 101*b _{0}}\)
czyli 0 modulo p, czyli to nic nie zmienia... Możecie przejść do następnego zadania .
[Rozgrzewka OM][MIX][Teoria liczb] Teoria liczb
: 9 gru 2010, o 18:51
autor: jerzozwierz
Może taki dowodzik:
Rozważmy szereg \(\displaystyle{ \sum_{i=1}^{ \infty} \frac{1}{p_i}}\). Załóżmy, że jest on zbieżny. Wobec tego istnieje takie k, że \(\displaystyle{ \sum_{i=k}^{ \infty} \frac{1}{p_i} \le \frac{1}{2}}\). Liczby pierwsze mniejsze od \(\displaystyle{ p_k}\) nazwijmy małymi, a większe bądź równe dużymi. Weźmy teraz jakieś N, i oszacujmy, ile jest liczb mniejszych od N mających same małe dzielniki. Oczywiście każda liczba n może być przedstawiona jako \(\displaystyle{ n=ab^2}\), gdzie a jest bezkwadratowe. Część bezkwadratową możemy wybrać na najwyżej \(\displaystyle{ 2^k}\) sposobów, a \(\displaystyle{ b< \sqrt{N}}\). Wobec tego mamy najwyżej \(\displaystyle{ 2^k \sqrt{N}}\) liczb mniejszych od N z samymi małymi dzielnikami. Teraz ile liczb ma co najmniej jeden duży dzielnik pierwszy? Oczywiście najwyżej \(\displaystyle{ \frac{N}{p_{k+1}} + \frac{N}{p_{k+2}} + ... < \frac{N}{2}}\). Stąd nierówność \(\displaystyle{ 2^k \sqrt{N} + \frac{N}{2} \ge N}\), która dla dużych N się sypie. Nasz szereg jest rozbieżny, więc liczb pierwszych jest nieskończenie wiele.
Nowe:
Dana jest liczba pierwsza p. Udowodnij, że kongruencja \(\displaystyle{ ax^2 +bx+c \equiv 0 \ (mod \ p)}\) ma rozwiązanie wtedy i tylko wtedy, gdy \(\displaystyle{ b^2 - 4ac}\) jest resztą kwadratową.
No, oczywiście \(\displaystyle{ a \not\equiv 0 \ (mod \ p)}\)