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.
Dla \(\displaystyle{ p=2}\) teza zachodzi, dla dowolnej liczby pierwszej \(\displaystyle{ p>2}\) popatrzmy na wyrażenie \(\displaystyle{ x^{p-1}+x^{p-2}+...+x+1}\), gdzie \(\displaystyle{ x \in \mathbb{Z}_+}\). Zauważmy, że zbiór dzielników pierwszych \(\displaystyle{ x^{p-1}+x^{p-2}+...+x+1}\) nie może zawierać się w zbiorze dzielników pierwszych \(\displaystyle{ x-1}\), istotnie, weźmy pewne \(\displaystyle{ r \in \mathbb{P}}\) dzielące oba składniki, czyli \(\displaystyle{ x \equiv 1\pmod{r}}\) ale wtedy \(\displaystyle{ 0 \equiv x^{p-1}+..+x+1 \equiv p\pmod{r}}\), czyli \(\displaystyle{ r=p}\), więc jedynym wspólnym dzielnikiem pierwszym tych dwóch składników może być jedynie \(\displaystyle{ p}\). Niech \(\displaystyle{ x = p^a\cdot n+1 \ , \ n \ge 1}\) gdzie \(\displaystyle{ a \ge 1 \Rightarrow b\ge 2}\), wówczas:
Ale patrząc na to \(\displaystyle{ \pmod{p^2}}\) dostajemy, że \(\displaystyle{ 0 \equiv p\pmod{p^2}}\) (dla \(\displaystyle{ a=1}\) trzeba rozwinąć te sumy z dwumianu Newtona) sprzeczność.
Przejdźmy do zadania. Rozważmy dowolny dzielnik pierwszy \(\displaystyle{ q_1 \nmid x-1}\) taki, że \(\displaystyle{ q_1 \mid x^{p-1}+...+x+1 = \frac{x^p-1}{x-1} \Rightarrow q_1 \mid x^p-1}\). Niech \(\displaystyle{ t=ord_{q_1} x}\), mamy więc \(\displaystyle{ t \mid p \wedge t \mid q_1-1}\), nie może być \(\displaystyle{ t=1}\) bo wtedy \(\displaystyle{ x-1 \equiv 0 \pmod{q_1}}\), więc \(\displaystyle{ t=p}\), czyli \(\displaystyle{ p \mid q_1-1 \iff q_1 = kp+1}\)
Naturalnie \(\displaystyle{ x}\) wybieraliśmy dowolne, więc biorąc teraz \(\displaystyle{ x=q_1+1}\) dostajemy kolejną liczbę pierwszą \(\displaystyle{ q_2}\), potem biorąc \(\displaystyle{ x=q_1q_2+1}\) otrzymujemy kolejną liczbę pierwszą \(\displaystyle{ q_3}\) itd. co dowodzi, że istotnie dla dowolnej liczby pierwszej \(\displaystyle{ p}\) istnieje nieskończenie wiele pierwszych \(\displaystyle{ q}\), że \(\displaystyle{ p\mid q-1}\)
//Dziękuję Sylwek za zwrócenie uwagi na jedną nieścisłość, już poprawione
Znajdź wszystkie pary liczb całkowitych dodatnich \(\displaystyle{ (a,b)}\) dla których \(\displaystyle{ 7^a - 3^b \mid a^4+b^2}\)
\(\displaystyle{ 7^a-3^b}\) jest liczbą parzystą, więc \(\displaystyle{ a^4+b^2}\) musi być liczbą parzystą, więc \(\displaystyle{ a \equiv b \pmod 2}\), ale wtedy \(\displaystyle{ 4 | 7^a-3^b}\), więc \(\displaystyle{ 4|a^4+b^2}\), stąd \(\displaystyle{ 2|a}\) i \(\displaystyle{ 2|b}\).
Niech \(\displaystyle{ a = 2m}\), \(\displaystyle{ b = 2n}\). Mamy \(\displaystyle{ (7^m-3^n)(7^m+3^n) | 16m^4 + 4n^2}\). Łatwo pokazać, że lewa strona jest podzielna przez 8 (dla nieparzystych \(\displaystyle{ a}\) i \(\displaystyle{ b}\) zachodzi \(\displaystyle{ 8|(a-b)(a+b)}\)), zatem \(\displaystyle{ n}\) musi być parzyste.
Niech \(\displaystyle{ a = 2m}\), \(\displaystyle{ b = 2n}\), mamy \(\displaystyle{ 16m^4+4n^2 \geq 2(7^m+3^n)}\) \(\displaystyle{ 8m^4+2n^2 \geq 7^m+3^n}\)
Jednak dla \(\displaystyle{ m,n \geq 4}\) zachodzi \(\displaystyle{ 7^m > 8m^4}\) oraz \(\displaystyle{ 3^n > 2n^2}\), stąd nierówność ta nie zachodzi. Zatem musi być \(\displaystyle{ n = 2}\), czyli \(\displaystyle{ b = 4}\) i wystarczy sprawdzić \(\displaystyle{ m \in \{1,2,3\}}\), czyli \(\displaystyle{ a \in \{2,4,6\}}\), okazuje się, że tylko para \(\displaystyle{ (2,4)}\) spełnia warunki zadania.
Wykaż, że dla każdego \(\displaystyle{ n \in \mathbb{N}}\) można znaleźć trzy różne liczby \(\displaystyle{ a,b,c}\) większe od \(\displaystyle{ n^2}\) i mniejsze od \(\displaystyle{ n^2+n+3\sqrt{n}}\) takie, że \(\displaystyle{ a|bc}\).-- 10 sie 2013, o 14:45 --
hint:
\(\displaystyle{ a = (n-x+1)(n+x+1) = n^2+2n+1-x^2}\), \(\displaystyle{ b, c}\) można wyrazić "podobnym" iloczynem, pokombinować z plusami, minusami i jedynką w tych nawiasach, a potem dobrać odpowiednie \(\displaystyle{ x}\), żeby spełnić założenia.
Przyjmijmy \(\displaystyle{ a=(n+1-x)(n+1+x) \ , \ b = (n+1-x)(n+x) \ , \ c = (n+1+x)(n-x)}\), wtedy naturalnie \(\displaystyle{ a \mid bc}\), oraz jak łatwo sprawdzić są to różne liczby. Pozostaje pokazać, że istnieje \(\displaystyle{ x}\), że wszystkie liczby należą do przedziału \(\displaystyle{ (n^2 ; n^2+n+3\sqrt{n})}\), rozpisując każdą i licząc delty itd dostajemy, że musi być:
\(\displaystyle{ x \in \left(\sqrt{n-3\sqrt{n}+1} \ ; \ \frac{-1+\sqrt{1+4n}}{2}\right)}\)
(naturalnie przy założeniu, że \(\displaystyle{ n-3\sqrt{n}+1 \ge 0}\), jak tak nie jest to po prostu dolnym ograniczeniem jest \(\displaystyle{ 0}\)). Zostaje pokazać, że zawsze jakiś całkowity \(\displaystyle{ x}\) siedzi w tym przedziale, czyli, że \(\displaystyle{ \frac{-1+\sqrt{1+4n}}{2} - \sqrt{n-3\sqrt{n}+1} > 1}\)
A to podnosząc dwukrotnie do kwadratu sprowadza się do \(\displaystyle{ n > 0}\)
Rozwiązać w \(\displaystyle{ \mathbb{Z}_+}\) równanie \(\displaystyle{ x!+y^3 = 18+z^3}\)
Załóżmy, że równanie ma rozwiązanie, gdy \(\displaystyle{ x \ge 7}\). Sześciany liczb naturalnych mogą dawać reszty \(\displaystyle{ 0,1,6}\) modulo \(\displaystyle{ 7}\), więc \(\displaystyle{ z^3-y^3}\) daje resztę \(\displaystyle{ 0,1,2,5}\) lub \(\displaystyle{ 6}\) modulo \(\displaystyle{ 7}\), jednak \(\displaystyle{ x!-18 \equiv 3 \pmod{7}}\).
Mamy więc następujące przypadki: \(\displaystyle{ 1^{\circ}}\)\(\displaystyle{ x \le 3}\). Wtedy \(\displaystyle{ y>z}\), więc możemy podstawić \(\displaystyle{ y=z+k}\), gdzie \(\displaystyle{ k \in \mathbb{Z}_+}\) i mamy \(\displaystyle{ 18-x!=k(3z^2+3zk+k^2)}\). Dla \(\displaystyle{ k \ge 2}\) zachodzi \(\displaystyle{ 18-x! \ge 2(3+6+4)}\), więc \(\displaystyle{ k=1}\). Jeśli \(\displaystyle{ x=1}\) lub \(\displaystyle{ x=3}\), to jedna strona równania \(\displaystyle{ 18-x!=3z^2+3z+1}\) nie jest przystająca do drugiej modulo 3, a gdy \(\displaystyle{ x=2}\), to pokazujemy, że równanie \(\displaystyle{ 3z^2+3z+1=16}\) nie ma rozwiązań w liczbach całkowitych dodatnich.
\(\displaystyle{ 2^{\circ}}\)\(\displaystyle{ x=4}\). Podstawiamy \(\displaystyle{ z=y+k}\), gdzie \(\displaystyle{ k\in \mathbb{Z}_+}\) i po uproszczeniu otrzymujemy \(\displaystyle{ 6=3y^2k+3yk^2+k^3 \ge 3+3+1}\)- sprzeczność .
\(\displaystyle{ 3^{\circ}}\)\(\displaystyle{ 2\cdot 51=z^3-y^3}\) z czego wynika, że \(\displaystyle{ z>y}\), oraz \(\displaystyle{ z \equiv y \equiv 1 \pmod{2}}\). Gdyby \(\displaystyle{ z \ge 7}\), to \(\displaystyle{ (z-y)(z^2+zy+y^2) \ge (7-6)(7^2+7 \cdot 6 +6^2)}\), więc \(\displaystyle{ z \le 6}\), stąd otrzymujemy \(\displaystyle{ (y,z)=(1,3) \vee (1,5) \vee (3,5)}\), jednak żadna para liczb nie spełnia równania.
\(\displaystyle{ 4^{\circ}}\)\(\displaystyle{ 6 \cdot 117=z^3-y^3 \ (1)}\), z czego wynika, że \(\displaystyle{ z \le 15}\) (inaczej byłoby: \(\displaystyle{ z^3-y^3 \ge 16^3-15^3}\)), oraz \(\displaystyle{ z \equiv y \equiv 1 \pmod{2} \wedge z\equiv y \pmod{3}}\), więc \(\displaystyle{ (y,z)=(1,7) \vee (1,13) \vee (3,9) \vee (3,15) \vee (5,11) \vee (7,13) \vee (9,15)}\). Podstawiamy do równania (1) i mamy jedno rozwiązanie \(\displaystyle{ (x,y,z)=(6,3,9)}\)
Dane są \(\displaystyle{ a,b,n \in \mathbb{Z}_+}\), takie, że \(\displaystyle{ 2^n-1=ab}\), oraz \(\displaystyle{ k \in \mathbb{Z}_+}\), takie że \(\displaystyle{ ab+a-b-1 \equiv 2^k \pmod{2^{k+1}}}\). Pokazać, że \(\displaystyle{ k}\) jest parzyste.
Niech \(\displaystyle{ a=2^{x_1}m_1 +1, b=2^{x_2}m_2 -1}\), gdzie \(\displaystyle{ m_1 m_2}\) jest nieparzyste. Wówczas dostajemy, że \(\displaystyle{ k=x_1 + x_2}\). Ponadto \(\displaystyle{ 2^n=2^{x_1 + x_2} m_1 m_2 - 2^{x_1} m_1 + 2^{x_2} m_2}\). Załóżmy prawie bez straty ogólności, że \(\displaystyle{ x_2 \leq x_1}\). Wówczas możemy sobie napisać \(\displaystyle{ 2^{n-x_2}=2^{x_1} m_1 m_2 - 2^{x_1-x_2} m_1 + m_2}\). No a widać, że poza przypadkami skrajnymi zachodzi \(\displaystyle{ n>x_2}\), więc skoro założyliśmy, że \(\displaystyle{ m_1 m_2}\) jest nieparzyste, to \(\displaystyle{ 2^{x_1} m_1 m_2 - 2^{x_1-x_2} m_1}\) też musi być nieparzyste, czyli \(\displaystyle{ x_1=x_2}\).
Przypadki skrajne można sobie rozpatrzeć oddzielnie, tam nie ma nic ciekawego.
Udowodnij, że \(\displaystyle{ \sum_{i=1}^{\frac{p-1}{4}} \lfloor \sqrt{ip} \rfloor = \frac{p^2-1}{12}}\) gdzie \(\displaystyle{ p}\) jest liczbą pierwszą taką, że w ciągu arytmetycznym \(\displaystyle{ p-1,2p-1,...}\) występuje co najmniej jeden kwadrat liczby naturalnej.
Wyznaczyć wszystkie liczby pierwsze \(\displaystyle{ p, q}\) takie, że \(\displaystyle{ m^{3pq} \equiv m \pmod{ 3pq}}\) dla dowolnej liczby naturalnej \(\displaystyle{ m}\)
Ostatnio zmieniony 21 paź 2018, o 00:37 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód:Poprawa wiadomości.
Udowodnić, że jeśli \(\displaystyle{ n>1}\) i \(\displaystyle{ 2n-1}\) oraz \(\displaystyle{ 3n-2}\) są kwadratami liczb całkowitych, to \(\displaystyle{ 19n - 14}\) jest liczbą złożoną
