GCDSteps - Maple Help

Student[Basics]

 GCDSteps
 generate steps for calculating the Greatest Common Divisor (Greatest Common Factor)

 Calling Sequence GCDSteps( expr ) GCDSteps( expr, implicitmultiply = true )

Parameters

 expr - list of integers or strings, sequence of integers, or an expression that contains %gcd(...) Euclid - (optional) truefalse to control whether the GCD will be calculated through Euclidean Algorithm (prime factorization is default) implicitmultiply - (optional) truefalse output = ... - (optional) option to control the return value displaystyle = ... - (optional) option to control the layout of the steps

Description

 • The GCDSteps command accepts a list or sequence of integers, or an expression that contains %gcd, and gives steps for calculating the Greatest Common Divisor (Greatest Common Factor). By default it gives steps to get GCD by doing prime factorization, but has the option to calculate it through the full Euclidean Algorithm if the optional parameter Euclid=true is given.
 • If the GCD is calculated through the Euclidean Algorithm, then the GCD will be the second-to-last element in the remainder column (r). In the same row as that entry, the values for s and t satisfy sa + tb = gcd(a, b), where a is the larger of the two values (the first value in the remainder row).
 • When expr is a list, one or more elements of the list can be given as a string. In this case, the string is parsed into an expression using InertForm:-Parse so that no automatic simplifications are applied, and thus no steps are missed.
 • The implicitmultiply option is only relevant when expr is a list of strings.  This option is passed directly on to the InertForm:-Parse command and will cause things like 2x to be interpreted as 2*x, but also, xyz to be interpreted as x*y*z.
 • The output and displaystyle options are described in Student:-Basics:-OutputStepsRecord. The return value is controlled by the output option.
 • This function is part of the Student:-Basics package.

Examples

 > $\mathrm{with}\left(\mathrm{Student}:-\mathrm{Basics}\right):$
 > $\mathrm{GCDSteps}\left(\left[12,3,4\right]\right)$
 $\begin{array}{lll}{}& {}& {\mathrm{GCD}}{}\left({12}{,}{3}{,}{4}\right)\\ \text{•}& {}& \text{Prime factorize each term:}\\ {}& {}& \left[\begin{array}{c}{12}{=}{\left({2}\right)}^{{2}}{}\left({3}\right)\\ {3}{=}\left({3}\right)\\ {4}{=}{\left({2}\right)}^{{2}}\end{array}\right]\\ \text{•}& {}& \text{Find the factors that are present in all terms}\\ {}& {}& {1}\end{array}$ (1)
 > $\mathrm{GCDSteps}\left(58,34,\mathrm{Euclid}=\mathrm{true}\right)$
 $\begin{array}{lll}{}& {}& {\mathrm{GCD}}{}\left({58}{,}{34}\right)\\ \text{•}& {}& \text{Do Euclidean Algorithm on}\phantom{\rule[-0.0ex]{1.0thickmathspace}{0.0ex}}\mathrm{GCD}{}\left(58,34\right)\\ {}& {}& \begin{array}{|cccc|}\hline {q}& {r}& {s}& {t}\\ {0}& {58}& {1}& {0}\\ {0}& {34}& {0}& {1}\\ {1}& {24}& {1}& {-1}\\ {1}& {10}& {-1}& {2}\\ {2}& {4}& {3}& {-5}\\ {2}& {2}& {-7}& {12}\\ {2}& {0}& {"/"}& {"/"}\\ \hline\end{array}\\ \text{•}& {}& \text{The GCD is the second-to-last element in the second column}\\ {}& {}& {2}\end{array}$ (2)
 > $\mathrm{GCDSteps}\left("gcd\left(348, 234\right) + gcd\left(4, 16\right) + 2"\right)$
 $\begin{array}{lll}{}& {}& {\mathrm{gcd}}{}\left({348}{,}{234}\right){+}{\mathrm{gcd}}{}\left({4}{,}{16}\right){+}{2}\\ \text{•}& {}& \text{Exmaine term}\\ {}& {}& {\mathrm{gcd}}{}\left({348}{,}{234}\right)\\ \text{•}& {}& \text{Prime factorize each term:}\\ {}& {}& \left[\begin{array}{c}{348}{=}{\left({2}\right)}^{{2}}{}\left({3}\right){}\left({29}\right)\\ {234}{=}\left({2}\right){}{\left({3}\right)}^{{2}}{}\left({13}\right)\end{array}\right]\\ \text{•}& {}& \text{Find the factors that are present in all terms}\\ {}& {}& \left({2}\right){}\left({3}\right)\\ \text{•}& {}& \text{Simplify}\\ {}& {}& {6}\\ \text{•}& {}& \text{This gives:}\\ {}& {}& {6}{+}{\mathrm{gcd}}{}\left({4}{,}{16}\right){+}{2}\\ \text{•}& {}& \text{Exmaine term}\\ {}& {}& {\mathrm{gcd}}{}\left({4}{,}{16}\right)\\ \text{•}& {}& \text{Prime factorize each term:}\\ {}& {}& \left[\begin{array}{c}{4}{=}{\left({2}\right)}^{{2}}\\ {16}{=}{\left({2}\right)}^{{4}}\end{array}\right]\\ \text{•}& {}& \text{Find the factors that are present in all terms}\\ {}& {}& {\left({2}\right)}^{{2}}\\ \text{•}& {}& \text{Simplify}\\ {}& {}& {4}\\ \text{•}& {}& \text{This gives:}\\ {}& {}& {6}{+}{4}{+}{2}\\ \text{•}& {}& \text{Simplify}\\ {}& {}& {12}\end{array}$ (3)

Compatibility

 • The Student:-Basics:-GCDSteps command was introduced in Maple 2024.