{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Chapter11 - Properties of integers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Ex11.2 Pg 319"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Division Algorithm\n",
      "a and j have equal values.Hence division algorithm is proved\n"
     ]
    }
   ],
   "source": [
    "from numpy import divide\n",
    "print 'Division Algorithm'\n",
    "a=4461#  #dividend\n",
    "b=16#    #divisor\n",
    "r=(a%b)  #remainder\n",
    "k=divide(a,b)    #quotient\n",
    "j=b*k+r  #dividend=divisor*quotient+remainder\n",
    "\n",
    "a=-262#  #dividend\n",
    "b=3#    #divisor\n",
    "k=divide(a,b)  #remainder\n",
    "r=(a%b)    #quotient\n",
    "j=b*k+r  #dividend=divisor*quotient+remainder\n",
    "print 'a and j have equal values.Hence division algorithm is proved'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Ex11.4 Pg 320"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Divisibility and Primes\n",
      "prime numbers less than 50 are\n",
      "the prime factorisation of 21,24 and 1729 respectively are:\n",
      "[3, 7] [2, 2, 2, 3] [7, 13, 19]\n"
     ]
    }
   ],
   "source": [
    "from math import floor\n",
    "print 'Divisibility and Primes'\n",
    "x=50#\n",
    "print 'prime numbers less than 50 are'\n",
    "def get_primes(n):\n",
    "    numbers = set(range(n, 1, -1))\n",
    "    primes = []\n",
    "    while numbers:\n",
    "        p = numbers.pop()\n",
    "        primes.append(p)\n",
    "        numbers.difference_update(set(range(p*2, n+1, p)))\n",
    "    return primes\n",
    "\n",
    "y=get_primes(x)\n",
    "\n",
    "print 'the prime factorisation of 21,24 and 1729 respectively are:'\n",
    "\n",
    "def factors(n):\n",
    "    primfac = []\n",
    "    d = 2\n",
    "    while d*d <= n:\n",
    "        while (n % d) == 0:\n",
    "            primfac.append(d)  # supposing you want multiple factors repeated\n",
    "            n //= d\n",
    "        d += 1\n",
    "    if n > 1:\n",
    "       primfac.append(n)\n",
    "    return primfac\n",
    "\n",
    "k=factors(21)\n",
    "l=factors(24)\n",
    "n=factors(1729)\n",
    "print k,l,n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Ex11.5 Pg 321"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "the GCD of the following numbers is:\n",
      "gcd(12,18) =  [6]\n",
      "gcd(12,-18) =  [6]\n",
      "gcd(12,-16) =  [4]\n",
      "gcd(29,15) =  [1]\n",
      "gcd(14,49) =  [7]\n"
     ]
    }
   ],
   "source": [
    "from numpy import int32\n",
    "import numpy as np\n",
    "print 'the GCD of the following numbers is:'\n",
    "def gcd(a, b):\n",
    "    a, b = np.broadcast_arrays(a, b)\n",
    "    a = a.copy()\n",
    "    b = b.copy()\n",
    "    pos = np.nonzero(b)[0]\n",
    "    while len(pos) > 0:\n",
    "        b2 = b[pos]\n",
    "        a[pos], b[pos] = b2, a[pos] % b2\n",
    "        pos = pos[b[pos]!=0]\n",
    "    return abs(a)\n",
    "print \"gcd(12,18) = \",gcd([12],[18])\n",
    "print \"gcd(12,-18) = \",gcd([12],[-18])\n",
    "print \"gcd(12,-16) = \",gcd([12],[-16])\n",
    "print \"gcd(29,15) = \",gcd([29],[15])\n",
    "print \"gcd(14,49) = \",gcd([14],[49])\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Ex11.6 Pg 322"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Euclidean Algorithm\n",
      "540.0\n",
      "168.0\n",
      "36.0\n",
      "24.0\n",
      "for the equation 540*x+168*y=12,we are given\n",
      "x=5 and y=16\n"
     ]
    }
   ],
   "source": [
    "from numpy import floor\n",
    "print 'Euclidean Algorithm'\n",
    "a=[540,168,36,24]#\n",
    "b=[168,36,24,12]#\n",
    "thegcd=[]\n",
    "for i in range(0,4):\n",
    "    thegcd.append(gcd(a,b))\n",
    "    \n",
    "\n",
    "\n",
    "def myf(dividend,divisor):\n",
    "    quotient=floor(dividend/divisor)#\n",
    "    rem=(dividend%divisor)#\n",
    "    k=quotient*divisor+rem#\n",
    "    print k\n",
    "    if(rem!=0):\n",
    "        myf(divisor,rem) \n",
    "\n",
    "\n",
    "\n",
    "myf(540,168)\n",
    "\n",
    "print 'for the equation 540*x+168*y=12,we are given'\n",
    "a=540#\n",
    "b=168#\n",
    "c=24#\n",
    "d=36#\n",
    "d=a-3*b#     #Eqn (1)\n",
    "c=b-4*d#      #Eqn (2)\n",
    "k=d-1*c#    #Eqn (3)\n",
    "5*d-1*b#      #Eqn (4)\n",
    "k=d-b+4*d#     #substituting value of c in Eqn (3) from Eqn (2) \n",
    "r=5*a-16*b#    \n",
    "if(r==k):\n",
    "    print 'x=5 and y=16'#    \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Ex11.9 Pg 324"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "gcd(a,b) = [792]\n",
      "lcm(a,b) = 183783600\n"
     ]
    }
   ],
   "source": [
    "a=2**4*3**3*7*11*13\n",
    "b=2**3*3**2*5**2*11*17\n",
    "d=gcd([a],[b])\n",
    "print \"gcd(a,b) =\",d\n",
    "lcm1=2**4*3**3*5**2*7*11*13*17   #lcm is the product of those primes which appear in either a or b\n",
    "print \"lcm(a,b) =\",lcm1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Ex11.19 Pg 332"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "solving for the congruence equation 8x @ 12(mod 28) ,where @ is the sign for congruence\n",
      "k is the unique solution of the equation \n",
      "solutions of the original equation at d=4\n",
      "[5]\n",
      "[12]\n",
      "[19]\n",
      "[26]\n"
     ]
    }
   ],
   "source": [
    "print 'solving for the congruence equation 8x @ 12(mod 28) ,where @ is the sign for congruence'\n",
    "a=8#\n",
    "b=12#\n",
    "m=28#\n",
    "d= gcd([a],[m])#\n",
    "a1= a/d#\n",
    "b1= b/d#\n",
    "m1= m/d#\n",
    " \n",
    "def f(x):\n",
    "    yd= (a1*x)-b1\n",
    "    return yd\n",
    " \n",
    "print 'k is the unique solution of the equation '\n",
    "for i in range(0,m1):\n",
    "    x=i#\n",
    "    p=f(x)#\n",
    "    if((p%m1) == 0):\n",
    "        k=x\n",
    "        break#\n",
    "\n",
    "s1=[k]#\n",
    "s2=k+m1#\n",
    "s3=k+(m1*2)#\n",
    "s4=k+(m1*3)#\n",
    "print 'solutions of the original equation at d=4'\n",
    "print s1\n",
    "print s2\n",
    "print s3\n",
    "print s4"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "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.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}