Chapter_31_Number-Theoretic_Algorithms/exercises_31.5.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 31.5 The Chinese remainder theorem"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 31.5-1\n",
    "\n",
    "> Find all solutions to the equations $x \\equiv 4 ~(\\text{mod}~5)$ and $x \\equiv 5 ~(\\text{mod}~11)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$m_1 = 11$, $m_2 = 5$.\n",
    "\n",
    "$m_1^{-1} = 1$, $m_2^{-1} = 9$.\n",
    "\n",
    "$c_1 = 11$, $c_2 = 45$.\n",
    "\n",
    "$a = (c_1 \\cdot a_1 + c_2 \\cdot a_2) ~\\text{mod}~ (n_1 \\cdot n_2) = (11 * 4 + 45 * 5) ~\\text{mod}~ 55 = 49$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 31.5-2\n",
    "\n",
    "> Find all integers $x$ that leave remainders $1, 2, 3$ when divided by $9, 8, 7$ respectively."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$10 + 504i$, $i \\in \\mathbb{Z}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 31.5-3\n",
    "\n",
    "> Argue that, under the definitions of Theorem 31.27, if $\\text{gcd}(a, n) = 1$, then\n",
    "> \n",
    ">  $(a^{-1} ~\\text{mod}~ n) \\leftrightarrow ((a_1^{-1} ~\\text{mod}~ n_1), (a_2^{-1} ~\\text{mod}~ n_2), \\dots, (a_k^{-1} ~\\text{mod}~ n_k))$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$\\text{gcd}(a, n) = 1 \\rightarrow \\text{gcd}(a, n_i) = 1$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 31.5-4\n",
    "\n",
    "> Under the definitions of Theorem 31.27, prove that for any polynomial $f$, the number of roots of the equation $f(x) \\equiv 0 ~(\\text{mod}~n)$ equals the product of the number of roots of each of the equations $f(x) \\equiv 0 ~(\\text{mod}~n_1), f(x) \\equiv 0 ~(\\text{mod}~n_2), \\dots, f(x) \\equiv 0 ~(\\text{mod}~n_k)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Based on 31.28 ~ 31.30."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}