# GCD and Polynomials

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

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)
# 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)
\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: 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

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

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

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

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
g = -g
else
end
if s.x1 ~= nil and s.x2 ~= nil then
table.insert(eqs, {eq = formatQuadratic(a, b, c),
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}

• 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