2

Is there a simple command to find the greatest common divisor (GCD) of any set of terms?

I am trying to use random numbers to generate complex trinomials of the form ax^2+bx+c such that a,b,c are all integers and a is not one.

But sometimes I'm getting output such as:

5x^2+15x+10 in which case the student would factor out a 5 and do

5(x^2+3x+2)

5(x+2)(x+1)

I'd like my initial complex trinomials to lack a non-one GCD. Even better, if it's not too hard, I'd like to have the option of whether or not non-one GCD is permissible and to show the fully factored form of that trinomial.

The code below doesn't cut it.

What else do I need to do?

p.s. Ironically, I do not know how to show LaTeX output in these forums. Is that possible?

\documentclass{article}

\usepackage{ifthen}
\usepackage{pgf}
 \pgfmathsetseed{\number\pdfrandomseed}
\usepackage{pgffor}

\newcommand{\InitVariables}
{%
\pgfmathsetmacro{\a}{int(random(2,5))}
\pgfmathsetmacro{\b}{int(random(1,5))}
\pgfmathsetmacro{\c}{int(random(1,5))}
\pgfmathsetmacro{\d}{int(random(1,5))}
\pgfmathsetmacro{\A}{int(\a*\c)}
\pgfmathsetmacro{\B}{int(\a*\d+\b*\c)}
\pgfmathsetmacro{\C}{int(\b*\d)}
}

\newcommand{\ComplexTrinomial}
{%
\InitVariables
\large
\(\A{x}^2+\B{x}+\C=\)\hspace{4cm}\((\a{x}+\b)(\c{x}+\d)\)
\vspace{1cm}
}

\newcommand{\MyTrinomials}[1]
{\foreach \x in {1,2,...,#1} {\ComplexTrinomial\\}}

\begin{document}

\MyTrinomials{20}

\end{document}
  • to show output just crop a screenshot of your pdf viewer and post the image – David Carlisle Dec 14 '16 at 19:52
  • GCD finding is a highly nontrivial task for noninteger roots. I don't think you would be ever happy with the TeX precision. – percusse Dec 14 '16 at 20:07
  • @percusse Op only needs gcd of integer coeffs i think – David Carlisle Dec 14 '16 at 20:19
  • Is you real range 1-5 or just the example as if so you only need to check that a not= b and not both a,b even and c not= d and not both c,d even which is easy enough, although if you simply divide out the factor then the pair (1,1) will be a three times as likely as (1,5) as it could be generated from random (1,1) or (2,2) or (4,4), does that matter? – David Carlisle Dec 14 '16 at 20:24
  • @DavidCarlisle I think you need to convert to monic polynomials anyways and that might cause trouble. – percusse Dec 14 '16 at 20:39
4

Randomly generated polynomials? GCD of coefficients of the polynomial? You're using enough mathematics to consider using the sagemath package, located here on CTAN which allows you to harness the power of a free computer algebra system. After setting up the ring of polynomials with integer coefficients, poly1 = R.random_element(2) creates a random polynomial of degree at most 2. The next line checks that the polynomial has degree equal to 2, GCD of the coefficients (called the content) equals 1 (so no common factor) and makes sure the polynomial is not irreducible (can be factored). Note that Sage does the factoring for you so there shouldn't be any mistakes. The information on polynomial commands can be found here.

\documentclass{article}
\usepackage{sagetex}
\usepackage{amsmath}
\begin{document}
\begin{sagesilent}
R.<x>=ZZ[]  #ring of polynomials with integral coefficients
poly1 = R.random_element(2) #choose polynomial from the ring with degree at most 2
while poly1.degree() != 2 or poly1.content() != 1 or   poly1.is_irreducible() == True:
    poly1 = R.random_element(2)
answer1 = factor(poly1)
# while degree is not equal to 2 or the GCD of the coefficients is not 1, or
# the polynomial is irreducible, keep picking a polynomial
\end{sagesilent}
\begin{enumerate}
\item Factor the polynomial $\sage{poly1}$.\\\\\\
\noindent The answer is $\sage{answer1}$\\\\
\begin{sagesilent}
R.<x>=ZZ[]
poly2 = R.random_element(2)
while poly2.degree() != 2 or poly2.content() != 1 or poly2.is_irreducible() == True:
    poly2 = R.random_element(2)
answer2 = factor(poly2)
\end{sagesilent}
\item Factor the polynomial $\sage{poly2}$.\\\\\\
\noindent The answer is $\sage{answer2}$\\\\
\end{enumerate}
\end{document}

Running in Sagemath Cloud gives the output: enter image description here Using the sagemath package requires Sage on your computer (a pain) OR a free Sagemath Cloud account.

  • It sounds like there are a lot of people out there recommending the sagetex package. Can anyone recommend a video series and/or book for learning sagetex for someone who knows ~0 about programming like me? – WeCanLearnAnything May 30 '17 at 21:10
  • Learning sagetex means learning Sage,LaTeX,and a bit of Python.You have LaTeX;the CTAN link above has documentation for using sagetex. For Sage, there is free documentation here ;it's available at the Sagemath site, too. I bought "Sage Beginner's Guide" but it's a bit outdated now. I'd suggest getting a SagemathCloud (now CoCalc) account and go though videos here. Search this site for examples, figure how you will use it, try writing on your own, and ask when stuck. – DJP May 31 '17 at 1:43
2

More proof of concept than anything else. It could be written in pure TeX, but I was lazy. Requires LuaLaTeX.

\RequirePackage{luatex85}
\documentclass[varwidth,border=5]{standalone}
\usepackage{amsmath,luacode}
\textwidth=8cm
\begin{luacode*}
function gcd(u, v)
  u = math.abs(u)
  v = math.abs(v)
  if u == v then
    return u
  end
  if u == 0 then
    return v
  end
  if v == 0 then
    return u
  end
  if u % 2 == 0 then
    if v % 2 == 1 then
      return gcd(math.floor(u / 2), v)
    else
      return gcd(math.floor(u / 2), math.floor(v / 2)) * 2
    end
  else
    if v % 2 == 0 then
      return gcd(u, math.floor(v / 2))
    end

    if u > v then
      return gcd(math.floor((u - v) / 2), v)
    else
      return gcd(math.floor((v - u) / 2), u)
    end
  end
end

function solveQuadratic(a, b, c)
  local d, x1, x2;
  d  = b * b - 4 * a * c
  if d >= 0 then
     x1 = (-b - math.sqrt(d)) / (2 * a)
     x2 = (-b + math.sqrt(d)) / (2 * a)
     if x1 ~= math.floor(x1) or x2~= math.floor(x2) then
       x1 = nil
       x2 = nil
     end
  else
    x1 = nil
    x2 = nil
  end
  return {x1 = x1, x2 = x2}
end

function coef(a)
  if a == 1 then
    return ''
  else
    return a
  end
end

function formatCoef(a, c)
  local str = ''
  if a ~= 0 then
    if math.abs(a) > 1 or c == '' then
      str = str .. math.abs(a)
    end
    if a < 0 then
      str = '-' .. str
    end 
    str = str .. c
  end
  return str
end

function formatQuadratic(a, b, c)
  local str = ''
  str = formatCoef(a, 'x^2')
  if str ~= '' and b > 0 then
    str = str .. '+'
  end
  str = str .. formatCoef(b, 'x')
  if str ~= '' and c > 0 then
    str = str .. '+'
  end
  str = str .. formatCoef(c, '')
  return str
end

function formatFactoredQuadratic(x1, x2, g)
  local str = ''
  if x1 == 0 then
    str = 'x'
  else
    if x1 > 0 then
      str = str .. '(x + ' .. x1 .. ')'
    else
      str = str .. '(x ' .. x1 .. ')'
    end
  end
  if x2 == 0 then
    str = str .. 'x'
  else
    if x2 > 0 then
      str = str .. '(x + ' .. x2 .. ')'
    else
      str = str .. '(x ' .. x2 .. ')'
    end
  end
  if g ~= nil then
    if math.abs(g) > 1 then
      str = g .. str
    elseif g == -1 then
      str = '-' .. str
    end
  end
  return str
end
function genEq(n, gc)
  local a, b, c, g, h1, h2, eqs
  if gc == nil then
    h1 = 1
    h2 = 1000 -- some large number
  else
    h1 = 0
    h2 = 1
  end
  eqs = {n=0}
  for a = -n,n do  
    for b = -n,n do
      for c = -n,n do
        if a ~= 0 and b ~=0 and c ~= 0 then
          g = gcd(gcd(a, b), c)
          if g > h1 and g <= h2 then
            if a < 0 then
              s = solveQuadratic(-a, -b, -c)
              g = -g
            else
              s = solveQuadratic(a, b, c)
            end
            if s.x1 ~= nil and s.x2 ~= nil then
              table.insert(eqs, {eq = formatQuadratic(a, b, c),
                fct = formatFactoredQuadratic(-s.x1, -s.x2, g)})
              eqs.n = eqs.n + 1
            end
          end
        end
      end
    end
  end
  return eqs
end
\end{luacode*}
\begin{document}
\begin{align*}
\intertext{Lacking a non-1 GCD}
\directlua{%
eqs = genEq(10,1)
for i = 1,5 do
x = math.random(1, eqs.n)
tex.print(eqs[x].eq .. ' &= ' .. eqs[x].fct ..'\noexpand\\\noexpand\\')
end
}
\\\intertext{Not lacking a non-1 GCD}
\directlua{%
eqs = genEq(10)
for i = 1,5 do
x = math.random(1, eqs.n)
tex.print(eqs[x].eq .. ' &= ' .. eqs[x].fct ..'\noexpand\\\noexpand\\')
end
}
\\
\end{align*}
\end{document}

enter image description here

  • I think the OP is after the polynomial GCD – percusse Dec 16 '16 at 22:09
  • @percusse that's an excellent point. I really should read questions properly. – Mark Wibrow Dec 17 '16 at 15:57
  • @percusse actually I take that back... at least until my next mistake is discovered ;) – Mark Wibrow Dec 18 '16 at 9:20
  • Ahaha great. In case Python needed, I also amused myself quite some time with polynomials. – percusse Dec 18 '16 at 10:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.