Mathematik1_2019-10-29.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 1. Übungsaufgabe Kongruenz\n",
    "\n",
    "$\n",
    "x \\equiv 3 \\textrm{(mod 8)} \\implies 3, \\fbox{11}, 19, 27, ... \\\\\n",
    "x \\equiv 2 \\textrm{(mod 3)} \\implies 2, 5, 8, \\fbox{11}, 14, ... \\\\\n",
    "x \\equiv 1 \\textrm{(mod 5)} \\implies 1, 6, \\fbox{11}, 16, 21, ... \\\\\n",
    "$\n",
    "\n",
    "### 1. Kombination\n",
    "\n",
    "$\n",
    "3 * 5 * x \\equiv 3 \\textrm{(mod 8)} \\quad | \\quad 15 * x \\equiv 3\\textrm{(mod 8)}, \\quad 7 * x \\equiv 3 \\textrm{(mod 8)} \\\\\n",
    "-1 * x \\equiv 3 \\textrm{(mod 8)} \\\\\n",
    "x = -3 \\textrm{(mod 8)} \\\\\n",
    "x = 5 \\textrm{(mod 8)} \\\\\n",
    "15 * 5 = 75\n",
    "$\n",
    "<br>\n",
    "\n",
    "### 2. Kombination\n",
    "\n",
    "$\n",
    "8 * 3 * x \\equiv 1 \\textrm{(mod 3)} \\\\\n",
    "1 * x \\equiv 2 \\textrm{(mod 3)} \\\\\n",
    "x \\equiv 2 \\textrm{(mod 3)} \\\\\n",
    "40 * 2 = 80\n",
    "$\n",
    "<br>\n",
    "\n",
    "### 3. Kombination\n",
    "\n",
    "$\n",
    "8 * 3 * x \\equiv 1 \\textrm{(mod 5)} \\\\\n",
    "4 * x \\equiv 1 \\textrm{(mod 5)} \\\\\n",
    "x \\equiv 4 \\textrm{(mod 5)} \\\\\n",
    "24 * 4 = 96\n",
    "$\n",
    "<br>\n",
    "\n",
    "### 4. Zusammenführen\n",
    "\n",
    "$\n",
    "75 + 80 + 96 = 251 \\\\\n",
    "3 * 5 * 8 = 120 \\\\\n",
    "251 = 2 * 120 + 11\n",
    "$\n",
    "\n",
    "$\n",
    "\\mathbb{Z} = 8 * 3 * 5 \\\\\n",
    "x = 11 \\textrm{ in } \\mathbb{Z}/200\\mathbb{Z}\n",
    "$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_mod_nums(mod, number, amount):\n",
    "    values = []\n",
    "    current = number\n",
    "    while len(values) < amount:\n",
    "        if current % mod == number:\n",
    "            values.append(current)\n",
    "        current += 1\n",
    "    return values"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[3, 11, 19, 27, 35, 43, 51, 59, 67, 75]"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "get_mod_nums(8, 3, 10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 5, 8, 11, 14, 17, 20, 23, 26, 29]"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "get_mod_nums(3, 2, 10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 6, 11, 16, 21, 26, 31, 36, 41, 46]"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "get_mod_nums(5, 1, 10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(mpz(11), 120)"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# with a library function\n",
    "from sympy.ntheory.modular import crt\n",
    "crt([8, 3, 5], [3, 2, 1])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 2. Kleiner Satz von Fermat"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [],
   "source": [
    "def ferm(p):\n",
    "    return [a ** (p - 1) % p for a in range(2, p)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 1, 1]"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ferm(5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [],
   "source": [
    "from random import randrange\n",
    "\n",
    "def fermat_test(n):\n",
    "    return (randrange(2, n) ** (n - 1)) % n == 1\n",
    "\n",
    "def fermat_test_prob(n, amount):\n",
    "    s = 0\n",
    "    for i in range(0, amount):\n",
    "        if fermat_test(n):\n",
    "            s += 1\n",
    "    return s / amount"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1.0"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "fermat_test_prob(29, 100000)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1.0"
      ]
     },
     "execution_count": 47,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "fermat_test_prob(3, 10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1.0"
      ]
     },
     "execution_count": 51,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "fermat_test_prob(29, 3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1.0"
      ]
     },
     "execution_count": 60,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "fermat_test_prob(2**16 + 1, 100)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 3. Rationale Zahlen"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.3333333333333333"
      ]
     },
     "execution_count": 61,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# rundungsfehler ...\n",
    "1/3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.6666666666666666"
      ]
     },
     "execution_count": 63,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# ... über rundungsfehler\n",
    "2/3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1.0"
      ]
     },
     "execution_count": 65,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# ... über noch mehr rundungsfehler,\n",
    "# die dann doch wieder stimmen.\n",
    "3*(1/3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Python kann auch Brüche!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "metadata": {},
   "outputs": [],
   "source": [
    "from fractions import Fraction"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Fraction(3, 4)"
      ]
     },
     "execution_count": 67,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Fraction(3, 4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Fraction(3, 4)"
      ]
     },
     "execution_count": 68,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Fraction(3/4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Fraction(1, 2)"
      ]
     },
     "execution_count": 69,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Fraction(0.5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Fraction(7034025480755159, 140737488355328)"
      ]
     },
     "execution_count": 73,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Präzision lässt irgendwann nach\n",
    "Fraction(12345 / 247)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 75,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Fraction(12345, 247)"
      ]
     },
     "execution_count": 75,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# besser als zwei getrennte Argumente\n",
    "Fraction(12345, 247)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 86,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Fraction(12345, 247)"
      ]
     },
     "execution_count": 86,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Oder als string (ih, bäh)\n",
    "Fraction('12345/247')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}