[Rozgrzewka OM][MIX][Teoria liczb] Teoria liczb

Zadania z kółek matematycznych lub obozów przygotowujących do OM. Problemy z minionych olimpiad i konkursów matematycznych.
Regulamin forum
Wszystkie tematy znajdujące się w tym dziale powinny być tagowane tj. posiadać przedrostek postaci [Nierówności], [Planimetria], itp.. Temat może posiadać wiele różnych tagów. Nazwa tematu nie może składać się z samych tagów.
Awatar użytkownika
jerzozwierz
Użytkownik
Użytkownik
Posty: 526
Rejestracja: 22 lut 2009, o 10:13
Płeć: Mężczyzna
Lokalizacja: Rzeszów
Podziękował: 8 razy
Pomógł: 42 razy

[Rozgrzewka OM][MIX][Teoria liczb] Teoria liczb

Post autor: jerzozwierz »

Co by się nikt nie poczuł pokrzywdzony


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.
Ostatnio zmieniony 20 maja 2012, o 13:32 przez Sylwek, łącznie zmieniany 3 razy.
Powód: Poprawa nazwy tematu.
Awatar użytkownika
arek1357
Użytkownik
Użytkownik
Posty: 5703
Rejestracja: 6 gru 2006, o 09:18
Płeć: Mężczyzna
Lokalizacja: blisko
Podziękował: 129 razy
Pomógł: 524 razy

[Rozgrzewka OM][MIX][Teoria liczb] Teoria liczb

Post 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...
Ahhaa
Użytkownik
Użytkownik
Posty: 68
Rejestracja: 14 paź 2010, o 22:39
Płeć: Mężczyzna
Lokalizacja: kraj walecznych obrońców krzyża
Pomógł: 3 razy

[Rozgrzewka OM][MIX][Teoria liczb] Teoria liczb

Post 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.
Awatar użytkownika
timon92
Użytkownik
Użytkownik
Posty: 1654
Rejestracja: 6 paź 2008, o 16:47
Płeć: Mężczyzna
Lokalizacja: Katowice
Podziękował: 7 razy
Pomógł: 472 razy

[Rozgrzewka OM][MIX][Teoria liczb] Teoria liczb

Post autor: timon92 »

Ahhaa pisze:\(\displaystyle{ 101k | P(x)-P(0)}\)
nieprawda
MateuszL
Użytkownik
Użytkownik
Posty: 61
Rejestracja: 1 lis 2009, o 17:20
Płeć: Mężczyzna
Lokalizacja: Gryfice
Pomógł: 3 razy

[Rozgrzewka OM][MIX][Teoria liczb] Teoria liczb

Post 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.
Ahhaa
Użytkownik
Użytkownik
Posty: 68
Rejestracja: 14 paź 2010, o 22:39
Płeć: Mężczyzna
Lokalizacja: kraj walecznych obrońców krzyża
Pomógł: 3 razy

[Rozgrzewka OM][MIX][Teoria liczb] Teoria liczb

Post autor: Ahhaa »

Racja, bzdury nawypisywałem. Chętnie zobaczę poprawne rozwiązanie : D
Awatar użytkownika
XMaS11
Użytkownik
Użytkownik
Posty: 382
Rejestracja: 6 mar 2008, o 21:40
Płeć: Mężczyzna
Lokalizacja: Suchedniów/Kielce
Podziękował: 5 razy
Pomógł: 47 razy

[Rozgrzewka OM][MIX][Teoria liczb] Teoria liczb

Post 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.
Kartezjusz
Użytkownik
Użytkownik
Posty: 7330
Rejestracja: 14 lut 2008, o 08:31
Płeć: Mężczyzna
Lokalizacja: Z Bielskia-Białej
Podziękował: 6 razy
Pomógł: 961 razy

[Rozgrzewka OM][MIX][Teoria liczb] Teoria liczb

Post autor: Kartezjusz »

Dokładnie,tylko na tym etapie też trzeba to dowieść...
Prastaruszek
Użytkownik
Użytkownik
Posty: 41
Rejestracja: 22 lip 2009, o 12:48
Płeć: Mężczyzna

[Rozgrzewka OM][MIX][Teoria liczb] Teoria liczb

Post autor: Prastaruszek »

Ukryta treść:    
Udowodnij, że liczb pierwszych jest nieskończenie wiele (najlepiej z Likenów).
Awatar użytkownika
timon92
Użytkownik
Użytkownik
Posty: 1654
Rejestracja: 6 paź 2008, o 16:47
Płeć: Mężczyzna
Lokalizacja: Katowice
Podziękował: 7 razy
Pomógł: 472 razy

[Rozgrzewka OM][MIX][Teoria liczb] Teoria liczb

Post 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
Leszczu21
Użytkownik
Użytkownik
Posty: 64
Rejestracja: 18 gru 2009, o 18:05
Płeć: Mężczyzna
Lokalizacja: Rz
Pomógł: 1 raz

[Rozgrzewka OM][MIX][Teoria liczb] Teoria liczb

Post 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?
Awatar użytkownika
smigol
Użytkownik
Użytkownik
Posty: 3454
Rejestracja: 20 paź 2007, o 23:10
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 89 razy
Pomógł: 353 razy

[Rozgrzewka OM][MIX][Teoria liczb] Teoria liczb

Post autor: smigol »

Leszczu21, spytaj pana Edwarda Tutaja.
Kartezjusz
Użytkownik
Użytkownik
Posty: 7330
Rejestracja: 14 lut 2008, o 08:31
Płeć: Mężczyzna
Lokalizacja: Z Bielskia-Białej
Podziękował: 6 razy
Pomógł: 961 razy

[Rozgrzewka OM][MIX][Teoria liczb] Teoria liczb

Post 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?
Prastaruszek
Użytkownik
Użytkownik
Posty: 41
Rejestracja: 22 lip 2009, o 12:48
Płeć: Mężczyzna

[Rozgrzewka OM][MIX][Teoria liczb] Teoria liczb

Post 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 .
Awatar użytkownika
jerzozwierz
Użytkownik
Użytkownik
Posty: 526
Rejestracja: 22 lut 2009, o 10:13
Płeć: Mężczyzna
Lokalizacja: Rzeszów
Podziękował: 8 razy
Pomógł: 42 razy

[Rozgrzewka OM][MIX][Teoria liczb] Teoria liczb

Post 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)}\)
ODPOWIEDZ