Debian Codegraph @

texmf-dist/doc/lualatex/luagcd/luagcd.tex

raw
1 \documentclass{article}
2 \usepackage{listings,color,booktabs,longtable,array,hyperref,multicol,framed}
3 \usepackage[ left=1in, right=1in]{geometry}
4 \hypersetup{colorlinks,urlcolor=blue}
5 \lstset{frame=none,
6 language=[LaTeX]{TeX},
7 aboveskip=3mm,
8 belowskip=3mm,
9 showstringspaces=false,
10 columns=flexible,
11 basicstyle={\ttfamily},
12 numbers=none,
13 numberstyle=\tiny\color{gray},
14 stringstyle=\color{mauve},
15 breaklines=true,
16 breakatwhitespace=true,
17 tabsize=1
18 }
19 \usepackage[backend=bibtex]{biblatex}
20 \begin{document}
21 \title{The luagcd Package in LaTeX}
22 \author{Chetan Shirore\thanks{Email id: [email protected]} \space and Ajit Kumar}
23 \maketitle
24 \section{Introduction}\label{section:introduction}
25 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.
26
27 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.
28 \[\gcd(\gcd(a,b),c)=\gcd(a,b,c)\]
29 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.
30 \[\gcd\{a,b\}=\gcd\{|a|,b\}=\gcd\{a,|b|\}=\gcd\{|a|,|b|\} \]
31
32 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
33 \[ax+by=d \iff (-a)(-x)+by = d \iff ax+(-b)(-y) = d \iff (-a)(-x)+(-b)(-y) = d \]
34
35 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.
36
37 \section{Installation and License}
38
39 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.
40
41 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.
42
43 \section{Commands in the luagcd package}
44 Table \ref{tbl:luagcd} lists operations in the \verb|luagcd| package.
45 \begin{longtable}{m{4cm}m{5cm}m{4cm}}
46 \toprule
47 \multicolumn{1}{l}{\textcolor{blue}{Command}} & \multicolumn{1}{l}{\textcolor{blue}{Syntax}} & \multicolumn{1}{l}{\textcolor{blue}{Description}} \\
48 \toprule
49 \begin{lstlisting}
50 \luagcd
51 \end{lstlisting} &
52 \begin{lstlisting}
53 \luagcd{x_1, x_2, ..., x_n}
54 \end{lstlisting} & Gives gcd of integers \(x_1,x_2,x_3,\ldots,x_n\).\\
55 \midrule
56 \begin{lstlisting}
57 \luagcdwithsteps
58 \end{lstlisting} &
59 \begin{lstlisting}
60 \luagcdwithsteps{a}{b}
61 \end{lstlisting} & Gives the gcd of two integers, \(a\) and \(b\), in a step-by-step manner by repeated application of the Euclidean algorithm. \\
62 \midrule
63 \begin{lstlisting}
64 \luagcdlincomb
65 \end{lstlisting} &
66 \begin{lstlisting}
67 \luagcdlincomb{a}{b}
68 \end{lstlisting} & Gives the gcd of two integers \(a\) and \(b\) and expresses it as a linear combination of two integers \(a\) and \(b\). \\
69 \midrule
70 \begin{lstlisting}
71 \luagcdlincombwithsteps
72 \end{lstlisting} &
73 \begin{lstlisting}
74 \luagcdlincombwithsteps{a}{b}
75 \end{lstlisting} & Expresses the gcd of two integers \(a\) and \(b\) as their linear combination in a step-by-step manner. \\ \\
76 \bottomrule
77
78 \caption{Operations in the luagcd package}
79 \label{tbl:luagcd}
80 \end{longtable}
81
82
83
84 \section{Examples and usage}
85 The command \verb|\luagcd{20,30,60,70}| outputs to \fbox{10}. \\
86 The command \verb|\luagcdwithsteps{-20}{-6008}| outputs the following.\\
87 \begin{framed}
88 \noindent Step 1: Apply the division algorithm to 6008 and 20.\\
89 $6008 = 20(300) + 8$\\
90 Step 2: Apply the division algorithm to 20 and 8.\\
91 $20 = 8(2) + 4$\\
92 Step 3: Apply the division algorithm to 8 and 4.\\
93 $8 = 4(2) + 0$ \\
94 The gcd of -20 and -6008 is the last non-zero remainder and it is 4.
95 \end{framed}
96
97 The command \verb|\luagcdwithsteps{-20}{-6008}| outputs the following LaTeX code.
98 \begin{lstlisting}
99 Step 1: Apply the division algorithm to 6008 and 20.\\
100 $6008 = 20(300) + 8$\\
101 Step 2: Apply the division algorithm to 20 and 8.\\
102 $20 = 8(2) + 4$\\
103 Step 3: Apply the division algorithm to 8 and 4.\\
104 $8 = 4(2) + 0$ \\
105 The gcd of -20 and -6008 is the last non-zero remainder and it is 4.
106 \end{lstlisting}
107
108 The command \verb|\luagcdlincomb{10011}{210}| outputs the following.
109
110 \begin{framed} \noindent The gcd of 10011 and 210 is 3 and the equation $-10011x + 210y = 3$
111 and has a solution $(x,y) = (3,-143)$.\end{framed}
112
113 The command \verb|\luagcdlincombwithsteps{-10011}{210}| outputs the following.
114
115 \begin{framed}
116 \noindent Step 1:10011 is written as a linear combination of 10011 and 210.\\
117 $10011 = (1)(10011) + (0)(210)$\\
118 Step 2:210 is written as a linear combination of 10011 and 210.\\
119 $210 = (0)(10011) + (1)(210)$\\
120 Step 3: The equation in Step 2 is multiplied by 47 and
121 subtracted from the equation in Step 1.\\
122 $141 = (1)(10011) + (-47)(210)$\\
123 Step 4: The equation in Step 3 is multiplied by 1 and
124 subtracted from the equation in Step 2.\\
125 $69 = (-1)(10011) + (48)(210)$\\
126 Step 5: The equation in Step 4 is multiplied by 2 and
127 subtracted from the equation in Step 3.\\
128 $3 = (3)(10011) + (-143)(210)$\\
129 The gcd of -10011 and 210 is 3 and the equation $-10011x + 210y = 3$
130 and has a solution $(x,y) = (-3,-143)$.
131 \end{framed}
132
133 The command \verb|\luagcdlincombwithsteps{-10011}{210}| outputs the following LaTeX code.
134 \begin{lstlisting}
135 Step 1:10011 is written as a linear combination of 10011 and 210.\\
136 $10011 = (1)(10011) + (0)(210)$\\
137 Step 2:210 is written as a linear combination of 10011 and 210.\\
138 $210 = (0)(10011) + (1)(210)$\\
139 Step 3: The equation in Step 2 is multiplied by 47 and
140 subtracted from the equation in Step 1.\\
141 $141 = (1)(10011) + (-47)(210)$\\
142 Step 4: The equation in Step 3 is multiplied by 1 and
143 subtracted from the equation in Step 2.\\
144 $69 = (-1)(10011) + (48)(210)$\\
145 Step 5: The equation in Step 4 is multiplied by 2 and
146 subtracted from the equation in Step 3.\\
147 $3 = (3)(10011) + (-143)(210)$\\
148 The gcd of -10011 and 210 is 3 and the equation $-10011x + 210y = 3$
149 and has a solution $(x,y) = (-3,-143)$.
150 \end{lstlisting}
151
152
153
154 \printbibliography
155 \end{document}