The_Euclidean_Algorithm.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "The Euclidean Algorithm.ipynb",
      "provenance": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "code",
      "metadata": {
        "id": "JARCuvjv7LK5"
      },
      "source": [
        "def gcd_it(a,b):\n",
        "  if a == 0 and b == 0:\n",
        "    raise ValueError(\"both entries cannot be 0\")\n",
        "    #if a and b are both zero, raise error\n",
        "  else:\n",
        "    if abs(b) >= abs(a):\n",
        "      k = a\n",
        "      a = b\n",
        "      b = k\n",
        "      #if b has a larger magnitude than a, then swap a and b\n",
        "    r = a%b\n",
        "    #r is the remainder of a divided by b\n",
        "    while r != 0:\n",
        "      a = b\n",
        "      b = r\n",
        "      r = a%b\n",
        "      #while r is not 0, set equal to b, b equal to the previous r, and the new r is the remainder of the new a divided by the new b\n",
        "      if r == 0:\n",
        "        return abs(b)\n",
        "        #if r equals 0 return the magnitude of the current b"
      ],
      "execution_count": 1,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "Haril9vw_71J",
        "outputId": "4c112b2f-c647-4051-954f-7ee79468769b"
      },
      "source": [
        "def gcd(a,b):\n",
        "  if a == 0 and b == 0:\n",
        "    raise ValueError(\"both entries cannot be 0\")\n",
        "    #if a and b are both zero, raise error\n",
        "  else:\n",
        "    if abs(b) > abs(a):\n",
        "      k = a\n",
        "      a = b\n",
        "      b = k\n",
        "      #if b > a, then swap a and b\n",
        "    if b == 0:\n",
        "      return a\n",
        "      #if b is zero, then the gcd is a\n",
        "    else:\n",
        "      return gcd(b,(a%b))\n",
        "        #if both a and b are non-zero, then run the code again with a = b, and b = a%b, until b = 0\n",
        "gcd(112233,445566)"
      ],
      "execution_count": 6,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "33"
            ]
          },
          "metadata": {},
          "execution_count": 6
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "aFViS7B9B3xt",
        "outputId": "e02093cf-ace8-4853-c68a-729fadd1a720"
      },
      "source": [
        "def xgcd(a,b):\n",
        "  if a == 0 and b == 0:\n",
        "    raise ValueError(\"both entries cannot be 0\")\n",
        "    #if a and b are both zero, raise error\n",
        "  else:\n",
        "    if abs(a) >= abs(b):\n",
        "      if b == 0:\n",
        "        #if b is zero...\n",
        "        if a < 0:\n",
        "          return [abs(a),-1,0]\n",
        "          #...and a is negative, return the magnitude of a, x = -1, and y = 0\n",
        "        if a > 0:\n",
        "          return [abs(a),1,0]\n",
        "          #... and a is positive return the magnitude of a, x = 1, and y = 0\n",
        "      else:\n",
        "        [d,x,y] = xgcd(b,a%b)\n",
        "        #[d,x,y] is equal to the recursion of (b,a%b)\n",
        "        Y = x - (a//b)*y\n",
        "        #the new Y is equal to the old x minus the lower round of (a/b) times the old y\n",
        "        X = y\n",
        "        #the new X is the old y\n",
        "        return[d,X,Y]\n",
        "    if abs(a) < abs(b):\n",
        "      if a == 0:\n",
        "        #if a is zero...\n",
        "        if b < 0:\n",
        "          return [abs(b),0,-1]\n",
        "          #...and b is negative, return the magnitude of b, x = 0, and y = -1\n",
        "        if b > 0:\n",
        "          return [abs(b),0,1]\n",
        "          #...and b is positive, return the magnitude of b, x = 0, and y = 0\n",
        "      else:\n",
        "        [d,x,y] = xgcd(b%a,a)\n",
        "        #[d,x,y] is equal to the recursion of (b%a,a)\n",
        "        X = y - (b//a)*x\n",
        "        #the new X is equal to the old y minus the lower round of (b/a) times the old x\n",
        "        Y = x\n",
        "        #the new Y is the old x\n",
        "        return[d,X,Y]\n",
        "xgcd(112233,445566)"
      ],
      "execution_count": 26,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[33, -4633, 1167]"
            ]
          },
          "metadata": {},
          "execution_count": 26
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "AmDPZCKsNszT",
        "outputId": "e12d0315-d4af-43f8-f377-e6aa2fba90d9"
      },
      "source": [
        "def s12mat(a,b):\n",
        "  if gcd(a,b) != 1:\n",
        "    raise ValueError(\"a and b are not relatively prime\")\n",
        "    #check that a and b are relatively prime\n",
        "  else:\n",
        "    [d,x,y] = xgcd(a,b)\n",
        "    #make the set [d,x,y] such that ax+by = 1\n",
        "    return [[a,b],[-y,x]]\n",
        "    #return this matrix because ax-by = 1, is the determinant equalling 1\n",
        "s12mat(1,7)"
      ],
      "execution_count": 35,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[[1, 7], [0, 1]]"
            ]
          },
          "metadata": {},
          "execution_count": 35
        }
      ]
    }
  ]
}