{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Lucas Polynomials and Proofs of Quadratic Reciprocity law\n",
    "Yasuaki Honda at gmail dot com\n",
    "\n",
    "https://mattbaker.blog/2020/06/02/quadratic-reciprocity-via-lucas-polynomials/"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "\\[\\tag{${\\it \\%o}_{1}$}{\\it LP}_{0}(x):=2\\]"
      ],
      "text/plain": [
       "(%o1)                             LP (x) := 2\n",
       "                                    0"
      ],
      "text/x-maxima": [
       "LP[0](x):=2"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "LP[0](x):=2;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "\\[\\tag{${\\it \\%o}_{2}$}{\\it LP}_{1}(x):=x\\]"
      ],
      "text/plain": [
       "(%o2)                             LP (x) := x\n",
       "                                    1"
      ],
      "text/x-maxima": [
       "LP[1](x):=x"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "LP[1](x):=x;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "\\[\\tag{${\\it \\%o}_{3}$}{\\it LP}_{n}(x):=x\\,{\\it LP}_{n-1}(x)+{\\it LP}_{n-2}(x)\\]"
      ],
      "text/plain": [
       "(%o3)                 LP (x) := x LP     (x) + LP     (x)\n",
       "                        n           n - 1        n - 2"
      ],
      "text/x-maxima": [
       "LP[n](x):=x*LP[n-1](x)+LP[n-2](x)"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "LP[n](x):=x*LP[n-1](x)+LP[n-2](x);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "\\({\\it LP}_{1}(x)=x\\)"
      ],
      "text/plain": [
       "inline-value"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/latex": [
       "\\({\\it LP}_{3}(x)=x^3+3\\,x\\)"
      ],
      "text/plain": [
       "inline-value"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/latex": [
       "\\({\\it LP}_{5}(x)=x^5+5\\,x^3+5\\,x\\)"
      ],
      "text/plain": [
       "inline-value"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/latex": [
       "\\({\\it LP}_{7}(x)=x^7+7\\,x^5+14\\,x^3+7\\,x\\)"
      ],
      "text/plain": [
       "inline-value"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/latex": [
       "\\({\\it LP}_{9}(x)=x^9+9\\,x^7+27\\,x^5+30\\,x^3+9\\,x\\)"
      ],
      "text/plain": [
       "inline-value"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/latex": [
       "\\({\\it LP}_{11}(x)=x^{11}+11\\,x^9+44\\,x^7+77\\,x^5+55\\,x^3+11\\,x\\)"
      ],
      "text/plain": [
       "inline-value"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/latex": [
       "\\[\\tag{${\\it \\%o}_{4}$}\\mathbf{done}\\]"
      ],
      "text/plain": [
       "(%o4)                                done"
      ],
      "text/x-maxima": [
       "done"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "for n:1 thru 11 step 2 do print(expand('LP[n](x)=LP[n](x)));"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "\\[\\tag{${\\it \\%o}_{5}$}H_{n}(x):=\\mathbf{if}\\;{\\it oddp}\\left(n\\right)\\;\\mathbf{then}\\;{\\it ratsubst}\\left(x , x^2 , {\\it expand}\\left(\\frac{{\\it LP}_{n}(x)}{x}\\right)\\right)\\;\\mathbf{else}\\;{\\it ratsubst}\\left(x , x^2 , {\\it expand}\\left({\\it LP}_{n}(x)\\right)\\right)\\]"
      ],
      "text/plain": [
       "                                                      LP (x)\n",
       "                                            2           n\n",
       "(%o5) H (x) := if oddp(n) then ratsubst(x, x , expand(------))\n",
       "       n                                                x\n",
       "                                                             2\n",
       "                                           else ratsubst(x, x , expand(LP (x)))\n",
       "                                                                         n"
      ],
      "text/x-maxima": [
       "H[n](x):=if oddp(n) then ratsubst(x,x^2,expand(LP[n](x)/x))\n",
       "      else ratsubst(x,x^2,expand(LP[n](x)))"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "H[n](x):=if oddp(n) then ratsubst(x,x^2,expand(LP[n](x)/x)) else ratsubst(x,x^2,expand(LP[n](x)));"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "\\(H_{1}(x)=1\\)"
      ],
      "text/plain": [
       "inline-value"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/latex": [
       "\\(H_{3}(x)=x+3\\)"
      ],
      "text/plain": [
       "inline-value"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/latex": [
       "\\(H_{5}(x)=x^2+5\\,x+5\\)"
      ],
      "text/plain": [
       "inline-value"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/latex": [
       "\\(H_{7}(x)=x^3+7\\,x^2+14\\,x+7\\)"
      ],
      "text/plain": [
       "inline-value"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/latex": [
       "\\(H_{9}(x)=x^4+9\\,x^3+27\\,x^2+30\\,x+9\\)"
      ],
      "text/plain": [
       "inline-value"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/latex": [
       "\\(H_{11}(x)=x^5+11\\,x^4+44\\,x^3+77\\,x^2+55\\,x+11\\)"
      ],
      "text/plain": [
       "inline-value"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/latex": [
       "\\[\\tag{${\\it \\%o}_{6}$}\\mathbf{done}\\]"
      ],
      "text/plain": [
       "(%o6)                                done"
      ],
      "text/x-maxima": [
       "done"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "for n:1 thru 11 step 2 do print('H[n](x)=expand(H[n](x)));"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "\\[\\tag{${\\it \\%o}_{7}$}\\left[ 3 , 8 , 9 \\right] \\]"
      ],
      "text/plain": [
       "(%o7)                              [3, 8, 9]"
      ],
      "text/x-maxima": [
       "[3,8,9]"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[hipow(H[7](x),x),hipow(H[17](x),x),hipow(H[19](x),x)];"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "\\[\\tag{${\\it \\%o}_{8}$}\\left[ 7 , 17 , 19 \\right] \\]"
      ],
      "text/plain": [
       "(%o8)                             [7, 17, 19]"
      ],
      "text/x-maxima": [
       "[7,17,19]"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[H[7](0),H[17](0),H[19](0)];"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "\\[\\tag{${\\it \\%o}_{9}$}\\left[ x^3 , x^8 , x^9 \\right] \\]"
      ],
      "text/plain": [
       "                                   3   8   9\n",
       "(%o9)                            [x , x , x ]"
      ],
      "text/x-maxima": [
       "[x^3,x^8,x^9]"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[polymod(H[7](x),7),polymod(H[17](x),17),polymod(H[19](x),19)];"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "\\[\\tag{${\\it \\%o}_{10}$}\\left[ 1 , 1 , -1 , 1 \\right] \\]"
      ],
      "text/plain": [
       "(%o10)                          [1, 1, - 1, 1]"
      ],
      "text/x-maxima": [
       "[1,1,-1,1]"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[resultant(H[7](x),H[11](x),x),resultant(H[19](x),H[11](x),x),resultant(H[19](x),H[3](x),x),resultant(H[21](x),H[5](x),x)];"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "\\[\\tag{${\\it \\%o}_{11}$}\\left[ 1 , 1 , -1 , 1 \\right] \\]"
      ],
      "text/plain": [
       "(%o11)                          [1, 1, - 1, 1]"
      ],
      "text/x-maxima": [
       "[1,1,-1,1]"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[jacobi(11,7),jacobi(11,19),jacobi(3,19),jacobi(5,21)];"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "\\[\\tag{${\\it \\%o}_{12}$}{\\it resultant}\\left(H_{p}(x) , H_{q}(x) , x\\right)={\\it resultant}\\left(x^{\\frac{p-1}{2}} , H_{q}(x)\\right) \\rm{mod} p\\]"
      ],
      "text/plain": [
       "                                                     p - 1\n",
       "                                                     -----\n",
       "                                                       2\n",
       "(%o12)   resultant(H (x), H (x), x) = mod(resultant(x     , H (x)), p)\n",
       "                    p      q                                 q"
      ],
      "text/x-maxima": [
       "'resultant('H[p](x),'H[q](x),x) = mod('resultant(x^((p-1)/2),'H[q](x)),p)"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "'resultant('H[p](x),'H[q](x),x)=mod('resultant(x^((p-1)/2),'H[q](x)),p);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "\\[\\tag{${\\it \\%o}_{13}$}{\\it resultant}\\left(x^{n} , f\\left(x\\right)\\right)=f\\left(0\\right)^{n}\\]"
      ],
      "text/plain": [
       "                                     n           n\n",
       "(%o13)                    resultant(x , f(x)) = f (0)"
      ],
      "text/x-maxima": [
       "'resultant(x^n,'f(x)) = f(0)^n"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "'resultant(x^n,'f(x))=f(0)^n;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "\\[\\tag{${\\it \\%o}_{14}$}a^6\\]"
      ],
      "text/plain": [
       "                                       6\n",
       "(%o14)                                a"
      ],
      "text/x-maxima": [
       "a^6"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "resultant(x^6,x^2+3*x+a,x);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "\\[\\tag{${\\it \\%o}_{15}$}{\\it resultant}\\left(x^{\\frac{p-1}{2}} , H_{q}(x) , x\\right)=H_{q}(0)^{\\frac{p-1}{2}}\\]"
      ],
      "text/plain": [
       "                              p - 1                   p - 1\n",
       "                              -----                   -----\n",
       "                                2                       2\n",
       "(%o15)             resultant(x     , H (x), x) = H (0)\n",
       "                                      q           q"
      ],
      "text/x-maxima": [
       "'resultant(x^((p-1)/2),'H[q](x),x) = 'H[q](0)^((p-1)/2)"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "'resultant(x^((p-1)/2),'H[q](x),x)='H[q](0)^((p-1)/2);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "\\[\\tag{${\\it \\%o}_{16}$}H_{q}(0)^{\\frac{p-1}{2}}=q^{\\frac{p-1}{2}}\\]"
      ],
      "text/plain": [
       "                                   p - 1    p - 1\n",
       "                                   -----    -----\n",
       "                                     2        2\n",
       "(%o16)                        H (0)      = q\n",
       "                               q"
      ],
      "text/x-maxima": [
       "'H[q](0)^((p-1)/2) = q^((p-1)/2)"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "'H[q](0)^((p-1)/2)=q^((p-1)/2);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Maxima",
   "language": "maxima",
   "name": "maxima"
  },
  "language_info": {
   "codemirror_mode": "maxima",
   "file_extension": ".mac",
   "mimetype": "text/x-maxima",
   "name": "maxima",
   "pygments_lexer": "maxima",
   "version": "5.42.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}