%%
%% This is file `xintgcd.sty',
%% generated with the docstrip utility.
%%
%% The original source files were:
%%
%% xint.dtx  (with options: `xintgcd')
%% 
%% IMPORTANT NOTICE:
%% 
%% For the copyright see the source file.
%% 
%% Any modified versions of this file must be renamed
%% with new filenames distinct from xintgcd.sty.
%% 
%% For distribution of the original source see the terms
%% for copying and modification in the file xint.dtx.
%% 
%% This generated file may be distributed as long as the
%% original source files, as listed above, are part of the
%% same distribution. (The sources need not necessarily be
%% in the same archive or directory.)
%% ---------------------------------------------------------------
%% The xint bundle 1.4 2020/01/31
%% Copyright (C) 2013-2020 by Jean-Francois Burnol
%% xintgcd: Euclidean algorithm with xint package
%% ---------------------------------------------------------------
\begingroup\catcode61\catcode48\catcode32=10\relax%
  \catcode13=5    % ^^M
  \endlinechar=13 %
  \catcode123=1   % {
  \catcode125=2   % }
  \catcode64=11   % @
  \catcode35=6    % #
  \catcode44=12   % ,
  \catcode45=12   % -
  \catcode46=12   % .
  \catcode58=12   % :
  \def\z{\endgroup}%
  \expandafter\let\expandafter\x\csname ver@xintgcd.sty\endcsname
  \expandafter\let\expandafter\w\csname ver@xint.sty\endcsname
  \expandafter\let\expandafter\t\csname ver@xinttools.sty\endcsname
  \expandafter
    \ifx\csname PackageInfo\endcsname\relax
      \def\y#1#2{\immediate\write-1{Package #1 Info: #2.}}%
    \else
      \def\y#1#2{\PackageInfo{#1}{#2}}%
    \fi
  \expandafter
  \ifx\csname numexpr\endcsname\relax
     \y{xintgcd}{\numexpr not available, aborting input}%
     \aftergroup\endinput
  \else
    \ifx\x\relax   % plain-TeX, first loading of xintgcd.sty
      \ifx\w\relax % but xint.sty not yet loaded.
         \expandafter\def\expandafter\z\expandafter{\z\input xint.sty\relax}%
      \fi
      \ifx\t\relax % but xinttools.sty not yet loaded.
         \expandafter\def\expandafter\z\expandafter{\z\input xinttools.sty\relax}%
      \fi
    \else
      \def\empty {}%
      \ifx\x\empty % LaTeX, first loading,
      % variable is initialized, but \ProvidesPackage not yet seen
          \ifx\w\relax % xint.sty not yet loaded.
            \expandafter\def\expandafter\z\expandafter{\z\RequirePackage{xint}}%
          \fi
          \ifx\t\relax % xinttools.sty not yet loaded.
            \expandafter\def\expandafter\z\expandafter{\z\RequirePackage{xinttools}}%
          \fi
      \else
        \aftergroup\endinput % xintgcd already loaded.
      \fi
    \fi
  \fi
\z%
\XINTsetupcatcodes% defined in xintkernel.sty
\XINT_providespackage
\ProvidesPackage{xintgcd}%
  [2020/01/31 v1.4 Euclide algorithm with xint package (JFB)]%
\def\xintBezout {\romannumeral0\xintbezout }%
\def\xintbezout #1%
{%
    \expandafter\XINT_bezout\expandafter {\romannumeral0\xintnum{#1}}%
}%
\def\XINT_bezout #1#2%
{%
    \expandafter\XINT_bezout_fork \romannumeral0\xintnum{#2}\Z #1\Z
}%
\def\XINT_bezout_fork #1#2\Z #3#4\Z
{%
    \xint_UDzerosfork
     #1#3\XINT_bezout_botharezero
      #10\XINT_bezout_secondiszero
      #30\XINT_bezout_firstiszero
       00\xint_UDsignsfork
    \krof
          #1#3\XINT_bezout_minusminus % A < 0, B < 0
           #1-\XINT_bezout_minusplus  % A > 0, B < 0
           #3-\XINT_bezout_plusminus  % A < 0, B > 0
            --\XINT_bezout_plusplus   % A > 0, B > 0
    \krof
    {#2}{#4}#1#3% #1#2=B, #3#4=A
}%
\def\XINT_bezout_botharezero #1\krof#2#300{{0}{0}{0}}%
\def\XINT_bezout_firstiszero #1\krof#2#3#4#5%
{%
    \xint_UDsignfork
      #4{{0}{-1}{#2}}%
       -{{0}{1}{#4#2}}%
    \krof
}%
\def\XINT_bezout_secondiszero #1\krof#2#3#4#5%
{%
    \xint_UDsignfork
       #5{{-1}{0}{#3}}%
        -{{1}{0}{#5#3}}%
    \krof
}%
\def\XINT_bezout_minusminus #1#2#3#4%
{%
    \expandafter\XINT_bezout_mm_post
    \romannumeral0\expandafter\XINT_bezout_preloop_a
    \romannumeral0\XINT_div_prepare {#1}{#2}{#1}%
}%
\def\XINT_bezout_mm_post #1#2%
{%
    \expandafter\XINT_bezout_mm_postb\expandafter
    {\romannumeral0\xintiiopp{#2}}{\romannumeral0\xintiiopp{#1}}%
}%
\def\XINT_bezout_mm_postb #1#2{\expandafter{#2}{#1}}%
\def\XINT_bezout_minusplus #1#2#3#4%
{%
    \expandafter\XINT_bezout_mp_post
    \romannumeral0\expandafter\XINT_bezout_preloop_a
    \romannumeral0\XINT_div_prepare {#1}{#4#2}{#1}%
}%
\def\XINT_bezout_mp_post #1#2%
{%
    \expandafter\xint_exchangetwo_keepbraces\expandafter
    {\romannumeral0\xintiiopp {#2}}{#1}%
}%
\def\XINT_bezout_plusminus #1#2#3#4%
{%
    \expandafter\XINT_bezout_pm_post
    \romannumeral0\expandafter\XINT_bezout_preloop_a
    \romannumeral0\XINT_div_prepare {#3#1}{#2}{#3#1}%
}%
\def\XINT_bezout_pm_post #1{\expandafter{\romannumeral0\xintiiopp{#1}}}%
\def\XINT_bezout_plusplus #1#2#3#4%
{%
    \expandafter\XINT_bezout_preloop_a
    \romannumeral0\XINT_div_prepare {#3#1}{#4#2}{#3#1}%
}%
\def\XINT_bezout_preloop_a #1#2#3%
{%
    \if0#1\xint_dothis\XINT_bezout_preloop_exchange\fi
    \if0#2\xint_dothis\XINT_bezout_preloop_exit\fi
    \xint_orthat{\expandafter\XINT_bezout_loop_B}%
    \romannumeral0\XINT_div_prepare {#2}{#3}{#2}{#1}110%
}%
\def\XINT_bezout_preloop_exit
    \romannumeral0\XINT_div_prepare #1#2#3#4#5#6#7%
{%
    {0}{1}{#2}%
}%
\def\XINT_bezout_preloop_exchange
{%
    \expandafter\xint_exchangetwo_keepbraces
    \romannumeral0\expandafter\XINT_bezout_preloop_A
}%
\def\XINT_bezout_preloop_A #1#2#3#4%
{%
    \if0#2\xint_dothis\XINT_bezout_preloop_exit\fi
    \xint_orthat{\expandafter\XINT_bezout_loop_B}%
    \romannumeral0\XINT_div_prepare {#2}{#3}{#2}{#1}%
}%
\def\XINT_bezout_loop_B #1#2%
{%
    \if0#2\expandafter\XINT_bezout_exitA
     \else\expandafter\XINT_bezout_loop_C
    \fi {#1}{#2}%
}%
\def\XINT_bezout_loop_C #1#2#3#4#5#6#7%
{%
    \expandafter\XINT_bezout_loop_D\expandafter
        {\romannumeral0\xintiiadd{\XINT_mul_plusplus{}{}#1\xint:#4\xint:}{#6}}%
        {\romannumeral0\xintiiadd{\XINT_mul_plusplus{}{}#1\xint:#5\xint:}{#7}}%
    {#2}{#3}{#4}{#5}%
}%
\def\XINT_bezout_loop_D #1#2%
{%
    \expandafter\XINT_bezout_loop_E\expandafter{#2}{#1}%
}%
\def\XINT_bezout_loop_E #1#2#3#4%
{%
    \expandafter\XINT_bezout_loop_b
    \romannumeral0\XINT_div_prepare {#3}{#4}{#3}{#2}{#1}%
}%
\def\XINT_bezout_loop_b #1#2%
{%
    \if0#2\expandafter\XINT_bezout_exita
     \else\expandafter\XINT_bezout_loop_c
    \fi {#1}{#2}%
}%
\def\XINT_bezout_loop_c #1#2#3#4#5#6#7%
{%
    \expandafter\XINT_bezout_loop_d\expandafter
        {\romannumeral0\xintiiadd{\XINT_mul_plusplus{}{}#1\xint:#4\xint:}{#6}}%
        {\romannumeral0\xintiiadd{\XINT_mul_plusplus{}{}#1\xint:#5\xint:}{#7}}%
    {#2}{#3}{#4}{#5}%
}%
\def\XINT_bezout_loop_d #1#2%
{%
    \expandafter\XINT_bezout_loop_e\expandafter{#2}{#1}%
}%
\def\XINT_bezout_loop_e #1#2#3#4%
{%
    \expandafter\XINT_bezout_loop_B
    \romannumeral0\XINT_div_prepare {#3}{#4}{#3}{#2}{#1}%
}%
\def\XINT_bezout_exita #1#2#3#4#5#6#7{{-#5}{#4}{#3}}%
\def\XINT_bezout_exitA #1#2#3#4#5#6#7{{#5}{-#4}{#3}}%
\def\xintEuclideAlgorithm {\romannumeral0\xinteuclidealgorithm }%
\def\xinteuclidealgorithm #1%
{%
    \expandafter\XINT_euc\expandafter{\romannumeral0\xintiiabs{\xintNum{#1}}}%
}%
\def\XINT_euc #1#2%
{%
    \expandafter\XINT_euc_fork\romannumeral0\xintiiabs{\xintNum{#2}}\Z #1\Z
}%
\def\XINT_euc_fork #1#2\Z #3#4\Z
{%
    \xint_UDzerofork
      #1\XINT_euc_BisZero
      #3\XINT_euc_AisZero
       0\XINT_euc_a
    \krof
    {0}{#1#2}{#3#4}{{#3#4}{#1#2}}{}\Z
}%
\def\XINT_euc_AisZero #1#2#3#4#5#6{{1}{0}{#2}{#2}{0}{0}}%
\def\XINT_euc_BisZero #1#2#3#4#5#6{{1}{0}{#3}{#3}{0}{0}}%
\def\XINT_euc_a #1#2#3%
{%
    \expandafter\XINT_euc_b\the\numexpr #1+\xint_c_i\expandafter.%
    \romannumeral0\XINT_div_prepare {#2}{#3}{#2}%
}%
\def\XINT_euc_b #1.#2#3#4%
{%
    \XINT_euc_c #3\Z {#1}{#3}{#4}{{#2}{#3}}%
}%
\def\XINT_euc_c #1#2\Z
{%
    \xint_gob_til_zero #1\XINT_euc_end0\XINT_euc_a
}%
\def\XINT_euc_end0\XINT_euc_a #1#2#3#4\Z%
{%
    \expandafter\XINT_euc_end_a
    \romannumeral0%
    \XINT_rord_main {}#4{{#1}{#3}}%
    \xint:
      \xint_bye\xint_bye\xint_bye\xint_bye
      \xint_bye\xint_bye\xint_bye\xint_bye
    \xint:
}%
\def\XINT_euc_end_a #1#2#3{{#1}{#3}{#2}}%
\def\xintBezoutAlgorithm {\romannumeral0\xintbezoutalgorithm }%
\def\xintbezoutalgorithm #1%
{%
    \expandafter \XINT_bezalg
    \expandafter{\romannumeral0\xintiiabs{\xintNum{#1}}}%
}%
\def\XINT_bezalg #1#2%
{%
    \expandafter\XINT_bezalg_fork\romannumeral0\xintiiabs{\xintNum{#2}}\Z #1\Z
}%
\def\XINT_bezalg_fork #1#2\Z #3#4\Z
{%
    \xint_UDzerofork
      #1\XINT_bezalg_BisZero
      #3\XINT_bezalg_AisZero
       0\XINT_bezalg_a
    \krof
    0{#1#2}{#3#4}1001{{#3#4}{#1#2}}{}\Z
}%
\def\XINT_bezalg_AisZero #1#2#3\Z{{1}{0}{0}{1}{#2}{#2}{1}{0}{0}{0}{0}{1}}%
\def\XINT_bezalg_BisZero #1#2#3#4\Z{{1}{0}{0}{1}{#3}{#3}{1}{0}{0}{0}{0}{1}}%
\def\XINT_bezalg_a #1#2#3%
{%
    \expandafter\XINT_bezalg_b\the\numexpr #1+\xint_c_i\expandafter.%
    \romannumeral0\XINT_div_prepare {#2}{#3}{#2}%
}%
\def\XINT_bezalg_b #1.#2#3#4#5#6#7#8%
{%
    \expandafter\XINT_bezalg_c\expandafter
     {\romannumeral0\xintiiadd {\xintiiMul {#6}{#2}}{#8}}%
     {\romannumeral0\xintiiadd {\xintiiMul {#5}{#2}}{#7}}%
     {#1}{#2}{#3}{#4}{#5}{#6}%
}%
\def\XINT_bezalg_c #1#2#3#4#5#6%
{%
    \expandafter\XINT_bezalg_d\expandafter {#2}{#3}{#4}{#5}{#6}{#1}%
}%
\def\XINT_bezalg_d #1#2#3#4#5#6#7#8%
{%
    \XINT_bezalg_e #4\Z {#2}{#4}{#5}{#1}{#6}{#7}{#8}{{#3}{#4}{#1}{#6}}%
}%
\def\XINT_bezalg_e #1#2\Z
{%
    \xint_gob_til_zero #1\XINT_bezalg_end0\XINT_bezalg_a
}%
\def\XINT_bezalg_end0\XINT_bezalg_a #1#2#3#4#5#6#7#8\Z
{%
    \expandafter\XINT_bezalg_end_a
    \romannumeral0%
    \XINT_rord_main {}#8{{#1}{#3}}%
    \xint:
      \xint_bye\xint_bye\xint_bye\xint_bye
      \xint_bye\xint_bye\xint_bye\xint_bye
    \xint:
}%
\def\XINT_bezalg_end_a #1#2#3#4{{#1}{#3}{0}{1}{#2}{#4}{1}{0}}%
\def\xintTypesetEuclideAlgorithm {%
    \unless\ifdefined\xintAssignArray
       \errmessage
        {xintgcd: package xinttools is required for \string\xintTypesetEuclideAlgorithm}%
       \expandafter\xint_gobble_iii
    \fi
    \XINT_TypesetEuclideAlgorithm
}%
\def\XINT_TypesetEuclideAlgorithm #1#2%
{% l'algo remplace #1 et #2 par |#1| et |#2|
  \par
  \begingroup
    \xintAssignArray\xintEuclideAlgorithm {#1}{#2}\to\U
    \edef\A{\U2}\edef\B{\U4}\edef\N{\U1}%
    \setbox 0 \vbox{\halign {$##$\cr \A\cr \B \cr}}%
    \count 255 1
    \xintloop
      \indent\hbox to \wd 0 {\hfil$\U{\numexpr 2*\count255\relax}$}%
      ${} =  \U{\numexpr 2*\count255 + 3\relax}
      \times \U{\numexpr 2*\count255 + 2\relax}
          +  \U{\numexpr 2*\count255 + 4\relax}$%
    \ifnum \count255 < \N
      \par
      \advance \count255 1
    \repeat
  \endgroup
}%
\def\xintTypesetBezoutAlgorithm {%
    \unless\ifdefined\xintAssignArray
       \errmessage
        {xintgcd: package xinttools is required for \string\xintTypesetBezoutAlgorithm}%
       \expandafter\xint_gobble_iii
    \fi
    \XINT_TypesetBezoutAlgorithm
}%
\def\XINT_TypesetBezoutAlgorithm #1#2%
{%
  \par
  \begingroup
    \xintAssignArray\xintBezoutAlgorithm {#1}{#2}\to\BEZ
    \edef\A{\BEZ2}\edef\B{\BEZ6}\edef\N{\BEZ1}% A = |#1|, B = |#2|
    \setbox 0 \vbox{\halign {$##$\cr \A\cr \B \cr}}%
    \count255 1
    \xintloop
      \indent\hbox to \wd 0 {\hfil$\BEZ{4*\count255 - 2}$}%
      ${} =  \BEZ{4*\count255 + 5}
      \times \BEZ{4*\count255 + 2}
          +  \BEZ{4*\count255 + 6}$\hfill\break
      \hbox to \wd 0 {\hfil$\BEZ{4*\count255 +7}$}%
      ${} = \BEZ{4*\count255 + 5}
      \times \BEZ{4*\count255 + 3}
          +  \BEZ{4*\count255 - 1}$\hfill\break
      \hbox to \wd 0 {\hfil$\BEZ{4*\count255 +8}$}%
      ${} =  \BEZ{4*\count255 + 5}
      \times \BEZ{4*\count255 + 4}
          +  \BEZ{4*\count255 }$
      \par
    \ifnum \count255 < \N
    \advance \count255 1
  \repeat
    \edef\U{\BEZ{4*\N + 4}}%
    \edef\V{\BEZ{4*\N + 3}}%
    \edef\D{\BEZ5}%
    \ifodd\N
       $\U\times\A  - \V\times \B = -\D$%
    \else
       $\U\times\A - \V\times\B = \D$%
    \fi
    \par
  \endgroup
}%
\XINT_restorecatcodes_endinput%
\endinput
%%
%% End of file `xintgcd.sty'.
