Basic Number Theory.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "# Number theory\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "# Bézout’s lemma and the extended Euclidean algorithm\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "Error Checking:\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The GCD of 45 and 33 is 3\n",
      "Bezout's coefficients are: 3 and -4\n",
      "45 and 33 are not coprime, so the modular inverse does not exist\n"
     ]
    }
   ],
   "source": [
    "def find_gcd_bezout_and_inverse(a, b):\n",
    "    # Use the extended_gcd function from Sage's Integer type\n",
    "    gcd, s, t = Integer(a).xgcd(Integer(b))\n",
    "\n",
    "    # Print out the GCD and Bezout's coefficients\n",
    "    print(f\"The GCD of {a} and {b} is {gcd}\")\n",
    "    print(f\"Bezout's coefficients are: {s} and {t}\")\n",
    "\n",
    "    # Check for coprimes\n",
    "    if gcd == 1:\n",
    "        # If so, print the modular inverse\n",
    "        print(f\"The modular inverse of {a} modulo {b} is {s % b}\")\n",
    "    else:\n",
    "        # If the GCD is not 1, then a and b are not coprime and the modular inverse does not exist\n",
    "        print(f\"{a} and {b} are not coprime, so the modular inverse does not exist\")\n",
    "\n",
    "# Call the function with two integers\n",
    "find_gcd_bezout_and_inverse(45, 33)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "# Modular Inverse Code Extension\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The GCD of 93 and 64 is 1\n",
      "Bezout's coefficients are: -11 and 16\n",
      "The modular inverse of 93 modulo 64 is 53\n"
     ]
    }
   ],
   "source": [
    "def find_gcd_bezout_and_inverse(a, b):\n",
    "    # Use the extended_gcd function from Sage's Integer type\n",
    "    gcd, s, t = Integer(a).xgcd(Integer(b))\n",
    "\n",
    "    # Print out the GCD and Bezout's coefficients\n",
    "    print(f\"The GCD of {a} and {b} is {gcd}\")\n",
    "    print(f\"Bezout's coefficients are: {s} and {t}\")\n",
    "\n",
    "    # Check for coprimes\n",
    "    if gcd == 1:\n",
    "        # If so, print the modular inverse\n",
    "        print(f\"The modular inverse of {a} modulo {b} is {s % b}\")\n",
    "    else:\n",
    "        # If the GCD is not 1, then a and b are not coprime and the modular inverse does not exist\n",
    "        print(f\"{a} and {b} are not coprime, so the modular inverse does not exist\")\n",
    "\n",
    "# Call the function with two integers\n",
    "find_gcd_bezout_and_inverse(93, 64)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "# Solving Linear Equations\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The GCD of 7 and 9 is 1\n",
      "Bezout's coefficients are: 4 and -3\n",
      "The modular inverse of 7 modulo 9 is 4\n",
      "The solution to the equation 7x ≡ 5 mod 9 is x = 2\n"
     ]
    }
   ],
   "source": [
    "def solve_modular_linear_equation(a, b, n):\n",
    "    # Use the extended_gcd function \n",
    "    gcd, s, t = Integer(a).xgcd(Integer(n))\n",
    "\n",
    "    # Print out the GCD and Bezout's coefficients\n",
    "    print(f\"The GCD of {a} and {n} is {gcd}\")\n",
    "    print(f\"Bezout's coefficients are: {s} and {t}\")\n",
    "\n",
    "    # Check for coprimes\n",
    "    if gcd == 1:\n",
    "        # If so, print the modular inverse  s\n",
    "        print(f\"The modular inverse of {a} modulo {n} is {s % n}\")\n",
    "\n",
    "        # Use the modular inverse to solve the modular linear equation\n",
    "        x = (b * s) % n\n",
    "        print(f\"The solution to the equation {a}x ≡ {b} mod {n} is x = {x}\")\n",
    "    else:\n",
    "        # If the GCD is not 1, then a and n are not coprime and the modular inverse does not exist\n",
    "        print(f\"{a} and {n} are not coprime, so the modular inverse does not exist\")\n",
    "        print(f\"Hence, the linear equation {a}x ≡ {b} mod {n} has no solution.\")\n",
    "\n",
    "# Call the function with the coefficients of the linear equation \n",
    "# Format is ax ≡ b mod c, input below is \"(a, b, c)\"\n",
    "solve_modular_linear_equation(7, 5, 9)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "# Solving Linear Equations with Composite Modulo\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The GCD of 18 and 59 is 1\n",
      "The simplified linear equation is 18x ≡ 34 mod 59\n",
      "The modular inverse of 18 modulo 59 is 23\n",
      "The solution to the equation 18x ≡ 34 mod 59 is x ≡ 15\n",
      "The solutions of the additional congruences are: \n",
      "x_0 ≡ 15 mod 59\n"
     ]
    }
   ],
   "source": [
    "def solve_composite_modular_linear_equation(a, b, n):\n",
    "    # Use the extended_gcd function from Sage's Integer type\n",
    "    d, s, t = Integer(a).xgcd(Integer(n))\n",
    "\n",
    "    # Print out the GCD\n",
    "    print(f\"The GCD of {a} and {n} is {d}\")\n",
    "\n",
    "    # Check if d divides b\n",
    "    if b % d != 0:\n",
    "        # If not, print an error message and return\n",
    "        print(f\"{b} is not divisible by {d}, so the linear equation {a}x ≡ {b} mod {n} has no solution.\")\n",
    "        return\n",
    "\n",
    "    # Divide a, b, and n by d to simplify the equation\n",
    "    a2, b2, n2 = a // d, b // d, n // d\n",
    "\n",
    "    # Print the simplified linear equation\n",
    "    print(f\"The simplified linear equation is {a2}x ≡ {b2} mod {n2}\")\n",
    "\n",
    "    # Use the extended_gcd function again to find the GCD of a2 and n2 and the Bezout coefficients\n",
    "    gcd, s2, t2 = Integer(a2).xgcd(Integer(n2))\n",
    "\n",
    "    # Check Coprimes\n",
    "    if gcd == 1:\n",
    "        # If so, print the modular inverse of a2 modulo n2\n",
    "        print(f\"The modular inverse of {a2} modulo {n2} is {s2 % n2}\")\n",
    "\n",
    "        # Use the modular inverse to solve the modular linear equation\n",
    "        x = (b2 * s2) % n2\n",
    "        print(f\"The solution to the equation {a2}x ≡ {b2} mod {n2} is x ≡ {x}\")\n",
    "\n",
    "        # Find additional solutions\n",
    "        i = 0\n",
    "        print(f\"The solutions of the additional congruences are: \")\n",
    "        while i <= d-1:\n",
    "            j = x + i*(n // d)\n",
    "            print(f\"x_{i} ≡ {j} mod {n}\")\n",
    "            i += 1\n",
    "    else:\n",
    "        # If the GCD is not 1, then a2 and n2 are not coprime and the modular inverse does not exist\n",
    "        print(f\"{a2} and {n2} are not coprime, so the modular inverse does not exist\")\n",
    "        print(f\"Hence, the linear equation {a2}x ≡ {b2} mod {n2} has no solution.\")\n",
    "\n",
    "# Call the function with the coefficients of the linear equation\n",
    "# Format is ax ≡ b mod c, input below is \"(a, b, c)\"\n",
    "solve_composite_modular_linear_equation(18, 34, 59)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "## Congruences using Solve Mod\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
   ],
   "source": [
    "solve_mod([2*x+5==3], 11)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
   ],
   "source": [
    "x = var('x')  # Define the variable\n",
    "equation = 35*x - 25  # Define the equation without the modulo\n",
    "modulus = 45  # Define the modulus\n",
    "solution = solve_mod([equation==0], modulus)  # Solve the equation\n",
    "print(solution)  # Print the solution"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "## Chinese remainder theorem\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
   ],
   "source": [
    "# Define the list of variables in the system of linear equations\n",
    "# Expressed in variables: Solve x ≡ rem1 (mod mod1) and x ≡ rem2 (mod mod2)\n",
    "rem1 = 7  \n",
    "mod1 = 19\n",
    "rem2 = 0  \n",
    "mod2 = 7\n",
    "\n",
    "# Check if mod1 and mod2 are coprime by finding their greatest common divisor\n",
    "if gcd(mod1, mod2) != 1:\n",
    "    print(f\"The moduli {mod1} and {mod2} are not coprime, so the Chinese Remainder Theorem cannot be applied.\")\n",
    "else:\n",
    "    # Use the crt function in SageMath to solve the system of linear equations\n",
    "    x = crt([rem1,rem2],[mod1,mod2])\n",
    "\n",
    "# Print the result\n",
    "print(f\"The solution is x = {x} mod {mod1*mod2}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "## Check the results\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
   ],
   "source": [
    "# Define the list of variables in the system of linear equations)\n",
    "# The equations expressed in variables: Solve x ≡ rem1 (mod mod1) and x ≡ rem2 (mod mod2)\n",
    "rem1 = 7  \n",
    "mod1 = 11\n",
    "rem2 = 19  \n",
    "mod2 = 31\n",
    "\n",
    "# Check if mod1 and mod2 are coprime by finding their greatest common divisor\n",
    "if gcd(mod1, mod2) != 1:\n",
    "    print(f\"The moduli {mod1} and {mod2} are not coprime, so the Chinese Remainder Theorem cannot be applied.\")\n",
    "else:\n",
    "    # Use the crt function in SageMath to solve the system of linear equations\n",
    "    x = crt([rem1,rem2],[mod1,mod2])\n",
    "\n",
    "    # Print the result\n",
    "    print(f\"The solution is x = {x} mod {mod1*mod2}\")\n",
    "\n",
    "    # Check the result by inserting the solution back into the original equations\n",
    "    check1 = x % mod1\n",
    "    check2 = x % mod2\n",
    "\n",
    "    # print the checked results\n",
    "    print(f\"Here are the checked results:\")\n",
    "    print(f\"Check for first equation: {x} mod {mod1} = {check1}, expected {rem1}\")\n",
    "    print(f\"Check for second equation: {x} mod {mod2} = {check2}, expected {rem2}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
   ],
   "source": [
    "# Input the numbers for which you want to find the gcd and coefficients\n",
    "a = 7\n",
    "b = 15\n",
    "\n",
    "# Compute the extended GCD of 7 and 15\n",
    "g, s, t = xgcd(a, b)\n",
    "\n",
    "# Print the results: \n",
    "print(f\"The gcd of {a} and {b} is {g}\")\n",
    "print(f\"Bézout's Coefficients are: {s} and {t}\")\n",
    "\n",
    "# Print Bézout's Identity\n",
    "print(f\"Bézout's Identity is: {s}*{a} + {t}*{b} = {g}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "## Euler totient function"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
   ],
   "source": [
    "# Declare the variables\n",
    "a = 15\n",
    "e = 4041\n",
    "n = 41\n",
    "\n",
    "# Calculate the Euler's totient of n\n",
    "phi_n = euler_phi(n)\n",
    "\n",
    "# Calculate the remainder and quotient of e / phi(n)\n",
    "k = e // phi_n  # quotient\n",
    "r = e % phi_n  # remainder\n",
    "\n",
    "# Print the result in the required format\n",
    "print(f\"Euler's Totient = {phi_n}\")\n",
    "print(f\"e = phi_n * k + r: {e} = {phi_n} * {k} + {r}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
   ],
   "source": [
    "# Declare the variables\n",
    "a = 15\n",
    "e = 4042\n",
    "n = 41\n",
    "\n",
    "# Check if a and n are coprime\n",
    "if gcd(a, n) != 1:\n",
    "    print(f\"{a} and {n} are not coprime, so Euler's theorem may not apply.\")\n",
    "else:\n",
    "    # Calculate φ(n)\n",
    "    phi_n = euler_phi(n)\n",
    "    print(f\"phi({n}) = {phi_n}\")\n",
    "\n",
    "    # Reduce e mod φ(n)\n",
    "    e_prime = e % phi_n\n",
    "    print(f\"{e} mod {phi_n} = {e_prime}\")\n",
    "\n",
    "    # Calculate a^e' (mod n)\n",
    "    result = power_mod(a, e_prime, n)\n",
    "    print(f\"{a}^{e_prime} mod {n} = {result} mod {n}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "# Fermat's Little Theorem\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
   ],
   "source": [
    "# define the variables in the format a mod p\n",
    "a = 8\n",
    "p = 11\n",
    "\n",
    "# check if p is a prime number and a is not divisible by p\n",
    "if is_prime(p) and gcd(a, p) == 1:\n",
    "\n",
    "    # calculate the totient of p\n",
    "    phi_p = euler_phi(p)\n",
    "\n",
    "    # calculate the multiplicative inverse of a mod p\n",
    "    inverse = power_mod(a, phi_p - 1, p)\n",
    "\n",
    "    # print the result\n",
    "    print(f\"The multiplicative inverse of {a} mod {p} is {inverse} mod {p}\")\n",
    "else:\n",
    "    print(f\"Error: p must be a prime number and a must not be divisible by p.\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "# Applications of Euler's Theorem\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
   ],
   "source": [
    "# Define variables\n",
    "a = 11\n",
    "e = 402\n",
    "d = 2 #The number of x last digits you want to find\n",
    "\n",
    "# Calculate n, the number we want to take the modulo with\n",
    "n = 10^d\n",
    "\n",
    "# Check that a and n are coprime\n",
    "if gcd(a, n) != 1:\n",
    "    print(f\"The number {a} and {n} are not coprime, so Euler's Theorem cannot be applied.\")\n",
    "else:\n",
    "    # Compute phi(n)\n",
    "    phi_n = euler_phi(n)\n",
    "\n",
    "    # Compute e % phi_n, since a^(phi(n)) ≡ 1 (mod n)\n",
    "    r = e % phi_n\n",
    "\n",
    "    # Compute a^r (mod n)\n",
    "    result = power_mod(a, r, n)\n",
    "\n",
    "    # Print the result\n",
    "    print(f\"The last {d} digits of {a}^{e} are {str(result).zfill(d)}.\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
   ],
   "source": [
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "argv": [
    "sage-10.0",
    "--python",
    "-m",
    "sage.repl.ipython_kernel",
    "--matplotlib=inline",
    "-f",
    "{connection_file}"
   ],
   "display_name": "SageMath 10.0",
   "env": {
   },
   "language": "sagemath",
   "metadata": {
    "cocalc": {
     "description": "Open-source mathematical software system",
     "priority": 1,
     "url": "https://www.sagemath.org/"
    }
   },
   "name": "sage-10.0",
   "resource_dir": "/ext/jupyter/kernels/sage-10.0"
  },
  "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.11.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}