1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
|
\documentclass{article}
\usepackage{listings,color,booktabs,longtable,array,hyperref,multicol,framed}
\usepackage[ left=1in, right=1in]{geometry}
\hypersetup{colorlinks,urlcolor=blue}
\lstset{frame=none,
language=[LaTeX]{TeX},
aboveskip=3mm,
belowskip=3mm,
showstringspaces=false,
columns=flexible,
basicstyle={\ttfamily},
numbers=none,
numberstyle=\tiny\color{gray},
stringstyle=\color{mauve},
breaklines=true,
breakatwhitespace=true,
tabsize=1
}
\usepackage[backend=bibtex]{biblatex}
\begin{document}
\title{The luagcd Package in LaTeX}
\author{Chetan Shirore and Dr. Ajit Kumar}
\maketitle
\section{Introduction}\label{section:introduction}
Using Lua, the \verb|luagcd| package is developed to find the \textbf{greatest common divisor (gcd)} of integers in LaTeX. It provides an easy way to find gcd of two or more integers inside LaTeX documents. The package provides commands to obtain step-by-step computation of gcd of two integers by using Euclidean algorithm. In addition, the package has the command to express gcd of two integers as a linear combination. The Bezout’s Identity can be verified for any two integers using commands in the package. No particular environment is required for the use of commands in the package. It is written in Lua, and the TeX file has to be compiled with the LuaLaTeX engine.
In order to find the gcd of two integers, \(a\) and \(b\), the package uses a repeated division algorithm. This technique is basically based on the fact \(\gcd(a,b)=\gcd(a,b-\lambda a)\), where \(\lambda\) is an integer. This technique to find the gcd of integers is called as Euclidean algorithm. For finding gcd of more than two numbers, the associativity of the gcd operation is used.
\[\gcd(\gcd(a,b),c)=\gcd(a,b,c)\]
This associativity of the gcd operation allows the recursion of functions to find the gcd of more than two integers. The recursion technique (where the function calls itself) in Lua is effectively used in the package for finding the gcd of integers. The package also makes use of the following result.
\[\gcd\{a,b\}=\gcd\{|a|,b\}=\gcd\{a,|b|\}=\gcd\{|a|,|b|\} \]
Algorithms in the package convert non-zero integers to positive integers, and then the Euclidean algorithm is used to find their gcd. If the gcd of \(a\) and \(b\) is \(d\) and it is expressed as a linear combination \(ax+by=d\), then we have
\[ax+by=d \iff (-a)(-x)+by = d \iff ax+(-b)(-y) = d \iff (-a)(-x)+(-b)(-y) = d \]
So in order to find a solution of \((-a)(-x)+by = d\), \( ax+(-b)(-y) = d\) or \((-a)(-x)+(-b)(-y) = d\) it suffices to find a solution of \(ax+by=d \). This fact is used in an algorithm of the package to express the gcd of two integers as their linear combination.
\section{Installation and License}
The installation of \verb|luagcd| package is similar to plain latex package, where the \texttt{.sty} file is in LaTeX directory of texmf tree. The package can be included with \verb|\usepackage{luagcd}| command in the preamble of the LaTeX document. The TeX file is to be compiled using the LuaLaTeX engine.
The \verb|luagcd| package is released under the LaTeX Project Public License v1.3c or later. The complete license text is available at \url{http://www.latex-project.org/lppl.txt}. It is developed in Lua. Lua is available as a certified open-source software. Its license is simple and liberal, which is compatible with GPL.
\section{Commands in the luagcd package}
Table \ref{tbl:luagcd} lists operations in the \verb|luagcd| package.
\begin{longtable}{m{4cm}m{5cm}m{4cm}}
\toprule
\multicolumn{1}{l}{\textcolor{blue}{Command}} & \multicolumn{1}{l}{\textcolor{blue}{Syntax}} & \multicolumn{1}{l}{\textcolor{blue}{Description}} \\
\toprule
\begin{lstlisting}
\luagcd
\end{lstlisting} &
\begin{lstlisting}
\luagcd{x_1, x_2, ..., x_n}
\end{lstlisting} & Gives gcd of integers \(x_1,x_2,x_3,\ldots,x_n\).\\
\midrule
\begin{lstlisting}
\luagcdwithsteps
\end{lstlisting} &
\begin{lstlisting}
\luagcdwithsteps{a}{b}
\end{lstlisting} & Gives the gcd of two integers, \(a\) and \(b\), in a step-by-step manner by repeated application of the Euclidean algorithm. \\
\midrule
\begin{lstlisting}
\luagcdlincomb
\end{lstlisting} &
\begin{lstlisting}
\luagcdlincomb{a}{b}
\end{lstlisting} & Gives the gcd of two integers \(a\) and \(b\) and expresses it as a linear combination of two integers \(a\) and \(b\). \\
\midrule
\begin{lstlisting}
\luagcdlincombwithsteps
\end{lstlisting} &
\begin{lstlisting}
\luagcdlincombwithsteps{a}{b}
\end{lstlisting} & Expresses the gcd of two integers \(a\) and \(b\) as their linear combination in a step-by-step manner. \\ \\
\bottomrule
\caption{Operations in the luagcd package}
\label{tbl:luagcd}
\end{longtable}
\section{Examples and usage}
The command \verb|\luagcd{20,30,60,70}| outputs to \fbox{10}. \\
The command \verb|\luagcdwithsteps{-20}{-6008}| outputs the following.\\
\begin{framed}
\noindent Step 1: Apply the division algorithm to 6008 and 20.\\
$6008 = 20(300) + 8$\\
Step 2: Apply the division algorithm to 20 and 8.\\
$20 = 8(2) + 4$\\
Step 3: Apply the division algorithm to 8 and 4.\\
$8 = 4(2) + 0$ \\
The gcd of -20 and -6008 is the last non-zero remainder and it is 4.
\end{framed}
The command \verb|\luagcdwithsteps{-20}{-6008}| outputs the following LaTeX code.
\begin{lstlisting}
Step 1: Apply the division algorithm to 6008 and 20.\\
$6008 = 20(300) + 8$\\
Step 2: Apply the division algorithm to 20 and 8.\\
$20 = 8(2) + 4$\\
Step 3: Apply the division algorithm to 8 and 4.\\
$8 = 4(2) + 0$ \\
The gcd of -20 and -6008 is the last non-zero remainder and it is 4.
\end{lstlisting}
The command \verb|\luagcdlincomb{10011}{210}| outputs the following.
\begin{framed} \noindent The gcd of 10011 and 210 is 3 and the equation $-10011x + 210y = 3$
and has a solution $(x,y) = (3,-143)$.\end{framed}
The command \verb|\luagcdlincombwithsteps{-10011}{210}| outputs the following.
\begin{framed}
\noindent Step 1:10011 is written as a linear combination of 10011 and 210.\\
$10011 = (1)(10011) + (0)(210)$\\
Step 2:210 is written as a linear combination of 10011 and 210.\\
$210 = (0)(10011) + (1)(210)$\\
Step 3: The equation in Step 2 is multiplied by 47 and
subtracted from the equation in Step 1.\\
$141 = (1)(10011) + (-47)(210)$\\
Step 4: The equation in Step 3 is multiplied by 1 and
subtracted from the equation in Step 2.\\
$69 = (-1)(10011) + (48)(210)$\\
Step 5: The equation in Step 4 is multiplied by 2 and
subtracted from the equation in Step 3.\\
$3 = (3)(10011) + (-143)(210)$\\
The gcd of -10011 and 210 is 3 and the equation $-10011x + 210y = 3$
and has a solution $(x,y) = (-3,-143)$.
\end{framed}
The command \verb|\luagcdlincombwithsteps{-10011}{210}| outputs the following LaTeX code.
\begin{lstlisting}
Step 1:10011 is written as a linear combination of 10011 and 210.\\
$10011 = (1)(10011) + (0)(210)$\\
Step 2:210 is written as a linear combination of 10011 and 210.\\
$210 = (0)(10011) + (1)(210)$\\
Step 3: The equation in Step 2 is multiplied by 47 and
subtracted from the equation in Step 1.\\
$141 = (1)(10011) + (-47)(210)$\\
Step 4: The equation in Step 3 is multiplied by 1 and
subtracted from the equation in Step 2.\\
$69 = (-1)(10011) + (48)(210)$\\
Step 5: The equation in Step 4 is multiplied by 2 and
subtracted from the equation in Step 3.\\
$3 = (3)(10011) + (-143)(210)$\\
The gcd of -10011 and 210 is 3 and the equation $-10011x + 210y = 3$
and has a solution $(x,y) = (-3,-143)$.
\end{lstlisting}
\printbibliography
\end{document}
|
