Użytkownicy online
Naszą witrynę przegląda teraz 2 gości| Rząd liczb |
 |
 |
 |
| Zadania II |
| Wpisany przez Joachim Jelisiejew |
| niedziela, 07 lutego 2010 19:41 |
|
Źródło zadań w texu. \documentclass[10pt]{article} \usepackage{amssymb} \usepackage{amsmath} \textwidth 16cm \textheight 24cm \oddsidemargin 0cm \topmargin 0pt \headheight 0pt \headsep 0pt \usepackage[polish]{babel} \usepackage[utf8]{inputenc} \usepackage[T1]{fontenc} %\usepackage{MnSymbol} % ---------------------------------------------------------------- \vfuzz4pt % Don't report over-full v-boxes if over-edge is small \hfuzz4pt % Don't report over-full h-boxes if over-edge is small % THEOREMS ------------------------------------------------------- \newtheorem{thm}{Twierdzenie}[section] \newtheorem{cor}[thm]{Wniosek} \newtheorem{lem}[thm]{Lemat} \newtheorem{defn}[thm]{Definicja} \newtheorem{tozs}[thm]{Tożsamość} \newtheorem{hyp}[thm]{Hipoteza} \newtheorem{useless}[thm]{} \def\mb#1{\mathbb{#1}} \def\rozw{\textbf{Rozwiązanie}: \\} \def\deg{^{\circ}} \def\source#1{$ $\\Źródło: #1} \def\o{\operatorname{ord}} \begin{document} \title{II kółko -- Czy mamy dość teorii liczb?} \date{27.10.09} \maketitle \paragraph{Teoria} \begin{enumerate} \item Małe twierdzenie Fermata: \begin{thm}[Małe twierdzenie Fermata] Dla każdej liczby pierwszej $p$ i liczby całkowitej $a$ zachodzi $$p | a^p - a$$ \end{thm} \item \begin{defn} Niech $a, n$ będą liczbami naturalnymi względnie pierwszymi. \emph{Rzędem} liczby $a$ modulo $n$ nazywamy najmniejsze $k\in\mb{Z}_+$, takie, że $$a^k \equiv 1 \mod n$$ Rząd ten oznaczamy przez $\o(a, n)$ lub, gdy $n$ jest znane, $\o(a)$. \end{defn} \item \begin{thm}[Lemat o rzędzie] Jeżeli $a, k', n$ są takie, że $$a^{k'} \equiv 1 \mod n$$ to $\displaystyle{\o(a, n) | k'}$. \end{thm} \item \begin{cor} Jeżeli $p$ jest liczbą pierwszą, zaś $a$ jest liczbą całkowitą niepodzielną przez $p$, to $$\o(a, p)|p-1$$ \end{cor} \end{enumerate} \paragraph{Zadania} \begin{enumerate} \item Udowodnić, że dla liczby pierwszej $p$ istnieje takie $n$ naturalne, że $$p|2^n - n$$ \source{Staszic} \item Udowodnić, że dla liczby pierwszej $p$ istnieje nieskończenie wiele liczb naturalnych $n$ takich, że $$p|2^n - n$$ \source{Staszic} \item Rozstrzygnąć, dla jakich $k\in \mb{N}$ istnieje liczba naturalna $n$, będąca kwadratem liczby naturalnej i zaczynająca się w zapisie dziesiętnym $k$ jedynkami. \source{Mathlinks} \item * Udowodnić, że równanie $$x^2 + y^2 + z^2 = (x-y)(y-z)(z-x)$$ ma nieskończenie wiele rozwiązań w liczbach naturalnych $x,y,z$. \source{Mathlinks} \item * Znajdź wszystkie liczby naturalne $n$ takie, że $$n^2 | 3^n + 1$$ \source{Staszic} \end{enumerate} \paragraph{Zadania ,,lekcyjne''} \begin{enumerate} \item Udowodnij, że dla każdej liczby naturalnej $n$ zachodzi $$2^{n+1} | 3^{2^n} - 1$$ \item Rozstrzygnąć, czy poniższe twierdzenie jest prawdziwe:\\ Jeżeli $p>2$ jest liczbą pierwszą, zaś $a$ jest taką liczbą całkowitą dodatnią, że $p | a+1$, to $$p^{n+1} | a^{p^n} + 1$$ dla wszystkich liczb $n\in \mb{Z}_+$. \end{enumerate} \end{document}
Źródło rozwiązań w texu. \documentclass[10pt]{article} \usepackage{amssymb} \usepackage{amsmath} \textwidth 16cm \textheight 24cm \oddsidemargin 0cm \topmargin 0pt \headheight 0pt \headsep 0pt \usepackage[polish]{babel} \usepackage[utf8]{inputenc} \usepackage[T1]{fontenc} %\usepackage{MnSymbol} % ---------------------------------------------------------------- \vfuzz4pt % Don't report over-full v-boxes if over-edge is small \hfuzz4pt % Don't report over-full h-boxes if over-edge is small % THEOREMS ------------------------------------------------------- \newtheorem{thm}{Twierdzenie}[section] \newtheorem{cor}[thm]{Wniosek} \newtheorem{lem}[thm]{Lemat} \newtheorem{defn}[thm]{Definicja} \newtheorem{tozs}[thm]{ToĹĽsamość} \newtheorem{hyp}[thm]{Hipoteza} \newtheorem{useless}[thm]{} \def\mb#1{\mathbb{#1}} \def\rozw{\textbf{Rozwiązanie}: \\} \def\deg{^{\circ}} \def\source#1{$ $\\Źródło: #1} \def\o{\operatorname{ord}} \begin{document} \def\comment#1{\ [[#1]]\ } \title{``Czy mamy dość teorii liczb?'' - rozwiązania} \author{Mateusz Jocz} \date{} \maketitle \begin{enumerate} \item Udowodnić, że dla liczby pierwszej $p$ istnieje takie $n$ naturalne, że $$p|2^n - n$$ \source{Staszic} \item Udowodnić, że dla liczby pierwszej $p$ istnieje nieskończenie wiele liczb naturalnych $n$ takich, że $$p|2^n - n$$ \source{Staszic} \textbf{Rozwiązanie:} \begin{enumerate} \item Jeżeli $p=2$ to teza jest spełniona dla $n=2$. Dalej zakładamy że $p\neq2$. \item Z małego twierdzenia Fermata mamy: \[2^{p-1} \equiv 1 \mod p\] Teraz na mocy \textit{lematu o rzędzie} otrzymujemy $\o(2,p)|p-1$. Z tego wynika, że liczby $\o(2,p)$ i $p$ są względnie pierwsze. \item Wykażemy, że teza jest spełniona dla pewnego $n=kd$, gdzie $k$ jest całkowite, a $d=\o(2,p)$. Dla każdego $k$, z definicji rzędu $d$, mamy: \[(2^{d})^{k} \equiv 1^{k}\mod p\] \[2^{n} \equiv 1\mod p\] \item Rozważmy zbiór liczb $A=\{0,d,2d,\ldots,(p-1)d\}$. Wiemy, że $p$ jest względnie pierwsze z $d$. Jeżeli istniałyby dwie liczby $h$ i $l$ $(0\leq l<h<p)$, takie że $hd$ i $ld$ dawałyby takie same reszty z dzielenia przez $p$ to mielibyśmy $p|d(h-l) \Rightarrow p|h-l$, sprzeczność. Zatem liczby ze zbioru $A$ dają różne reszty z dzielenia przez $p$, a skoro w $A$ jest tyle samo liczb, co w zbiorze wszystkich reszt, to liczby z $A$ dają wszystkie reszty z dzielenia przez $p$, w szczególności dla pewnego $m\in\{0,1,2,\ldots,p-1\}$ mamy: \[md \equiv 1 \mod p\] \item Definiujemy $$n:=md$$ gdzie $m,d$ określone są wyżej. Udowodniliśmy, że $$2^n \equiv 1 \mod p \hbox{ oraz } n\equiv 1\mod p$$ Stąd wynika, że $$p | 2^n - n$$ Istnieje więc liczba $n$ spełniająca warunki zadania, pozostaje dowieść, że takich liczb jest nieskończenie wiele. \item Niech $z$ będzie dowolną liczbą naturalną, $d=\o(2,p)$, jak wyżej, a $n$ będzie takie, że $n \equiv 2^n\equiv 1 \mod p$. Zauważmy że: \[n+zpd \equiv n \equiv 1 \mod p\] \[2^{n+zpd} = 2^n \cdot (2^{d})^{zp} \equiv 1\cdot 1^{zp} = 1 \mod p\] \[2^{n+zpd} - (n + zpd) \equiv 0\mod p \] Ponieważ $z$ może być dowolną liczbą naturalną to otrzymujemy nieskończenie wiele rozwiązań postaci $n + zpd$. \end{enumerate} \item Rozstrzygnąć, dla jakich $k\in \mb{N}$ istnieje liczba naturalna $n$, będąca kwadratem liczby naturalnej i zaczynająca się w zapisie dziesiętnym $k$ jedynkami. \source{Mathlinks} \textbf{Rozwiązanie:} \begin{enumerate} \item Dla $k=0$ taka liczba oczywiście istnieje, na przykład $n=4=2^{2}$. \item Dla $k\geq 1$ mamy: \[{\underbrace{33\ldots 3}_{k-1\ razy}4}^{2}=(\frac{10^{k-1}-1}{3}\cdot 10 +4)^{2}=\] \[=\frac{10^{2k-2}-2\cdot10^{k-1}+1}{9}\cdot 10^{2}+8\cdot10\cdot \frac{10^{k-1}-1}{3}+16=\] \[=\frac{10^{2k}}{9}- 20\cdot\frac{10^k}{9}+\frac{100}{9}+24\cdot \frac{10^{k}}{9}-\frac{240}{9}+\frac{90}{9}+6=\] \[=\frac{10^{2k}}{9}-\frac{10^{k}}{9}+5\cdot \frac{10^{k}}{9}-\frac{50}{9}+6=\] \[=\frac{10^{k}-1}{9} \cdot 10^{k}+5 \cdot \frac{10^{k-1}-1}{9}\cdot 10 +6=\] \[=\underbrace{11\ldots1}_{k\ razy}\underbrace{55\ldots5}_{k-1\ razy}6\] Stąd już widzimy, że o ile $k\geq 1$ to taka liczba $n$ dla każdego $k$ istnieje. \item Ostatecznie liczba naturalna $n$ o wymaganych własnościach istnieje dla wszystkich $k\in \mb{N}$, \newline $c.k.d.$ % \item Ogólnie prawdziwa jest równość: % \[({\underbrace{33\ldots 3}_{k+1\ razy}\cdot10^{[\log{\alpha}]+1}+\alpha})^{2}= % \underbrace{11\ldots1}_{k\ razy}\cdot10^{[\log{\beta}]+1}+\beta\] % dla każdego naturalnego $\alpha$ i pewnego naturalnego $\beta$. % Dla przykładu: \item Oczywiście istnieją też inne przykłady podobnych liczb, np.: \[{\underbrace{33\ldots 3}_{k+1\ razy}}^{2}=\underbrace{11\ldots1}_{k\ razy}0\underbrace{88\ldots8}_{k\ razy}9\] \[{\underbrace{33\ldots 3}_{k-1\ razy}45}^{2}=\underbrace{11\ldots1}_{k\ razy}\underbrace{88\ldots8}_{k-2\ razy}9025\] \item \textbf{Komentarz:} Takie rozwiązanie narzuca się, jeżeli pomyśli się, że liczba $111111\dots$ jest prawie równa $10^{2k} \cdot 1/9$, a przecież ta liczba jest kwadratem liczby $10^k \cdot 1/3$ równej $333333\dots$. Potem te ``prawie'' trzeba oczywiście sformalizować... \end{enumerate} \item * Udowodnić, że równanie $$x^2 + y^2 + z^2 = (x-y)(y-z)(z-x)$$ ma nieskończenie wiele rozwiązań w liczbach naturalnych $x,y,z$. \source{Mathlinks} \textbf{Rozwiązanie:} \begin{enumerate} \item Niech $k$ będzie dowolną liczbą całkowitą dodatnią. Rozważmy rozwiązania postaci: \[ (x,y,z)=(\ (2k-1)(6k^{2}+1), 2k(6k^{2}+1), (2k+1)(6k^{2}+1)\ )\] Obliczamy, że lewa strona równania jest równa: \[ x^{2}+y^{2}+z^{2}=(2k-1)^{2}(6k^{2}+1)^{2}+(2k)^{2}(6k^{2}+1)^{2} + (2k+1)^{2}(6k^{2}+1)^{2}=\] \[=(6k^{2}+1)^{2}(4k^{2}-4k+1+4k^{2}+4k^{2}+4k+1)=(6k^{2}+1)^{2}(12k^{2}+2)=2(6k^{2}+1)^{3}\] Natomiast prawa strona równania wynosi: \[(x-y)(y-z)(z-x)=(6k^{2}+1)(2k-1-2k)\cdot(6k^{2}+1)(2k-2k-1)\cdot(6k^{2}+1)(2k+1-2k+1)=\] \[=(6k^{2}+1)^{2}\cdot 2(6k^{2}+1)= 2(6k^{2}+1)^{3}\] Widzimy, że obie strony równania są równe. Ponieważ $k$ jest dowolną liczbą całkowitą dodatnią i dla różnych $k$ wartości liczby $z=(2k+1)(6k^2 + 1)$ są różne, to otrzymaliśmy nieskończoną liczbę rozwiązań postaci \[ (x,y,z) = (\ (2k-1)(6k^{2}+1), 2k(6k^{2}+1), (2k+1)(6k^{2}+1)\ ) \] \textbf{Koniec dowodu -- punkt następny służy tylko objaśnieniu i nie potrzeba go pisać np. na olimpiadzie.} \item \emph{W jaki sposób możemy znaleźć właśnie taką postać rozwiązania?}\\ \begin{enumerate} \item Na początku stwierdzamy, że trzy niewiadome to trochę za dużo. Spróbujmy ograniczyć się do dwóch. Warto więc aby $(x,y,z)$ był jakimś ciągiem, którego wyrazy możemy zapisać za pomocą dwóch niewiadomych. Jako jeden z pierwszych nasuwa nam się ciąg arytmetyczny. Różnicę naszego ciągu oznaczmy przez $r$. Prawdziwe są równości: $$x=y-r\ \ \hbox{ i }\ \ z=y+r$$ Po podstawieniu tych równości możemy zredukować równanie $$x^2 + y^2 + z^2 = (x-y)(y-z)(z-x)$$ do postaci: $$3y^{2}=2r^{2}(r-1)$$ \item Z powyższego równania możemy wyliczyć $y$: $$y = \sqrt{\frac{2r^2(r-1)}{3}} = r\sqrt{\frac{2(r-1)}{3}}$$ Jeżeli teraz znajdziemy nieskończenie wiele takich $r$ całkowitych dodatnich, że $\displaystyle{r\sqrt{\frac{2(r-1)}{3}}}$ jest całkowite (oczywiście jest też wtedy dodatnie) i przyjmiemy $$r_y:=r\sqrt{\frac{2(r-1)}{3}},\ r_x:=r_y - r,\ r_z:=r_y + r$$ to trójka $(r_x,r_y,r_z)$ będzie rozwiązaniem naszego wyjściowego równania. \item Kiedy $\sqrt{\frac{2(r-1)}{3}}$ może być całkowite?\\ Żeby było to całkowite, wystarczy, żeby $r$ było postaci $r=6k^2+1$, gdzie $k\in \mathbb{Z}_+$ -- wtedy $\sqrt{\frac{2(r-1)}{3}} = 2k$.\\ Przyjmujemy więc takie $r$ i wyliczamy $$r_y = 2k(6k^2 + 1),\ r_x = (2k-1)(6k^2+1),\ r_z = (2k+1)(6k^2 +1)$$ % $$3y^{2}-2r^{2}(r-1)=0$$ % Wiedząc że $$y=\frac{\pm\sqrt{\Delta}}{6}\hbox{,}$$ $$\hbox{gdzie}\ \Delta \hbox{ jest wyróżnikiem % rozważanego równania}$$ % chcemy by delta była kwadratem liczby całkowitej i ponadto była podzielna przez 36. % $$\Delta=24r^{2}(r-1)=4\cdot r^{2}\cdot6(r-1)$$ % Wyrażenia $4$ i $r^{2}$ nas mało obchodzą bo są kwadratami liczb całkowitych. Nas obchodzi tylko to, % aby wyrażenie $6(r-1)$ było kwadratem liczby całkowitej. Więc bierzemy $r-1=6k^{2}$, gdzie $k$ jest % całkowite. Przy okazji okazuje się, że teraz delta jest faktycznie podzielna przez 36. % $$r=6k^{2}+1$$ % $$\Delta=4\cdot (6k^{2}+1)^{2}\cdot 36k^{2}$$ % Interesuje nas dodatnia wartość y, więc: % $$y=\frac{\sqrt{4\cdot (6k^{2}+1)^{2}\cdot 36k^{2}}}{6}= % \frac{2\cdot (6k^{2}+1)\cdot 6k}{6}=2k(6k^{2}+1)$$ % Pozostaje nam wyliczyć $x$ oraz $z$, pamiętając że: % $$x=y-r\ \ \hbox{ i }\ \ z=y+r$$ % \[ x=(2k-1)(6k^{2}+1)\ \ \hbox{ i }\ \ z=(2k+1)(6k^{2}+1)\] \end{enumerate} \end{enumerate} \item * Znajdź wszystkie liczby naturalne $n$ takie, że $$n^2 | 3^n + 1$$ \source{Staszic} \textbf{Rozwiązanie:} \begin{enumerate} \item Załóżmy, że dla pewnego $n>1$ teza jest spełniona. Wtedy możemy $n$ przedstawić w postaci: $n=k\cdot p$, gdzie $p$ jest \textbf{najmniejszym} pierwszym dzielnikiem liczby $n$, a $k$ jest pewną liczbą całkowitą dodatnią. \item Zauważmy, że $3\not|n$ i tym samym $p\neq 3$. Sensowny jest więc napis $\o(3,p)$ Zauważmy, że: \[ 3^{n} \equiv -1 \mod p \] \[ 3^{2n} \equiv 1 \mod p \] Na mocy \textit{lematu o rzędzie} mamy $\o(3,p) | 2n = 2pk$. Z drugiej strony z (wniosku z) \textit{lematu o rzędzie} wynika że $\o(3,p)|p-1$, czyl $\o(3,p)$ jest względnie pierwsze z $p$. Zatem $\o(3,p) | 2k$. \item Niech $d$ będzie największym wspólnym dzielnikiem liczb $\o(3,p)$ i $k$.\\ Możliwe są dwa przypadki: $\o(3,p)=d$ lub $\o(3,p)=2d$. W obu przypadkach, jeżeli $d\geq p$, to $\o(3,p)\geq p$ i otrzymujemy sprzeczność z $\o(3,p)|p-1$. Stąd wynika $d<p$.\\ \item Liczby $d<p$ i $p$ są dzielnikami $n$, przy czym $p$ jest najmniejszym dzielnikiem pierwszym, więc $d=1$ (kluczowy moment) i tym samym $$\o(3,p)=1 \hbox{ lub } \o(3,p)=2$$ korzystając z definicji rzędu otrzymujemy \[3^{1} \equiv 1 \mod p \hbox{ lub } 3^{2} \equiv 1 \mod p\] \[p|2 \hbox{ lub } p|8\] A więc $p=2$, $n=2k$, czyli $4|n^{2}$. Zauważmy, że jeśli $n$ jest parzyste to $3^{n} \equiv 1 \mod 4$. Liczba $3^{n} +1$ nie może więc być podzielna przez $4$. Sprzeczność.\\ \item Pozostaje nam przypadek gdy $n=1$. Łatwo zauważyć, że teza jest teraz spełniona. Jest to więc jedyne rozwiązanie.\end{enumerate} \end{enumerate} %\end{enumerate} \end{document} |
