% 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