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

[Dumel]

nie mam do tego wzorcowki. sam tez tego nie zrobilem, mialem nadzieje ze komuś sie uda

[Piotrusg]

To moge powiedziec ze to dziwne zadanie jest bo to jest funkcja N->N wiec moze by tak indukcje strzelic ? Poza tym to ze jest rosnaca to wg polowiczna sciema bo chodzi o to ze jest roznowartosciowa To pomysle nad tym moze sie cos uda rozkminic

[TomciO]

To równanie funkcyjne, chodziło o wyznaczenie wszystkich funkcji \(\displaystyle{ f: \mathbb{N} \rightarrow \mathbb{N}}\) rosnących i spełniających \(\displaystyle{ f(yf(x))=x^2f(xy)}\)

Wstawiając \(\displaystyle{ y=1}\) do równania dostajemy \(\displaystyle{ f(f(x))=x^2f(x)}\).
Wstawiając \(\displaystyle{ y=f(y)}\) mamy \(\displaystyle{ f(f(x)f(y))=x^2f(xf(y))=x^2y^2f(xy)}\).
Ale wstawiając \(\displaystyle{ x=xy}\) do pierwszego z powyższych równań dostajemy \(\displaystyle{ f(f(xy))=x^2y^2f(xy)}\). A zatem \(\displaystyle{ f(f(x)f(y))=f(f(xy))}\) co oznacza, że \(\displaystyle{ f(x)f(y)=f(xy)}\) ze względu na monotoniczność, a zatem również różnowartościowość funkcji \(\displaystyle{ f}\).
Dalej wykorzystamy już tylko powyższą równość oraz jeszcze \(\displaystyle{ f(f(x))=x^2f(x)}\).
Załóżmy, że istnieje taka liczba naturalna \(\displaystyle{ n}\), że \(\displaystyle{ f(n) < n^2}\). Wówczas \(\displaystyle{ f(f(n)) < f(n^2)=(f(n))^2}\) ze względu na to, że funkcja jest rosnąca. Ale przecież \(\displaystyle{ f(f(n)) = n^2f(n)}\), co oznacza, że \(\displaystyle{ n^2 < f(n)}\) czyli sprzeczność. A jeśli \(\displaystyle{ f(n) > n^2}\), to analogicznie \(\displaystyle{ n^2f(n) = f(f(n)) > f(n^2)=(f(n))^2}\), czyli \(\displaystyle{ n^2 > f(n)}\) i znowu sprzeczność. Co pokazuje, że \(\displaystyle{ f(n)=n^2}\) dla każdej liczby naturalnej \(\displaystyle{ n}\).

Jak widać monotoniczność to nie była ściema tylko dość istotnie się przydawała. Ale za to ściemą chyba było, że to z naturalnych w naturalne bo nigdzie tego specjalnie nie wykorzystałem.

[szablewskil]

1) Udowdnij że dla dowolnych liczb naturalnych m,n jeżeli mn+1 jest podzielne przez 24 to m+n również jest podzielne przez 24

2) Wyznacz pary liczb naturalnych (a,b) spełniające warunki:
\(\displaystyle{ a \ge b}\) i \(\displaystyle{ NWD(a,b)+NWW(a,b)+a+b=ab}\)

3)Niech a,b będą takimi liczbami naturalnymi że \(\displaystyle{ a|b+1}\) oraz \(\displaystyle{ b|a^{2}-2}\). Udowodnij że liczba \(\displaystyle{ \frac{b+1}{2}}\) jest kwadratem pewnej lcizby całkowitej

[Dumel]

zad. 2. zrobilem z rok temu i tak sie sklada ze mam je w jakims zeszycie wiec przytocze moje rozwiazanie:
\(\displaystyle{ x=(a,b)}\) (te nawiasy oznaczaja NWD jakby ktos nie wiedzial)
\(\displaystyle{ a=px, b=qx}\) przy czym \(\displaystyle{ (p,q)=1}\)
podstawiamy do rownania, wykozystujac rownosc \(\displaystyle{ NWW(a,b)= \frac{ab}{NWD(a,b)}}\)
z tego wyznaczamy: \(\displaystyle{ x= \frac{1+p+q+pq}{pq}}\), skad \(\displaystyle{ a=\frac{1+p+q+pq}{q}}\) i \(\displaystyle{ b=\frac{1+p+q+pq}{p}}\).
wstawiajac te wszystkie bochomazy do pierwotnego rownania otrzymamy tozsamosc, wiec wystarczy znalezc takie liczby wzglednie pierwsze p i q ze wyliczony \(\displaystyle{ x}\) jest liczba calkowita. dla \(\displaystyle{ p,q \ge 3}\) mamy \(\displaystyle{ x \le 1}\) wiec sprawdzamy recznie przypadki \(\displaystyle{ p=1,2,3}\), stad otrzymujemy trzy pary \(\displaystyle{ (p,q)}\): \(\displaystyle{ (1,2),(2,3),(1,1)}\) (pomijajac kolejnosc wyazow). wyliczamy w kazdym przypadku x i dostajemy 3 pary \(\displaystyle{ (a,b):(6,3),(6,4),(4,4)}\)

tylko przepisalem co mialem w zeszycie bez weryfikacji, ale mysle ze nie ma bledow

[matex_06]

Mógłby ktoś pokazać jak zaatakowac to zadanie?

Niech \(\displaystyle{ n \geq a_1>a_2>...>a_k}\) beda liczbami calkowitymi dodatnimi spelniajacymi \(\displaystyle{ NWW(a_i,a_j) \leq n}\) dla dowolnych roznych i,j z zbioru \(\displaystyle{ {1,2,...,k}}\). Udowodnij, ze \(\displaystyle{ ia_i \leq n}\) dla \(\displaystyle{ i=1,2,...,k}\).-- 12 lutego 2009, 07:45 --Ma ktos jakis pomysł na to zadanie?

[Sylwek]

6.63 z "Niebieskiego Pawłowskiego". Jakby ktoś miał sprytny pomysł na część 2) , to byłbym wdzięczny

Mamy wielomian \(\displaystyle{ W(x)=x^n+(k+1)x^{n-1}+(2k+1)x^{n-2}+\ldots+((n-1)k+1)x+nk+1}\), wykaż, że:
1) \(\displaystyle{ W(1-k)=n+1}\)

szkic:    

Łatwo sprawdzić, że: \(\displaystyle{ W(x)-n-1=(x-(1-k))(x^{n-1}+2x^{n-2}+3x^{n-3}+\ldots+(n-1)x+n)}\), dalej wiadomo

2) \(\displaystyle{ n \ge 3 \ \wedge \ 0 \neq k \in \mathbb{Z}}\), to \(\displaystyle{ W}\) nie ma pierwiastka całkowityego.

szkic:    

Posiłkując się pierwszą częścią zadania wystarczy pokazać, że równanie: \(\displaystyle{ (x-(1-k))(x^{n-1}+2x^{n-2}+3x^{n-3}+\ldots+(n-1)x+n)=-n-1}\) nie ma rozwiązania dla \(\displaystyle{ x}\) całkowitego, a to zrobiłem dość mechanicznie, tzn. najpierw przypadek gdy \(\displaystyle{ x \ge 0}\), potem rozdzielam na n parzyste i nieparzyste, oddzielnie sprawdzam dla \(\displaystyle{ x=-1}\), a potem ograniczam jakimiś nierównościami w zależności od parzystości n. Może jest ładniejszy sposób?

[MagdaW]

1. To może dodam kolejne zadanie: Rozwiąż w liczbach całkowitych dodatnich równanie: \(\displaystyle{ a^{3}=6b ^{2}+2}\) Niekoniecznie na finał, ale dosyć ciekawe.

[Gierol]

rownowaznie:
\(\displaystyle{ a^{3}=(b+1)^{3} + (1-b)^{3}}\)
zatem na mocy wielkiego twierdzenia fermata jedynymi rozwiazaniami moga byc pary \(\displaystyle{ (2;1),(2;-1)}\)
ofc znalem juz to zadanie

[snm]

Było na ostatnim Zwardoniu zdaje się

[arek1357]

A ja myślę żeby w tym zadaniu z funkcjami znaleźdź rozszerzyć dziedzinę do wszystkich rzeczywistych znaleźdź wszystkie funkcje spełaniające tą równość f(yf(x))=xxf(xy)

a potem zawęzić dziedzinę spowrotem do naturalnych i wybrać funkcję która pasuje do warunków zadania:
mi wyszły 3 funkcje: f(x)=0 , f(x)=1/x i f(x)=xx widać że pasuje tylko ta ostatnia...

[XMaS11]

To ja jeszcze rzucę fajne zadanko:
wyznaczyć wszystkie dodatnie liczby całkowite \(\displaystyle{ n}\) takie, że:
\(\displaystyle{ n^2 | 3^n + 1}\).

[Piotr Rutkowski]

To ja jeszcze rzucę fajne zadanko:
wyznaczyć wszystkie dodatnie liczby całkowite \(\displaystyle{ n}\) takie, że:
\(\displaystyle{ n^2 | 3^n + 1}\).

Niech \(\displaystyle{ p}\) będzie najmniejszym dzielnikiem pierwszym liczby \(\displaystyle{ n>1}\)
Niech \(\displaystyle{ r=ord_{3}p}\)
zatem \(\displaystyle{ r|2n}\) oraz \(\displaystyle{ r|p-1}\) bo \(\displaystyle{ p\neq 2}\) i \(\displaystyle{ p\neq 3}\) (w pierwszym przypadku 4 musiałoby dzielić \(\displaystyle{ 3^{2x}+1\equiv 2 (mod4)}\), a w drugim \(\displaystyle{ 3|1}\))
Zatem \(\displaystyle{ r\leq p-1<p}\) jesli r jest nieparzyste to \(\displaystyle{ (r|2n)\Rightarrow (r|n)}\) i sprzeczność w wyborem p
Jeśli \(\displaystyle{ r=2r_{1}}\) to \(\displaystyle{ r_{1}|n}\) oraz \(\displaystyle{ r_{1}<2r_{1}\leq p-1 <p}\), również sprzeczność, zatem jedynym n spełniającym warunki zadania jest \(\displaystyle{ n=1}\)

[limes123]

No to moze jeszcze takie
\(\displaystyle{ n^2|2^n+1}\). To zadanie jest trudne, wiec wrzuce jeszcze jedno, zeby nie blokowac tematu;p
Dla kazdego naturalnego k>1 istnieje r takie, ze \(\displaystyle{ k|[r^n]+1}\) dla kazdego n naturalnego.

[XMaS11]

Zad. Wyznaczyć wszystkie liczby całkowite dodatnie \(\displaystyle{ n}\) takie, że \(\displaystyle{ n^2|2^n+1}\).
Rozwiązanie:
Lemat 1.
Dana jest liczba naturalna \(\displaystyle{ m}\) niepodzielna przez \(\displaystyle{ 3}\) oraz liczba \(\displaystyle{ l}\) taka, że:
\(\displaystyle{ 3^{2l} | 2^{3^lm} + 1}\). Wtedy prawdziwa jest następująca podzielność:
\(\displaystyle{ 3^{2l} | 2^{3^l} + 1}\).

Dowód:    

Po pierwsze: \(\displaystyle{ \varphi(3^{2l})=2 \cdot {3^{2l-1}}\).
Po drugie każda liczba \(\displaystyle{ a}\) taka, że \(\displaystyle{ 3^{2l} | 2^a - 1}\) jest parzysta.
Niech \(\displaystyle{ d}\) będzie najmniejszą liczbą naturalną spełniającą warunek :
\(\displaystyle{ 3^{2l}|2^d-1}\).
Oczywiście zachodzi : \(\displaystyle{ d|2 \cdot 3^{2l-1}}\), a ponieważ \(\displaystyle{ d}\) jest parzyste, to dostajemy: \(\displaystyle{ d=2 \cdot 3^k}\) dla pewnego całkowitego \(\displaystyle{ k}\). Stąd natychmiastowy wniosek, że \(\displaystyle{ 3^k}\) jest najmniejszą liczbą taką, że \(\displaystyle{ 3^{2l}|2^{3^k} + 1}\), oraz dla każdej liczby \(\displaystyle{ b}\) takiej, że \(\displaystyle{ 3^{2l}|2^b+1}\) zachodzi \(\displaystyle{ 3^k|b}\).
Teraz przechodząc do dowodu lematu:
\(\displaystyle{ 3^k|3^lm}\), co (na mocy tego, że \(\displaystyle{ m}\) jest niepodzielne przez \(\displaystyle{ 3}\)) pociąga za sobą \(\displaystyle{ 3^k|3^l}\), i dostajemy to co chcieliśmy (bo \(\displaystyle{ -1}\) podniesiona do nieparzystej potęgi daje \(\displaystyle{ -1}\)).

Lemat 2.
Jeśli dla pewnego naturalnego \(\displaystyle{ n}\) największą liczbą \(\displaystyle{ k}\) taką, że \(\displaystyle{ 3^k|2^{3^n}+1}\) jest \(\displaystyle{ k=2n}\), to dla każdego \(\displaystyle{ m>n}\) następująca podzielność: \(\displaystyle{ 3^{2m}|2^{3^m}+1}\) jest fałszywa.

Dowód:    

Niech \(\displaystyle{ f(m)}\) oznacza największą liczbę \(\displaystyle{ k}\) taką, że \(\displaystyle{ 3^k|2^{3^m}+1}\).
\(\displaystyle{ 2^{3^{m+1}}+1=(2^{3^m}+1)(4^{3^m}-2^{3^m}+1)}\)
Jednakże \(\displaystyle{ (4^{3^m}-2^{3^m}+1) \equiv 3 (mod 9)}\) co pociąga za sobą \(\displaystyle{ f(m+1)=f(m)+1}\).
Fałszywość tezy oznaczałaby, że dla pewnego \(\displaystyle{ a}\) mielibyśmy \(\displaystyle{ f(a)+1=f(a+1) \ge f(a)+2}\), w każdym razie dalej to indukcją ciągniemy.

Teraz przechodzimy do zadania :
\(\displaystyle{ n=1}\) działa, od teraz \(\displaystyle{ n \ge 2}\).
Niech \(\displaystyle{ p}\) będzie najmniejszą liczbą pierwszą, że \(\displaystyle{ p|n}\).
Niech \(\displaystyle{ d}\) będzie najmniejszą liczbą naturalną, że \(\displaystyle{ p|2^d - 1}\).
Ponieważ zachodzi jednocześnie \(\displaystyle{ d|p-1}\) oraz \(\displaystyle{ d|2n}\), to \(\displaystyle{ d=1}\) lub \(\displaystyle{ d=2}\).
Możliwy jest oczywiście tylko drugi przypadek, który pociąga za sobą \(\displaystyle{ p=3}\), czyli \(\displaystyle{ n=3k}\).
Dla \(\displaystyle{ k=1}\) dostajemy kolejne rozwiązanie, od teraz \(\displaystyle{ k \ge 2}\).
Dostajemy więc:
\(\displaystyle{ 9k^2|8^k+1}\), stąd \(\displaystyle{ k}\) jest niepodzielne przez \(\displaystyle{ 7}\).
Niech \(\displaystyle{ q}\) będzie najmniejszą liczbą pierwszą, że \(\displaystyle{ q|k}\).
Niech \(\displaystyle{ e}\) będzie najmniejszą liczbą naturalną, że \(\displaystyle{ q|2^e-1}\).
Powtarzając poprzednie rozumowanie dostajemy \(\displaystyle{ q=7}\) lub \(\displaystyle{ q=3}\), stąd \(\displaystyle{ q=3}\), czyli \(\displaystyle{ k=3l}\).
Mamy więc za zadanie wyznaczyć wszystkie liczby naturalne \(\displaystyle{ l}\), że
\(\displaystyle{ (3^2l)^2|2^{3^2l}+1}\).
Teraz niech \(\displaystyle{ c}\) będzie największą liczba taką, że \(\displaystyle{ 3^{c-2}|l}\).
Kładąc \(\displaystyle{ l=3^{c-2}z}\) dostajemy znaleźć wszystkie liczby całkowite \(\displaystyle{ c \ge 2}\) i \(\displaystyle{ z}\) takie, że
\(\displaystyle{ 3^{2c}z^2|2^{3^{c}z}+1}\).
Udowodnimy, że dla \(\displaystyle{ c \ge 2}\) podzielność
\(\displaystyle{ 3^{2c}|2^{3^cz}+1}\) nie może zachodzić.
Na mocy lematu 1 dostalibyśmy
\(\displaystyle{ 3^{2c}|2^{3^c}+1}\).
Jednakże na mocy lematu 2 jest to możliwe tylko dla \(\displaystyle{ c \le 1}\).
Stąd wszystkie szukane liczby całkowite \(\displaystyle{ n}\) to \(\displaystyle{ 1}\) i \(\displaystyle{ 3}\).
Byłbym wdzięczny, gdyby ktoś rzucił okiem na to rozwiązanie i napisał o ewentualnych błędach. W niektórych miejscach po prostu rzucałem idee, nie chciało mi się całego dowodu przepisywać.