Математикийн олимпиадад бэлтгэгч сурагчдад болон математик сонирхогч залуустаа зориулан зарим сэдвүүдийг товч, хөнгөн байдлаар хүргэж байхаар боллоо. Сэдвүүдийг жишээ, даалгавараар илүү баяжуулан хүргэх болно.

Олимпиадын холбогдолтой бусад хичээлүүдийг www.iMath.mn/lesson товч дээр дараад үзээрэй.

ЭЙЛЕРИЙН ФУНКЦ

Жишээ 1, $n=20$ бол $\mathbb{Z}_{20}^{*}=\{1,3,7,9,11,13,17,19\}$ ба $\varphi(20)=8$ байна.

Баталгаа. $p$ анхны тоо тул $p^k$-тэй харилцан анхны биш тоонууд нь $$p,\ 2p,\ 3p,...,p^{k-1}\cdot p$$ юм. Нийт $p^{k-1}$ ширхэг тоо байна. $|\mathbb Z_{p^k}|=p^k$ тул харилцан анхны тоонуудын тоо нь $$\varphi=p^k-p^{k-1}$$ байх нь ойлгомжтой. Батлагдав.

Баталгаа. $m$ ба $n$ тоонуудын хувьд $\mathbb{Z}_{m}^{*}=\left\{r_{1}, r_{2}, \ldots, r_{\varphi(m)}\right\}$, $\mathbb{Z}_{n}^{*}=\left\{s_{1}, s_{2}, \ldots, s_{\varphi(n)}\right\}$ ба $\mathbb Z_{mn}^*=\{t_1,...,t_{\varphi(mn)}\}$ байг. $t\in\mathbb Z_{mn}^*$ ба $t=mq_1+r_1$, $t=nq_2+r_2$ бол $(m,r_1)=1$, $(n,r_2)=1$ гэж гарна. Өөрөөр хэлбэл $\mathbb Z_{mn}^*\to Z_m^*\times \mathbb Z_n^*$ буулгалт оршин байх буюу $\mathbb Z_{mn}^*$ олонлогийн элемент бүрээс $(r_i, s_j)$ хос олдоно. Энд, $r_i\in\mathbb Z_m^*$, $s_j\in\mathbb Z_n^*$

Нөгөө талаас, үлдэгдлийн тухай хятадын теоремоор $0 \leq t< m n$ $$ r_{i}=t(\bmod m), \quad s_{j}=t(\bmod n) $$ байх $t$ тоо цор ганц олдоно. Үүгээр $\mathbb Z_{mn}^*\to Z_m^*\times \mathbb Z_n^*$ буулгалт харилцан нэг утгатай буюу $$\varphi(m n)=\varphi(m) \varphi(n)$$ байх нь батлагдана.

Лемм 1 болон теорем 1-ээс дараах үр дүн гарна.

Баталгаа. Өмнө баталсан лемм 1 болон теорем 1-ийг ашиглан тооцоолвол

Жишээ 2. $264$ тооны хувьд $$\varphi(264)=\varphi\left(2^{3} \cdot 3 \cdot 11\right)=$$$$=264\left(\frac{1}{2}\right)\left(\frac{2}{3}\right)\left(\frac{10}{11}\right)=80$$

ЭЙЛЕРИЙН ТЕОРЕМ

Бүхэл $a$ ба $b$ тоонуудыг $m$-д хуваахад гарах үлдэгдэл нь тэнцүү байвал $a\equiv b(\bmod m)$ гэж бичээд $m$ модулиар тэнцүү гэж ярьна.

Жишээлбэл, $$41 \equiv 80(\bmod 13)$$ $$41 \equiv-37(\bmod 13)$$ $$41 \not \equiv 7(\bmod 13)$$

Баталгаа хялбархан тул дасгал болгон өөрсдөө хийгээрэй.

Баталгаа. $a, 2 a, \ldots,(p-1) a$ тоонуудыг авч үзье. Эдгээр тоонуудын хувьд $p$-д хуваахад ижил үлдэгдэл өгдөг тоонууд байдаг гэе. Тухайлбал, $1 \leq i< j \leq p-1$ ба $i a \equiv j a(\bmod p)$ байх $i,\ j $ тоонууд олддог гэвэл лемм 2 д) ёсоор $i\equiv j(\bmod p)$ болж зөрчилд хүрнэ. Эндээс $a, 2 a, \ldots,(p-1) a$ тоонууд $\bmod p$-ээр ялгаатай гэсэн дүгнэлт гарна. Мөн, $a$ нь $p$-д хуваагдахгүй гэдгээс $a, 2 a, \ldots,(p-1) a$ тоонуудыг $p$ хуваахад гарах үлдэгдлүүд нь $\{1,2,...,p-1\}$ байна гэж хэлж болно. Эндээс $$ a \cdot 2 a \cdots(p-1) a \equiv(p-1) !(\bmod p) $$ буюу $$ (p-1) ! \cdot a^{p-1} \equiv(p-1) !(\bmod p) $$ байна. $(p-1)!$ нь $p$-тэй харилцан анхны байна гэдгийг анхаараад хоёр талыг $(p-1)!$-д хуваавал $$a^{p-1}\equiv1(\bmod p)$$ болж теорем батлагдана. Энэхүү теорем нь зөвхөн $p$ анхны тооны хувьд ашиглагдана. Тэгвэл зохиомол тооны хувьд хэрхэх тухай дараах теоремыг тодорхойльё.

Баталгаа. $\mathbb{Z}_{n}^{*}=\left\{z_{1}, z_{2}, \ldots, z_{\varphi(n)}\right\}$ олонлогийг авч үзье. $z_{i}$ болон $a$ нь $n$-тэй харилцан анхны тул $z_{i} a$ нь $n$-тэй харилцан анхны байна. $z_1a,\ z_2a,...,z_{\varphi(n)}a$ тоонууд $\bmod n$-ээр бүгд ялгаатай болохыг Фермагийн бага теоремын баталгааны адилаар баталж болно. Эндээс, $$z_{1} a \cdot z_{2} a \cdot \ldots \cdot z_{\varphi(n)} a \equiv$$ $$\equiv z_{1} \cdot z_{2} \cdots \ldots \cdot z_{\varphi(n)}(\bmod n)$$ буюу хоёр талыг $z_1z_2...z_{\varphi(n)}$-д хуваагаад $$a^{\varphi(n)} \equiv 1(\bmod n)$$ болох нь батлагдана.