http://vmath.ru/vf5/ 2026-10-13T03:42:32+0300 http://vmath.ru/vf5/ http://vmath.ru/vf5/lib/tpl/vf5/images/favicon.ico text/html 2024-10-03T09:13:13+0300 Anonymous (anonymous@undisclosed.example.com) http://vmath.ru/vf5/modular/crt?rev=1727935993&do=diff МОДУЛЯРНАЯ АРИФМЕТИКА ---------- Китайская теорема об остатках Пример$ 3_{} $$ 2_{} $$ 7_{} $$ 3_{} $$ 10_{} $---$ 9_{} $ Решение. Пусть $ u,v,w $ --- частные от деления неизвестного числа на $ 3, 7 $ и $ 10_{} $ соответственно. Имеем: $$ 3\,u+2=7\,v+3,\ 3\,u+2=10\, w+9,\ 7\,v+3=10\, w+9 \ . $$ Решаем последнее уравнение в целых числах, применяя рассуждения, приведенные $$ w=7\,t_1-2,\ v=10\,t_1-2 \quad npu \quad \forall t_1 \in \mathbb Z \ . $$$ v_{} $$ 3\,u+2=7\,v+3 $$$ 3\,u-70\, t_1=-13 \… text/html 2020-06-11T20:24:12+0300 Anonymous (anonymous@undisclosed.example.com) http://vmath.ru/vf5/modular/easter?rev=1591896252&do=diff МОДУЛЯРНАЯ АРИФМЕТИКА ---------- Определение даты Пасхи по году Следующие правила составлены Гауссом, я их взял из , но для православной Пасхи при переводе в новый стиль пришлось вносить коррективы.$ N_{} $$ C_{} $$ C=\lfloor N/100 \rfloor $$ N_{} $$ 4,7,19 $$$a= N \pmod{4}, \quad b= N \pmod{7},\quad c= N \pmod{19} \ . $$$$ M=15+C- \left\lfloor \frac{C}{4} \right\rfloor - \left\lfloor \frac{8\,C+13}{25} \right\rfloor \ , \quad L=4+C- \left\lfloor \frac{C}{4} \right\rfloor \ . $$$$ d=19\,c+M \p… text/html 2025-01-17T13:00:19+0300 Anonymous (anonymous@undisclosed.example.com) http://vmath.ru/vf5/modular/eulert?rev=1737108019&do=diff Теорема ЭйлераТеорема [Эйлер].Для любых натуральных взаимно простых$ A_{} $и$ M_{}>1 $выполняется $$ A^{\phi(M)}\equiv 1 \pmod{M} \ , $$ здесь $ \phi $ означает функцию Эйлера. Доказательство. Пусть известно каноническое разложение числа $ M_{} $$$ M=p_1^{{\mathfrak m}_1}p_2^{{\mathfrak m}_2}\times \dots \times p_{\mathfrak r}^{{\mathfrak m}_{\mathfrak r}} \ . $$$$ \phi (M) =\prod_{j=1}^{\mathfrak r} p_j^{{\mathfrak m}_j-1}(p_j-1)\ . $$$$ A^{p_j^{{\mathfrak m}_j-1}(p_j-1)} \equiv 1 \pmod{p_… text/html 2024-10-24T17:25:54+0300 Anonymous (anonymous@undisclosed.example.com) http://vmath.ru/vf5/modular/index?rev=1729779954&do=diff МОДУЛЯРНАЯ АРИФМЕТИКА--- Индекс (дискретный логарифм) Первообразный корень Задача. Найти длину цикла последовательности $ \{A^j \pmod{M} \}_{j=0}^{\infty} $ . Для случая простого модуля верхняя оценка для длины цикла дается $ p_{} $$ A_{} $$ p_{} $$$ A^{p-1} \equiv 1 \pmod{p} \ . $$$ A_{} $$$ \begin{array}{ccl} \left\{3^j \pmod{17} \right\}_{j=0}^{\infty}&=& 1,\, 3,\, 9,\,10,\, 13,\, 5,\,15,\,11,\,16,\,14,\,8,\,7,\,4,\,12,\,2,\,6,\,1,\dots ; \\ \left\{4^j \pmod{17} \right\}_{j=0}^{\inf… text/html 2021-09-06T17:49:28+0300 Anonymous (anonymous@undisclosed.example.com) http://vmath.ru/vf5/modular/problems?rev=1630939768&do=diff МОДУЛЯРНАЯ АРИФМЕТИКА ---------- Задачи Решить сравнения $$ {\mathbf a)} \ x^{p-2} \equiv p-1 \pmod{p} \qquad ; \qquad {\mathbf b)} \ x^{p-2} \equiv \frac{p-1}{2} \pmod{p} $$ для простого $ p>2 $. Вычислить $$ {\mathbf a)} \ (p-3)! \pmod{p} \qquad ; \qquad {\mathbf b)} \ (p-4)! \pmod{p} , $$ для простого $ p\ge 5 $. Доказать, что для $ j \in \{1,2,\dots,p-2 \} $ выполняется $$ [ j! ]^{-1} \equiv (-1)^{j-1} (p-j-1)! \pmod{p} \, . $$ . Вычислить три последние цифры числа $ 7^{9999} … text/html 2020-03-11T14:00:22+0300 Anonymous (anonymous@undisclosed.example.com) http://vmath.ru/vf5/modular/vspom1?rev=1583924422&do=diff $ 874 $. text/html 2020-03-11T14:00:22+0300 Anonymous (anonymous@undisclosed.example.com) http://vmath.ru/vf5/modular/vspom2?rev=1583924422&do=diff а) $ 35 $ ; б) $ 93 $ text/html 2020-03-11T14:00:22+0300 Anonymous (anonymous@undisclosed.example.com) http://vmath.ru/vf5/modular/vspom3?rev=1583924422&do=diff $ 41 $ ; $ 101 $ text/html 2023-12-03T17:34:14+0300 Anonymous (anonymous@undisclosed.example.com) http://vmath.ru/vf5/modular/vspom4?rev=1701614054&do=diff МОДУЛЯРНАЯ АРИФМЕТИКА... Решение системы линейных уравнений в целых числах Решение системы линейных уравнений $$ \left\{ \begin{array}{lllll} a_{11}x_1 &+a_{12}x_2&+ \ldots&+a_{1n}x_n &= b_1,\\ a_{21}x_1 &+a_{22}x_2&+ \ldots&+a_{2n}x_n &= b_2,\\ \dots & & & \dots & \\ a_{m1}x_1 &+a_{m2}x_2&+ \ldots&+a_{mn}x_n &= b_m \end{array} \right. $$ с целыми коэффициентами $ \{a_{jk} \}, \{b_j\} $ в целых числах $ x_1,x_2,\dots,x_n $ можно свести к случаю одного уравнения.$ A_1x+A_2y=B $$ x_{} $$ y_{} $… text/html 2021-09-06T17:45:29+0300 Anonymous (anonymous@undisclosed.example.com) http://vmath.ru/vf5/modular/vspom5?rev=1630939529&do=diff ТЕОРЕМА ФЕРМА ---------- Теорема [Ферма (малая)].Если$ p_{} $простое и$ A_{} $не делитсяна$ p_{} $то$$ A^{p-1} \equiv 1 \pmod{p} \ . $$ Доказательство основано на одном свойстве биномиальных коэффициентов. Если внимательно рассмотреть $$ \begin{array}{l|cccccccccccccccc} &&&&&&&&1 \\ n=1&&&&&&& 1 && 1 \\ n=2&&&&&& 1 && 2 && 1 \\ n=3&&&&&1 && 3 && 3 && 1 \\ n=4&&&&1 && 4 && 6 && 4 && 1 \\ n=5&&&1 && 5 && 10 && 10 && 5 && 1 \\ n=6&&1 && 6 && 15 && 20 && 15 && 6 && 1 \\ n=7&1 && 7 && 21 && 35 && … text/html 2025-10-03T09:16:40+0300 Anonymous (anonymous@undisclosed.example.com) http://vmath.ru/vf5/modular/wilson?rev=1759472200&do=diff МОДУЛЯРНАЯ АРИФМЕТИКА ---------- Критерий Вильсона Теорема [Вильсон]Для того чтобы число$ p>2 $было простым, необходимо и достаточно, чтобы выполнялось сравнение $$ (p-1)! \equiv -1 \pmod{p} \ . $$ Доказательство.$ p_{} $$ A\in \{1,\dots, p-1 \} $$ Ax\equiv 1 \pmod{p} $$ \tilde A_{} $$ A_{} $$ \tilde A_{} $$ A = \tilde A_{} $$ A =1 $$ A =p-1 $$$A^2 \equiv 1 \pmod{p} $$$$(A-1)(A+1) \equiv 0 \pmod{p} \quad \iff \quad A \equiv 1 \pmod{p} \ \mbox{ или } \ A \equiv -1 \pmod{p} \ .$$$ 2, 3,\dots…