[MIX][Wielomiany][Teoria liczb] Wielomiany i 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
limes123
Użytkownik
Użytkownik
Posty: 666
Rejestracja: 21 sty 2008, o 22:48
Płeć: Mężczyzna
Lokalizacja: Ustroń
Podziękował: 26 razy
Pomógł: 93 razy

[MIX][Wielomiany][Teoria liczb] Wielomiany i teoria liczb

Post autor: limes123 »

Pomyslalem, ze warto zrobic tez taki temat, bo nierownosci sie zdecydowanie sprawdzily. Wrzucajcie jakies ciekawe zadania, lematy, twierdzenia itd. Zaczne od takich dwoch
1. Udowodnij, ze dla kazdej naturalnej liczby n istnieje naturalna liczba o n niezerowych cyfrach w zapisie dzisietnym, podzielna przez \(\displaystyle{ 5^n}\).
2. Wykazac, ze dla kazdego \(\displaystyle{ n\geq 2}\) wielomian \(\displaystyle{ W(x)=x^n+x^{n-1}+3}\) nie jest iloczynem dwoch wielomianow stopnia dodatniego o wspolczynnikach calkowitych.
Ostatnio zmieniony 29 sty 2009, o 13:55 przez limes123, łącznie zmieniany 1 raz.
frej

[MIX][Wielomiany][Teoria liczb] Wielomiany i teoria liczb

Post autor: frej »

1. Liczba musi składać się z dokładnie \(\displaystyle{ n}\) cyfr, tak?
Awatar użytkownika
limes123
Użytkownik
Użytkownik
Posty: 666
Rejestracja: 21 sty 2008, o 22:48
Płeć: Mężczyzna
Lokalizacja: Ustroń
Podziękował: 26 razy
Pomógł: 93 razy

[MIX][Wielomiany][Teoria liczb] Wielomiany i teoria liczb

Post autor: limes123 »

Tak.
Dumel
Użytkownik
Użytkownik
Posty: 2000
Rejestracja: 19 lut 2008, o 17:35
Płeć: Mężczyzna
Lokalizacja: Stare Pole/Kraków
Podziękował: 60 razy
Pomógł: 202 razy

[MIX][Wielomiany][Teoria liczb] Wielomiany i teoria liczb

Post autor: Dumel »

no to zad. 2:
zalozmy ze dla dodatnich \(\displaystyle{ a_i,b_j}\) zachodzi
\(\displaystyle{ x^n+x^{n-1}+3=(a_kx^k+...+a_0)(b_{n-k}x^{n-k}+...+b_0)}\) przy czym mozemy zalozyc ze \(\displaystyle{ k \le \frac{n}{2}}\). wspolczynik przy \(\displaystyle{ x^k}\) wynosi \(\displaystyle{ a_kb_0+A}\) gdzie \(\displaystyle{ A}\) to jakas tam liczba nieujemna, a wiec ten wspolczynnik jest dodatni czyli \(\displaystyle{ n-1=k \le \frac{n}{2}}\) stad mamy ze \(\displaystyle{ n \le 2}\) czyli z zalozenia \(\displaystyle{ n=2}\). latwo sprawdzic ze nie moze byc \(\displaystyle{ x^2+x+3=(ax+b)( \frac{1}{a}x+ \frac{3}{b})}\) bo wtedy zachodziloby \(\displaystyle{ \frac{3a}{b}+ \frac{b}{a}=1}\) a tak byc nie moze np na mocy AM-GM

dorzuce cos od siebie:
1. znalezc wszystkie wielomiany \(\displaystyle{ P(x)}\) o wsp. rzeczywistych spelniajace dla kazdego \(\displaystyle{ x}\):
\(\displaystyle{ (x+1)^3P(x-1)-(x-1)^3P(x+1)=4(x^2-1)P(x)}\)
2. \(\displaystyle{ p}\) jest nieparzysta liczba pierwsza. pokazac ze jesli dla pewnego \(\displaystyle{ n}\) zachodzi
\(\displaystyle{ p|n(n+1)(n+2)(n+3)+1}\) to dla pewnego \(\displaystyle{ m}\) mamy \(\displaystyle{ p|m^2-5}\)
Awatar użytkownika
limes123
Użytkownik
Użytkownik
Posty: 666
Rejestracja: 21 sty 2008, o 22:48
Płeć: Mężczyzna
Lokalizacja: Ustroń
Podziękował: 26 razy
Pomógł: 93 razy

[MIX][Wielomiany][Teoria liczb] Wielomiany i teoria liczb

Post autor: limes123 »

Inny sposob na zadanie drugie byl mniej wiecej taki:
zalozyc, ze sie da, wymnozyc i porownac wspolczynniki i wtedy dowodzilo sie prosta indukcja, ze wszsytkie sa podzielne przez 3. Na koniec zostawal jeszcze chyba przypadek jak jeden jest jednomianem ale to nie moze zachodzic, bo ten wielomian z zadania nie ma pierwiastkow calkowitych.
Dumel
Użytkownik
Użytkownik
Posty: 2000
Rejestracja: 19 lut 2008, o 17:35
Płeć: Mężczyzna
Lokalizacja: Stare Pole/Kraków
Podziękował: 60 razy
Pomógł: 202 razy

[MIX][Wielomiany][Teoria liczb] Wielomiany i teoria liczb

Post autor: Dumel »

ale chyba zalozyles ze wspolczynniki sa wymierne a tego nie ma w zadaniu
Awatar użytkownika
limes123
Użytkownik
Użytkownik
Posty: 666
Rejestracja: 21 sty 2008, o 22:48
Płeć: Mężczyzna
Lokalizacja: Ustroń
Podziękował: 26 razy
Pomógł: 93 razy

[MIX][Wielomiany][Teoria liczb] Wielomiany i teoria liczb

Post autor: limes123 »

Zrobilem blad w zadaniu (ale przy okazji poznalismy rozwiazanie trudniejszej wersji:p). Teraz juz ok.-- 29 stycznia 2009, 14:49 --Niech \(\displaystyle{ p}\) będzie niezerowym wielomianem o wspolczynnikach calkowitych. Czy istnieje nieskonczenie takich naturalnych n, ze \(\displaystyle{ p(n)}\) i \(\displaystyle{ 2^{2^{n}}+1}\) mają wspólny dzielnik pierwszy?
Dumel
Użytkownik
Użytkownik
Posty: 2000
Rejestracja: 19 lut 2008, o 17:35
Płeć: Mężczyzna
Lokalizacja: Stare Pole/Kraków
Podziękował: 60 razy
Pomógł: 202 razy

[MIX][Wielomiany][Teoria liczb] Wielomiany i teoria liczb

Post autor: Dumel »

limes123 pisze: 1. Udowodnij, ze dla kazdej naturalnej liczby n istnieje naturalna liczba o n niezerowych cyfrach w zapisie dzisietnym, podzielna przez \(\displaystyle{ 5^n}\).
sam sie troche zdziwilem ale bardzo latwo idzie indukcyjnie. dla \(\displaystyle{ n=1}\) jest ok i teraz zalozmy ze dla \(\displaystyle{ k-1}\) istnieje postulowana liczba: \(\displaystyle{ 5^{k-1}A}\). szukamy liczby postaci \(\displaystyle{ 5^{k-1}A+10^{k-1}c=5^{k-1}(A+2^{k-1}c)}\) przy czym \(\displaystyle{ c \in \{1,2,...,9 \}}\). no i teraz wystarczy sobie zrobic tabelke (mozna pewnie ladniej ale nie chcialo mi sie nad tym zastanawiac) zeby zobaczyc ze niezaleznie od reszt z dzielenia przez 5, ktore daja liczby \(\displaystyle{ A, 2^{k-1}}\) zawsze mozemy wybrac \(\displaystyle{ c}\) aby \(\displaystyle{ 5|A+2^{k-1}c}\) (wiecej: zawsze mozemy wybrac c z przedzialu 1-5. latwo tez oddolnie oszacowac liczbe postulowanych liczb na 2^n) ckd
Awatar użytkownika
limes123
Użytkownik
Użytkownik
Posty: 666
Rejestracja: 21 sty 2008, o 22:48
Płeć: Mężczyzna
Lokalizacja: Ustroń
Podziękował: 26 razy
Pomógł: 93 razy

[MIX][Wielomiany][Teoria liczb] Wielomiany i teoria liczb

Post autor: limes123 »

Bardzo dobrze jak pierwszy raz zobaczylem tez wydawalo mi sie trudne. Wystarczy wziac ta k-1 i dla k rozwazyc
1N
3N
5N
7N
9N
w zapisie dziesietnym, gdzie N jest ta k-1 cyfrowa podzielna przez \(\displaystyle{ 5^{k-1}}\). Skoro wszystkie daja rozne reszty z dzielenia przez 5 to jedna z nich jest podzielna przez \(\displaystyle{ 5^n}\) ckd. To moze jeszcze cos takiego
Niech \(\displaystyle{ d}\) bedzie liczba calkowita dodatnia, a \(\displaystyle{ S}\) zbiorem dodatnich liczb postaci \(\displaystyle{ x^2+dy^2}\) gdzie x i y sa nieujemne i calkowite. Wykazac, ze jesli \(\displaystyle{ a\in S}\) i \(\displaystyle{ b\in S}\) to \(\displaystyle{ ab\in S}\).
Dumel
Użytkownik
Użytkownik
Posty: 2000
Rejestracja: 19 lut 2008, o 17:35
Płeć: Mężczyzna
Lokalizacja: Stare Pole/Kraków
Podziękował: 60 razy
Pomógł: 202 razy

[MIX][Wielomiany][Teoria liczb] Wielomiany i teoria liczb

Post autor: Dumel »

nie bardzo rozumiem. po pierwsze, skąd wiesz że tam nigdzie sie nie pojawi 0, a po drugie liczby 1N,3N,5N,7N,9N nie musza miec wcale k cyfr
___
ludzie, nikt nie napisał ze w tym topicu moge sie wypowiadac tylko ja i limes123, nie krepujcie sie
Ostatnio zmieniony 29 sty 2009, o 17:26 przez Dumel, łącznie zmieniany 1 raz.
Awatar użytkownika
limes123
Użytkownik
Użytkownik
Posty: 666
Rejestracja: 21 sty 2008, o 22:48
Płeć: Mężczyzna
Lokalizacja: Ustroń
Podziękował: 26 razy
Pomógł: 93 razy

[MIX][Wielomiany][Teoria liczb] Wielomiany i teoria liczb

Post autor: limes123 »

Chodzi o \(\displaystyle{ \overline{1N}}\) itd (N jest zapisem dziesietnym tej liczby dla k-1 i pozniej dorzucamy jeszcze na poczatek te liczby 1,3,5...).

[Edit]
Dokladnie Niech inne osoby tez cos wrzuca
Wasilewski
Użytkownik
Użytkownik
Posty: 3921
Rejestracja: 10 gru 2007, o 20:10
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 36 razy
Pomógł: 1194 razy

[MIX][Wielomiany][Teoria liczb] Wielomiany i teoria liczb

Post autor: Wasilewski »

Ostatnie zadanie limesa:
\(\displaystyle{ (x_{1}^2 + dy_{1}^2)(x_{2}^2 + dy_{2}^2) = (x_{1}x_{2})^2 + (dy_{1}y_{2})^2 + d(y_{1}x_{2})^2 + d(y_{2}x_{1})^2 = \\ (x_{1}x_{2} + dy_{1}y_{2})^2 - 2d (x_{1}y_{2})(x_{2}y_{1}) + d(x_{1}y_{2})^2 + d(x_{2}y_{1})^2 = \\ (x_{1}x_{2} + dy_{1}y_{2})^2 + d(x_{1}y_{2} - x_{2}y_{1})^2 \in S}\)
Dumel pisze:2. \(\displaystyle{ p}\) jest nieparzysta liczba pierwsza. pokazac ze jesli dla pewnego \(\displaystyle{ n}\) zachodzi
\(\displaystyle{ p|n(n+1)(n+2)(n+3)+1}\) to dla pewnego \(\displaystyle{ m}\) mamy \(\displaystyle{ p|m^2-5}\)
\(\displaystyle{ n(n+1)(n+2)(n+3) + 1 = (n^2 + 3n+1)^2 \Rightarrow p\mid n^2 + 3n+1 \Rightarrow p\mid 4(n^2+3n+1) = 4n^2 + 12n + 9 - 5 = (2n+3)^2 - 5}\)
Dumel
Użytkownik
Użytkownik
Posty: 2000
Rejestracja: 19 lut 2008, o 17:35
Płeć: Mężczyzna
Lokalizacja: Stare Pole/Kraków
Podziękował: 60 razy
Pomógł: 202 razy

[MIX][Wielomiany][Teoria liczb] Wielomiany i teoria liczb

Post autor: Dumel »

świetnie, robilem tak samo bo inaczej chyba sie nie da

ma ktoś pomysł na to: ?
niech \(\displaystyle{ p>5}\) bedzie liczba pierwsza. pokazać ze w zbiorze \(\displaystyle{ \{p-n^2:n^2<p \}}\)
istnieja różne liczby \(\displaystyle{ a,b>1}\) takie ze \(\displaystyle{ a|b}\)

a ostatnie zadanie limesa to bylo cos prawie jak zad. 6. z zeszlorocznego finalu

[edit]
nie wpadlem na to bo w domysle przyjalem ze liczby a i b sa rozne (i pewnie o to chodzilo autorowi zadania bo bez sensu bylyby ograniczenia na liczbe p). poprawiam tresc
Ostatnio zmieniony 30 sty 2009, o 13:41 przez Dumel, łącznie zmieniany 1 raz.
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

[MIX][Wielomiany][Teoria liczb] Wielomiany i teoria liczb

Post autor: timon92 »

Dumel pisze: niech \(\displaystyle{ p>5}\) bedzie liczba pierwsza. pokazać ze w zbiorze \(\displaystyle{ \{p-n^2:n^2<p \}}\)
istnieja liczby \(\displaystyle{ a,b>1}\) takie ze \(\displaystyle{ a|b}\)
wystarczy przyjąć \(\displaystyle{ a=b=p-1}\)
Piotr Rutkowski
Użytkownik
Użytkownik
Posty: 2234
Rejestracja: 26 paź 2006, o 18:08
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 22 razy
Pomógł: 390 razy

[MIX][Wielomiany][Teoria liczb] Wielomiany i teoria liczb

Post autor: Piotr Rutkowski »

limes123 pisze: Niech \(\displaystyle{ p}\) będzie niezerowym wielomianem o wspolczynnikach calkowitych. Czy istnieje nieskonczenie takich naturalnych n, ze \(\displaystyle{ p(n)}\) i \(\displaystyle{ 2^{2^{n}}+1}\) mają wspólny dzielnik pierwszy?
Rozwiązanie zainspirowane staaarym zadaniem.

Udowodnimy, że nie istnieje.
Oznaczmy \(\displaystyle{ g=deg(p(x))}\)
Dodatkowo weźmy dowolną dodatnią liczbę \(\displaystyle{ a>a_{g}}\), gdzie \(\displaystyle{ a_{g}}\) jest współczynnikiem wielomianu przy najwyższej potędze. Wtedy
\(\displaystyle{ \exists_{r\in \mathbb{R_{+}}}\forall_{x\geq r} \ p(x)<ax^{g}}\)

Dalej zdefiniujmy funkcję \(\displaystyle{ D(n)}\) oznaczającą najmniejszy dzielnik pierwszy liczby naturalnej n.
Niech \(\displaystyle{ l}\) będzie dzielnikiem pierwszym \(\displaystyle{ a_{n}=2^{2^{n}}+1}\). W szczególności \(\displaystyle{ l\neq 2}\)
Niech \(\displaystyle{ b=ord_{2}l}\). Oczywiście \(\displaystyle{ 2^{2^{n}}\equiv -1 \ (modl)}\) czyli \(\displaystyle{ 2^{2^{n+1}}\equiv 1 \ (modl)}\)
Zatem \(\displaystyle{ (b\not |2^{n}) \wedge (b|2^{n+1})}\) czyli po prostu \(\displaystyle{ b=2^{n+1}}\)
Dodatkowo skoro \(\displaystyle{ (l,2)=1}\) to z MTF \(\displaystyle{ l|2^{l-1}-1}\)
Zateb \(\displaystyle{ b|l-1}\) czyli \(\displaystyle{ 2^{n+1}|l-1}\)
Zatem \(\displaystyle{ l=k*2^{n}+1}\)

Przechodzimy do rozwiązania zadania. Dla udowodnienia postulowanej tezy wystarczy udowodnić, że \(\displaystyle{ \exists_{n_{1}\in \mathbb{N}}\forall_{n\geq n_{1}} D(a_{n})>p(n)}\)
Korzystając z tego co udowodniliśmy wcześniej mamy \(\displaystyle{ D(a_{n})\geq k*2^{n}+1>k*2^{n}}\)
oraz \(\displaystyle{ p(n)<a*n^{g}}\)
Wystarczy zatem pokazać, że \(\displaystyle{ \lim_{n\to \infty} \frac{n^{g}}{2^{n}}=0}\)
Co jest prawdą, bo \(\displaystyle{ \lim_{n\to \infty}\frac{\frac{(n+1)^{g}}{2^{n+1}}}{\frac{n^{g}}{2^{n}}}=\lim_{n\to \infty}(1+\frac{1}{n})^{g}*\frac{1}{2}=\frac{1}{2}<1}\) co dowodzi wartości żądanej granicy i tezy naszego zadania. Q.E.D.

P.S. 6 z zeszłorocznego finału było chyba jednak trudniejsze
P.S.2 Nawet nie trzeba założenia o współczynnikach całkowitych, wystarcza informacja o tym, że w dla całkowitych argumentów przyjmuje wartości całkowite.
Ostatnio zmieniony 5 lut 2009, o 16:25 przez Piotr Rutkowski, łącznie zmieniany 1 raz.
ODPOWIEDZ