задание 3

1 files changed, 112 insertions, 0 deletions

diff --git a/t4mk.ipynb b/t4mk.ipynb
index ce13d34..517014a 100644
--- a/t4mk.ipynb
+++ b/t4mk.ipynb
@@ -225,6 +225,118 @@
    ]
   },
   {
+   "cell_type": "code",
+   "execution_count": 82,
+   "metadata": {},
+   "outputs": [
+    {
+     "data": {
+      "text/latex": [
+       "$\\displaystyle M = 3 \\cdot 5 \\cdot 4 = 60$"
+      ],
+      "text/plain": [
+       "<IPython.core.display.Math object>"
+      ]
+     },
+     "metadata": {},
+     "output_type": "display_data"
+    },
+    {
+     "data": {
+      "text/latex": [
+       "$\\displaystyle M_{1} = 20; 20 x \\equiv 1 \\pmod{3}; z_{1} = 2$"
+      ],
+      "text/plain": [
+       "<IPython.core.display.Math object>"
+      ]
+     },
+     "metadata": {},
+     "output_type": "display_data"
+    },
+    {
+     "data": {
+      "text/latex": [
+       "$\\displaystyle M_{2} = 12; 12 x \\equiv 3 \\pmod{5}; z_{2} = 4$"
+      ],
+      "text/plain": [
+       "<IPython.core.display.Math object>"
+      ]
+     },
+     "metadata": {},
+     "output_type": "display_data"
+    },
+    {
+     "data": {
+      "text/latex": [
+       "$\\displaystyle M_{3} = 15; 15 x \\equiv 2 \\pmod{4}; z_{3} = 2$"
+      ],
+      "text/plain": [
+       "<IPython.core.display.Math object>"
+      ]
+     },
+     "metadata": {},
+     "output_type": "display_data"
+    },
+    {
+     "data": {
+      "text/latex": [
+       "$\\displaystyle x = M_{0} \\cdot z_{0} + M_{1} \\cdot z_{1} + M_{2} \\cdot z_{2} = 20 \\cdot 2 + 12 \\cdot 4 + 15 \\cdot 2 = 58 \\pmod{60}$"
+      ],
+      "text/plain": [
+       "<IPython.core.display.Math object>"
+      ]
+     },
+     "metadata": {},
+     "output_type": "display_data"
+    }
+   ],
+   "source": [
+    "ai, mi = [1, 3, 2], [3, 5, 4]\n",
+    "\n",
+    "def gcd_extended(x1, x2):\n",
+    "    if x1 == 0:\n",
+    "        return x2, 0, 1\n",
+    "    else:\n",
+    "        div, x, y = gcd_extended(x2 % x1, x1)\n",
+    "    return div, y - (x2 // x1) * x, x\n",
+    "\n",
+    "def inverse(a, m):\n",
+    "    d, u, v = gcd_extended(a, m)\n",
+    "    if d != 1:\n",
+    "        print('Нет обратного у элемента a =', a, 'в кольце вычетов по модулю', m)\n",
+    "        exit()\n",
+    "    x = u % m\n",
+    "    return x\n",
+    "\n",
+    "def greco_chinese_theorem(u, m):\n",
+    "    ltx = []\n",
+    "    M = 1\n",
+    "    for i in m:\n",
+    "        M *= i\n",
+    "    tmp = ' \\\\cdot '\n",
+    "    ltx.append(f\"M = {tmp.join(map(str, m))} = {M}\")\n",
+    "\n",
+    "    tmp1 = []\n",
+    "    tmp2 = []\n",
+    "    x = 0\n",
+    "    for i in range(len(m)):\n",
+    "        c = M // m[i]\n",
+    "        d = inverse(c, m[i])\n",
+    "        x += c * d * u[i]\n",
+    "        ltx.append(f\"M_{{{i + 1}}} = {c}; {c} x \\\\equiv {u[i]} \\\\pmod{{{m[i]}}}; z_{{{i + 1}}} = {(d * u[i]) % m[i]}\")\n",
+    "        tmp1.append(f\"M_{{{i + 1}}} \\cdot z_{{{i + 1}}}\")\n",
+    "        tmp2.append(f\"{c} \\cdot {(d * u[i]) % m[i]}\")\n",
+    "    \n",
+    "    ltx.append(f\"x = {' + '.join(tmp1)} = {' + '.join(tmp2)} = {x % M} \\\\pmod{{{M}}}\")\n",
+    "\n",
+    "    return ltx, x % M\n",
+    "\n",
+    "ltx, x = greco_chinese_theorem(ai, mi)\n",
+    "for line in ltx:\n",
+    "    display(Math(line))"
+   ]
+  },
+  {
    "cell_type": "markdown",
    "metadata": {},
    "source": [