% luagcd package
% version 1.1
% Licensed under LaTeX Project Public License v1.3c or later. The complete license text is available at http://www.latex-project.org/lppl.txt.
% Authors: Chetan Shirore and Ajit Kumar

\ProvidesPackage{luagcd}[1.1]
\RequirePackage{luacode}
\begin{luacode*}
function findgcd2(a,b) -- function to find gcd of 2 numbers.
   a = math.abs(a)
   b = math.abs(b)
   if b ~= 0 then
      return findgcd2(b, a % b)
   else
      return a
   end
end

function findgcd(...) -- function to find gcd of 2 or more numbers.
   local tbl = table.pack(...)
   if #(tbl) > 2 then
      local rem = table.remove(tbl,1)
      return findgcd (rem, findgcd( table.unpack(tbl) ) )
   else
      u,v = table.unpack(tbl)
      return math.floor(findgcd2(u,v))
   end
end

function inputcheck ( ... ) -- validating input.
   local tbl = table.pack(...)
   for _, v in ipairs(tbl) do
      if type(v) ~= 'number' then
         error('Only numbers are expected.')
         return
      elseif v~= math.floor(v) then
         error('Error: Only integers are expected.')
         return
      end
   end
end
- function to find gcd with input validatiion.
function luagcd(...) -
   inputcheck(...)
   return findgcd(...)

end
-- function to find gcd of 2 numbers with steps.
function stepbystepgcd(a,b,sep) 
   if type(a) ~= 'number' or type(b) ~= 'number' then
      error('Only numbers are expected.')
      return
   elseif a~= math.floor(a) or b~= math.floor(b) then
      error('Error: Only integers are expected.')
      return
   end
   local val1,val2 = a,b
   a,b = math.max(math.abs(a),math.abs(b)),
   math.min(math.abs(a),math.abs(b))
   p,q = math.max(math.abs(a),math.abs(b)),
   math.min(math.abs(a),math.abs(b))
   if b==0 then 
return 
	("The gcd of " .. val1 .." and " .. val2 ..  " is " .. a .. '.' )
end
   local tbl ={}
   local k = 0
   local sep = sep or 'Step '
   local stepcnt = 0
   while b~=0 do
      x=a
      y=b
      t = b
      b = a % b
      a = t
      k=k+1
      stepcnt = stepcnt + 1
      if b ~=0 then
         d = x // y
         tbl[k] = sep .. stepcnt ..
			": Apply the division algorithm to " .. x .." and " .. y .."."
         k=k+1
         tbl[k] = "$".. x.." = ".. t .."("
         .. d ..") + ".. b .."$"
      else
         tbl[k] = sep .. stepcnt ..
			": Apply the division algorithm to " .. x .." and " .. y .."."
         k=k+1
         tbl[k] ="$".. x.." = "..t.."("
         .. (x // y)..") +  ".. b .."$"
      end
   end
   local str = table.concat(tbl,"\\\\")
   if stepcnt==1 then
      return str  .. " \\\\" .. "The gcd of ".. val1 .." and " .. val2..
      " is " ..t.. "."

   else
      return str  .. " \\\\" .. "The gcd of ".. val1 .." and " .. val2 ..
      " is the last non-zero remainder and it is " ..t.. "."
   end
end
-- function to express gcd of 2 numbers as an integer linear combination.
function lincombgcd (a,b)
   local val1,val2 = a,b
   if type(a) ~= 'number' or type(b) ~= 'number' then
      error('Only numbers are expected.')
      return
   elseif a~= math.floor(a) or b~= math.floor(b) then
      error('Error: Only integers are expected.')
      return
   end

   local x,y=math.max(math.abs(a),math.abs(b)),
   math.min(math.abs(a),math.abs(b))

   local a,b=math.max(math.abs(a),math.abs(b)),
   math.min(math.abs(a),math.abs(b))

   if x == 0 and y == 0 then
      return 
("The gcd of $0$ and $0$  is clearly a linear combination of $0$ and $0$.")
   elseif y == 0 then
      return ("The gcd of " .. val1 .." and " .. val2 ..
      " is $" .. x .. "$" .. " and  $" ..  x .." = 1 "
      .."(".. x .. ")".." + 0(0)$.")
   end

   if x % y == 0 then
      return ("The gcd of " .. val1 .." and " .. val2 ..
      " is $" .. y .. "$" .. " and  one number is a multiple of other.")
   end

   local e_1 = 1
   local e_2 = 0
   local e_3 = 0
   local f_1 = 0
   local f_2 = 1
   local f_3 = 0

   while (a > 0 and b > 0) do
      if (a > b) then
         q = a // b
         r = a % b

         if r > 0 then
            e_3 = e_1 - (q * e_2)
            e_1 = e_2
            e_2 = e_3
            f_3 = f_1 - (q * f_2)
            f_1 = f_2
            f_2 = f_3
            gcd = r
         end
         a = a % b
      else do
         q = b // a
         r = b % a
         if r > 0 then
            e_3 = e_1 - (q * e_2)
            e_1 = e_2
            e_2 = e_3
            f_3 = f_1 - (q * f_2)
            f_1 = f_2
            f_2 = f_3
            gcd = r
         end
         b = b % a
      end
   end
end

if math.abs(val1) >= math.abs(val2) then
   coeff1,coeff2 = val1, val2
   if val1 < 0 and val2 < 0 then
      e_3,f_3 = -e_3,-f_3
   elseif val1 > 0 and val2 < 0 then
      f_3 = -f_3
   elseif val1 < 0 and val2 > 0 then
      e_3 = -e_3
   end
else
   coeff1,coeff2 = val2,val1
   if val1 < 0 and val2 < 0 then
      e_3,f_3 = -e_3,-f_3
   elseif val1 > 0 and val2 < 0 then
      e_3 = -e_3
   elseif val1 < 0 and val2 > 0 then
      f_3 = -f_3
   end
end

if coeff2 <0 then
   op = ""
else
   op = " + "
end

return ("The gcd of " .. val1 .." and " .. val2 .. " is " .. gcd ..
" and the equation $" .. coeff1 .."x" .. op ..  coeff2 .."y = "
..gcd ..  "$ has a solution $(x,y) =  (" .. e_3 .. "," .. f_3 ..")$.")
end
-- function to express gcd of 2 numbers as an integer linear combination with steps.
function lincombgcdstepbystep (a,b)
local val1,val2 = a,b
if type(a) ~= 'number' or type(b) ~= 'number' then
  error('Only numbers are expected.') 
  return
  elseif a~= math.floor(a) or b~= math.floor(b) then
   error('Error: Only integers are expected.')
   return
  end

local x,y=math.max(math.abs(a),math.abs(b)),
math.min(math.abs(a),math.abs(b))

local a,b=math.max(math.abs(a),math.abs(b)),
math.min(math.abs(a),math.abs(b))

if x == 0 and y == 0 then
 return 
("The gcd of $0$ and $0$  is clearly a linear combination of $0$ and $0$.")
elseif y == 0 then
  return ("The gcd of " .. val1 .." and " .. val2 ..
   " is $" .. x .. "$" .. " and  $" ..  x .." = 1 " 
    .."(".. x .. ")".." + 0(0)$.")
end 

if x % y == 0 then 
 return ("The gcd of " .. val1 .." and " .. val2 ..
   " is $" .. y .. "$" .. " and  one number is a multiple of other.")
end

local e_1 = 1
local e_2 = 0
local e_3 = 0
local f_1 = 0
local f_2 = 1
local f_3 = 0
local sep = "Step "
local stcnt = 2
local cnt = 4

local tbl ={}
tbl[1] = "Step 1:" .. x .. " is written as a linear combination of "
.. x .. " and " .. y .. "."
tbl[2] = "$".. x .. " = (" .. "1" .. ")" .. "(" .. x .. ") + " 
.. "(" .. "0" .. ")" .. "(" .. y .. ")$" 

tbl[3] = "Step 2:" .. y .. " is written as a linear combination of "
.. x .. " and " .. y .. "."
tbl[4] = "$".. y .. " = (" .. "0" .. ")".. "(" .. x .. ") + "
.. "(" .. "1" .. ")" .. "(" .. y .. ")$"



while (a > 0 and b > 0) do
    if (a > b) then
        q = a // b
        r = a % b

        if r > 0 then
            e_3 = e_1 - (q * e_2)
            e_1 = e_2
            e_2 = e_3
            f_3 = f_1 - (q * f_2)
            f_1 = f_2
            f_2 = f_3
          
          cnt = cnt + 1
          stcnt = stcnt + 1
           
          tbl[cnt] = sep..stcnt ..": ".."The equation in Step "  
			..(stcnt-1).. " is multiplied  by " .. q .. 
			" and subtracted from  the equation in Step " 
			..(stcnt-2) .. "."
          cnt = cnt +1
          
          tbl[cnt] = "$".. r .. " = (" .. e_3 .. ")" .. "(" .. x .. ") + " 
           .. "(" .. f_3 .. ")" .. "(" .. y .. ")$"
           gcd = r
        end
        a = a % b 
     else do
       q = b // a
       r = b % a
        if r > 0 then
            e_3 = e_1 - (q * e_2)
            e_1 = e_2
            e_2 = e_3
            f_3 = f_1 - (q * f_2)
            f_1 = f_2
            f_2 = f_3
          cnt = cnt +1
          stcnt = stcnt + 1
          tbl[cnt] = sep..( stcnt) ..": ".."The equation in Step "  
			..(stcnt-1).. " is multiplied  by " .. q .. 
			" and subtracted from  the equation in Step " 
			..(stcnt-2) .. "."
          cnt = cnt +1
          tbl[cnt] = "$" .. r .. " = (" .. e_3 .. ")" .. "(" .. x .. ") + "
          .. "(" .. f_3 .. ")" .. "(" .. y .. ")$"
          gcd = r
       end
        b = b % a
    end
end
end

if math.abs(val1) >= math.abs(val2) then
coeff1,coeff2 = val1, val2
  if val1 < 0 and val2 < 0 then
  e_3,f_3 = -e_3,-f_3
  elseif val1 > 0 and val2 < 0 then
  f_3 = -f_3
  elseif val1 < 0 and val2 > 0 then
  e_3 = -e_3
  end
else
coeff1,coeff2 = val2,val1
  if val1 < 0 and val2 < 0 then
  e_3,f_3 = -e_3,-f_3
  elseif val1 > 0 and val2 < 0 then
  e_3 = -e_3
  elseif val1 < 0 and val2 > 0 then
  f_3 = -f_3
  end
end

if coeff2 <0 then
  op = ""
else
  op = " + "
end

tbl[cnt+1] = "The gcd of " .. val1 .." and " .. val2 .. " is " .. gcd ..
" and the equation $" .. coeff1 .."x" .. op ..  coeff2 .."y = "
..gcd ..  "$  has a solution $(x,y) =  (" .. e_3 .. "," .. f_3 ..")$."
return table.concat(tbl,"\\\\")

end

\end{luacode*}

\newcommand\luagcd[1]{\directlua{tex.sprint(luagcd(#1))}}

\newcommand\luagcdwithsteps[2]
{\directlua{tex.sprint(stepbystepgcd(#1,#2))}}

\newcommand\luagcdlincomb[2]
{\directlua{tex.sprint(lincombgcd(#1,#2))}}

\newcommand\luagcdlincombwithsteps[2]
{\directlua{tex.sprint(lincombgcdstepbystep(#1,#2))}}

\endinput