{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This is an ipython (jupyter) worksheet with code from the lecture notes for the course\n",
    "**Permutation Puzzles: A Mathematical Perspective**, by Jamie Mulholland\n",
    "\n",
    "Coures webpage: http://www.sfu.ca/~jtmulhol/math302 <br />\n",
    "Course notes booklet: http://www.sfu.ca/~jtmulhol/math302/notes/302notes.pdf"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Appendix B: Basic Properties of Integers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### B.1 Divisibility and the Euclidean Algorithm\n",
    "\n",
    "Python commands // and % are used to compute quotients and remainders respectively."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "29//8"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "29%8"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Greatest Common Divisor** (gcd)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "7"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "gcd(343,273)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The extended euclidean algorithm is used to write the gcd of two numbers as a linear combination of the two numbers.  `xgcd` is the command for the extended euclidean algorithm."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(7, 4, -5)"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "xgcd(343,273)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This means $7 = 4\\cdot343+(-5)\\cdot 273$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### B.2 Prime Numbers\n",
    "\n",
    "`is_prime` is the command to check if a number is prime, or not."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "is_prime(3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "is_prime(6)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Every interger can be factored into a product of primes."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2^3 * 11 * 13 * 4013"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "factor(4590872)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### B.3 Euler's $\\phi$-Function\n",
    "\n",
    "For any positive integer $n$, $\\phi(n)$ is the number of integers in $\\{1,2,...,n\\}$ which are relatively prime to $n$. In other words,\n",
    "$$\\phi(n)=|\\{m\\in \\mathbb{Z} \\mid 1\\le m \\le n, \\gcd(m,n)=1 \\}|.$$\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "32"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "euler_phi(96)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To find the 32 numbers relatively prime to 96 we can do the following."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1,\n",
       " 5,\n",
       " 7,\n",
       " 11,\n",
       " 13,\n",
       " 17,\n",
       " 19,\n",
       " 23,\n",
       " 25,\n",
       " 29,\n",
       " 31,\n",
       " 35,\n",
       " 37,\n",
       " 41,\n",
       " 43,\n",
       " 47,\n",
       " 49,\n",
       " 53,\n",
       " 55,\n",
       " 59,\n",
       " 61,\n",
       " 65,\n",
       " 67,\n",
       " 71,\n",
       " 73,\n",
       " 77,\n",
       " 79,\n",
       " 83,\n",
       " 85,\n",
       " 89,\n",
       " 91,\n",
       " 95]"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[n for n in range(1,97) if gcd(n,96)==1]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Or we could use a fliter with a lambda function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1,\n",
       " 5,\n",
       " 7,\n",
       " 11,\n",
       " 13,\n",
       " 17,\n",
       " 19,\n",
       " 23,\n",
       " 25,\n",
       " 29,\n",
       " 31,\n",
       " 35,\n",
       " 37,\n",
       " 41,\n",
       " 43,\n",
       " 47,\n",
       " 49,\n",
       " 53,\n",
       " 55,\n",
       " 59,\n",
       " 61,\n",
       " 65,\n",
       " 67,\n",
       " 71,\n",
       " 73,\n",
       " 77,\n",
       " 79,\n",
       " 83,\n",
       " 85,\n",
       " 89,\n",
       " 91,\n",
       " 95]"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "filter(lambda x: gcd(x,96)==1,range(1,97))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "SageMath 7.3",
   "language": "",
   "name": "sagemath"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}