Bignum: implement extended GCD (#18427)

4 files changed, 1174 insertions, 3 deletions

diff --git a/testsuite/tests/lib/integer/all.T b/testsuite/tests/lib/integer/all.T
index 0e32d11981..45270453a1 100644
--- a/testsuite/tests/lib/integer/all.T
+++ b/testsuite/tests/lib/integer/all.T
@@ -5,11 +5,12 @@ test('integerConstantFolding', normal, makefile_test, ['integerConstantFolding']
 test('fromToInteger', [], makefile_test, ['fromToInteger'])
 test('IntegerConversionRules', [], makefile_test, ['IntegerConversionRules'])
 test('gcdInteger', normal, compile_and_run, [''])
+test('gcdeInteger', normal, compile_and_run, [''])
 test('integerPowMod', [], compile_and_run, [''])
+test('integerGcdExt', [omit_ways(['ghci'])], compile_and_run, [''])
 
 # skip ghci as it doesn't support unboxed tuples
 test('integerImportExport', [omit_ways(['ghci'])], compile_and_run, [''])
 
 # Disable GMP only tests
-#test('integerGcdExt', [omit_ways(['ghci'])], compile_and_run, [''])
 #test('integerGmpInternals', [], compile_and_run, [''])
diff --git a/testsuite/tests/lib/integer/gcdeInteger.hs b/testsuite/tests/lib/integer/gcdeInteger.hs
new file mode 100644
index 0000000000..9fabc2cbce
--- /dev/null
+++ b/testsuite/tests/lib/integer/gcdeInteger.hs
@@ -0,0 +1,114 @@
+
+{-# LANGUAGE MagicHash #-}
+{-# LANGUAGE MultiWayIf #-}
+
+module Main (main) where
+
+import GHC.Base
+import GHC.Num.Integer
+import Control.Monad
+import System.Exit
+
+main :: IO ()
+main = do
+
+   let test a b = do
+         putStrLn $ "GCDE " ++ show a ++ " " ++ show b
+         let r@(g,x,y) = integerGcde a b
+         putStrLn $ "   -> g = " ++ show g
+         putStrLn $ "   -> x = " ++ show x
+         putStrLn $ "   -> y = " ++ show y
+         let sign a | a >= 0    = 1
+                    | otherwise = -1
+         let assert text cond term
+               | not cond  = return ()
+               | term      = return ()
+               | otherwise = do
+                  putStrLn $ "FAILED: " ++ text
+                  putStrLn $ "a*x + b*y = g"
+                  putStrLn $ "a = " ++ show a
+                  putStrLn $ "b = " ++ show b
+                  putStrLn $ "x = " ++ show x
+                  putStrLn $ "y = " ++ show y
+                  putStrLn $ "g = " ++ show g
+                  putStrLn $ "expected g = " ++ show (abs (integerGcd a b))
+                  exitFailure
+
+         -- check properties
+         assert "g >= 0"            True (g >= 0)
+         assert "a*x + b*y = g"     True (a*x + b*y == g)
+         assert "g = abs (gcd a b)" True (g == abs (integerGcd a b))
+
+         if -- special cases
+            | a == 0 && b == 0 -> do
+               assert "a == 0 && b ==0 ==> g == 0" (a == 0 && b == 0) (g == 0)
+
+            | abs a == abs b -> do
+               assert "abs a == abs b ==> x == 0 && y == sign b && g == abs a"
+                  (abs a == abs b) (x == 0 && y == sign b && g == abs a)
+
+            -- non special cases
+            | otherwise -> do
+               assert "b == 0 ==> x=sign a"
+                  (b == 0)
+                  (x == sign a)
+
+               assert "abs b == 2g ==> x=sign a"
+                  (abs b == 2*g)
+                  (x == sign a)
+
+               assert "b /= 0 ==> abs x <= abs b / 2*g"
+                  (b /= 0)
+                  (abs x <= abs b `div` 2 * g)
+
+               assert "a /= 0 ==> abs y <= abs a / 2*g"
+                  (a /= 0)
+                  (abs y <= abs a `div` 2 * g)
+
+               assert "a == 0 ==> y=sign b"
+                  (a == 0)
+                  (y == sign b)
+
+               assert "abs a == 2g ==> y==sign b"
+                  (abs a == 2*g)
+                  (y == sign b)
+
+               assert "x == 0 ==> g == abs b"
+                  (x == 0)
+                  (g == abs b)
+
+       nums =
+            [ 0
+            , 1
+            , 7
+            , 14
+            , 123
+            , 1230
+            , 123456789456789456789456789456789456789465789465456789465454645789
+            , 4 * 123456789456789456789456789456789456789465789465456789465454645789
+            , -1
+            , -123
+            , -123456789456789456789456789456789456789465789465456789465454645789
+            , 4567897897897897899789897897978978979789
+            , 2988348162058574136915891421498819466320163312926952423791023078876139
+            , 2351399303373464486466122544523690094744975233415544072992656881240319
+            , 5328841272400314897981163497728751426
+            , 32052182750761975518649228050096851724
+            ]
+
+   forM_ nums $ \a ->
+      forM_ nums $ \b ->
+         test a b
+
+   -- see #15350
+   do
+       let a = 2
+           b = 2^65 + 1
+       test a b
+       test a (-b)
+       test (-a) b
+       test (-a) (-b)
+       test b a
+       test b (-a)
+       test (-b) a
+       test (-b) (-a)
diff --git a/testsuite/tests/lib/integer/gcdeInteger.stdout b/testsuite/tests/lib/integer/gcdeInteger.stdout
new file mode 100644
index 0000000000..f4854ddb08
--- /dev/null
+++ b/testsuite/tests/lib/integer/gcdeInteger.stdout
@@ -0,0 +1,1056 @@
+GCDE 0 0
+   -> g = 0
+   -> x = 0
+   -> y = 0
+GCDE 0 1
+   -> g = 1
+   -> x = 0
+   -> y = 1
+GCDE 0 7
+   -> g = 7
+   -> x = 0
+   -> y = 1
+GCDE 0 14
+   -> g = 14
+   -> x = 0
+   -> y = 1
+GCDE 0 123
+   -> g = 123
+   -> x = 0
+   -> y = 1
+GCDE 0 1230
+   -> g = 1230
+   -> x = 0
+   -> y = 1
+GCDE 0 123456789456789456789456789456789456789465789465456789465454645789
+   -> g = 123456789456789456789456789456789456789465789465456789465454645789
+   -> x = 0
+   -> y = 1
+GCDE 0 493827157827157827157827157827157827157863157861827157861818583156
+   -> g = 493827157827157827157827157827157827157863157861827157861818583156
+   -> x = 0
+   -> y = 1
+GCDE 0 -1
+   -> g = 1
+   -> x = 0
+   -> y = -1
+GCDE 0 -123
+   -> g = 123
+   -> x = 0
+   -> y = -1
+GCDE 0 -123456789456789456789456789456789456789465789465456789465454645789
+   -> g = 123456789456789456789456789456789456789465789465456789465454645789
+   -> x = 0
+   -> y = -1
+GCDE 0 4567897897897897899789897897978978979789
+   -> g = 4567897897897897899789897897978978979789
+   -> x = 0
+   -> y = 1
+GCDE 0 2988348162058574136915891421498819466320163312926952423791023078876139
+   -> g = 2988348162058574136915891421498819466320163312926952423791023078876139
+   -> x = 0
+   -> y = 1
+GCDE 0 2351399303373464486466122544523690094744975233415544072992656881240319
+   -> g = 2351399303373464486466122544523690094744975233415544072992656881240319
+   -> x = 0
+   -> y = 1
+GCDE 0 5328841272400314897981163497728751426
+   -> g = 5328841272400314897981163497728751426
+   -> x = 0
+   -> y = 1
+GCDE 0 32052182750761975518649228050096851724
+   -> g = 32052182750761975518649228050096851724
+   -> x = 0
+   -> y = 1
+GCDE 1 0
+   -> g = 1
+   -> x = 1
+   -> y = 0
+GCDE 1 1
+   -> g = 1
+   -> x = 0
+   -> y = 1
+GCDE 1 7
+   -> g = 1
+   -> x = 1
+   -> y = 0
+GCDE 1 14
+   -> g = 1
+   -> x = 1
+   -> y = 0
+GCDE 1 123
+   -> g = 1
+   -> x = 1
+   -> y = 0
+GCDE 1 1230
+   -> g = 1
+   -> x = 1
+   -> y = 0
+GCDE 1 123456789456789456789456789456789456789465789465456789465454645789
+   -> g = 1
+   -> x = 1
+   -> y = 0
+GCDE 1 493827157827157827157827157827157827157863157861827157861818583156
+   -> g = 1
+   -> x = 1
+   -> y = 0
+GCDE 1 -1
+   -> g = 1
+   -> x = 0
+   -> y = -1
+GCDE 1 -123
+   -> g = 1
+   -> x = 1
+   -> y = 0
+GCDE 1 -123456789456789456789456789456789456789465789465456789465454645789
+   -> g = 1
+   -> x = 1
+   -> y = 0
+GCDE 1 4567897897897897899789897897978978979789
+   -> g = 1
+   -> x = 1
+   -> y = 0
+GCDE 1 2988348162058574136915891421498819466320163312926952423791023078876139
+   -> g = 1
+   -> x = 1
+   -> y = 0
+GCDE 1 2351399303373464486466122544523690094744975233415544072992656881240319
+   -> g = 1
+   -> x = 1
+   -> y = 0
+GCDE 1 5328841272400314897981163497728751426
+   -> g = 1
+   -> x = 1
+   -> y = 0
+GCDE 1 32052182750761975518649228050096851724
+   -> g = 1
+   -> x = 1
+   -> y = 0
+GCDE 7 0
+   -> g = 7
+   -> x = 1
+   -> y = 0
+GCDE 7 1
+   -> g = 1
+   -> x = 0
+   -> y = 1
+GCDE 7 7
+   -> g = 7
+   -> x = 0
+   -> y = 1
+GCDE 7 14
+   -> g = 7
+   -> x = 1
+   -> y = 0
+GCDE 7 123
+   -> g = 1
+   -> x = -35
+   -> y = 2
+GCDE 7 1230
+   -> g = 1
+   -> x = -527
+   -> y = 3
+GCDE 7 123456789456789456789456789456789456789465789465456789465454645789
+   -> g = 1
+   -> x = -52910052624338338624052909767195481481199624056624338342337705338
+   -> y = 3
+GCDE 7 493827157827157827157827157827157827157863157861827157861818583156
+   -> g = 1
+   -> x = 70546736832451118165403879689593975308266165408832451123116940451
+   -> y = -1
+GCDE 7 -1
+   -> g = 1
+   -> x = 0
+   -> y = -1
+GCDE 7 -123
+   -> g = 1
+   -> x = -35
+   -> y = -2
+GCDE 7 -123456789456789456789456789456789456789465789465456789465454645789
+   -> g = 1
+   -> x = -52910052624338338624052909767195481481199624056624338342337705338
+   -> y = -3
+GCDE 7 4567897897897897899789897897978978979789
+   -> g = 1
+   -> x = -1305113685113685114225685113708279708511
+   -> y = 2
+GCDE 7 2988348162058574136915891421498819466320163312926952423791023078876139
+   -> g = 1
+   -> x = 1280720640882246058678239180642351199851498562682979610196152748089774
+   -> y = -3
+GCDE 7 2351399303373464486466122544523690094744975233415544072992656881240319
+   -> g = 1
+   -> x = -671828372392418424704606441292482884212850066690155449426473394640091
+   -> y = 2
+GCDE 7 5328841272400314897981163497728751426
+   -> g = 1
+   -> x = 2283789116742992099134784356169464897
+   -> y = -3
+GCDE 7 32052182750761975518649228050096851724
+   -> g = 1
+   -> x = -13736649750326560936563954878612936453
+   -> y = 3
+GCDE 14 0
+   -> g = 14
+   -> x = 1
+   -> y = 0
+GCDE 14 1
+   -> g = 1
+   -> x = 0
+   -> y = 1
+GCDE 14 7
+   -> g = 7
+   -> x = 0
+   -> y = 1
+GCDE 14 14
+   -> g = 14
+   -> x = 0
+   -> y = 1
+GCDE 14 123
+   -> g = 1
+   -> x = 44
+   -> y = -5
+GCDE 14 1230
+   -> g = 2
+   -> x = 88
+   -> y = -1
+GCDE 14 123456789456789456789456789456789456789465789465456789465454645789
+   -> g = 1
+   -> x = -26455026312169169312026454883597740740599812028312169171168852669
+   -> y = 3
+GCDE 14 493827157827157827157827157827157827157863157861827157861818583156
+   -> g = 2
+   -> x = 70546736832451118165403879689593975308266165408832451123116940451
+   -> y = -2
+GCDE 14 -1
+   -> g = 1
+   -> x = 0
+   -> y = -1
+GCDE 14 -123
+   -> g = 1
+   -> x = 44
+   -> y = 5
+GCDE 14 -123456789456789456789456789456789456789465789465456789465454645789
+   -> g = 1
+   -> x = -26455026312169169312026454883597740740599812028312169171168852669
+   -> y = -3
+GCDE 14 4567897897897897899789897897978978979789
+   -> g = 1
+   -> x = 1631392106392106392782106392135349635639
+   -> y = -5
+GCDE 14 2988348162058574136915891421498819466320163312926952423791023078876139
+   -> g = 1
+   -> x = 640360320441123029339119590321175599925749281341489805098076374044887
+   -> y = -3
+GCDE 14 2351399303373464486466122544523690094744975233415544072992656881240319
+   -> g = 1
+   -> x = 839785465490523030880758051615603605266062583362694311783091743300114
+   -> y = -5
+GCDE 14 5328841272400314897981163497728751426
+   -> g = 2
+   -> x = -380631519457165349855797392694910816
+   -> y = 1
+GCDE 14 32052182750761975518649228050096851724
+   -> g = 2
+   -> x = 2289441625054426822760659146435489409
+   -> y = -1
+GCDE 123 0
+   -> g = 123
+   -> x = 1
+   -> y = 0
+GCDE 123 1
+   -> g = 1
+   -> x = 0
+   -> y = 1
+GCDE 123 7
+   -> g = 1
+   -> x = 2
+   -> y = -35
+GCDE 123 14
+   -> g = 1
+   -> x = -5
+   -> y = 44
+GCDE 123 123
+   -> g = 123
+   -> x = 0
+   -> y = 1
+GCDE 123 1230
+   -> g = 123
+   -> x = 1
+   -> y = 0
+GCDE 123 123456789456789456789456789456789456789465789465456789465454645789
+   -> g = 1
+   -> x = -49181973035631572216938070596607181973039216941523436453717704420
+   -> y = 49
+GCDE 123 493827157827157827157827157827157827157863157861827157861818583156
+   -> g = 1
+   -> x = -172638762492421029006394860053396638762505006406980225919172350209
+   -> y = 43
+GCDE 123 -1
+   -> g = 1
+   -> x = 0
+   -> y = -1
+GCDE 123 -123
+   -> g = 123
+   -> x = 0
+   -> y = -1
+GCDE 123 -123456789456789456789456789456789456789465789465456789465454645789
+   -> g = 1
+   -> x = -49181973035631572216938070596607181973039216941523436453717704420
+   -> y = -49
+GCDE 123 4567897897897897899789897897978978979789
+   -> g = 1
+   -> x = 854159769525623184513558143524524524676
+   -> y = -23
+GCDE 123 2988348162058574136915891421498819466320163312926952423791023078876139
+   -> g = 1
+   -> x = 1360548756709594729002357069950682033446578418893571835221929206642795
+   -> y = -56
+GCDE 123 2351399303373464486466122544523690094744975233415544072992656881240319
+   -> g = 1
+   -> x = -1108789915411877562723862663271333540611451736082126473443691862698687
+   -> y = 58
+GCDE 123 5328841272400314897981163497728751426
+   -> g = 3
+   -> x = 606534778972393565623872268034166829
+   -> y = -14
+GCDE 123 32052182750761975518649228050096851724
+   -> g = 3
+   -> x = 1042347406528844732313796034149491113
+   -> y = -4
+GCDE 1230 0
+   -> g = 1230
+   -> x = 1
+   -> y = 0
+GCDE 1230 1
+   -> g = 1
+   -> x = 0
+   -> y = 1
+GCDE 1230 7
+   -> g = 1
+   -> x = 3
+   -> y = -527
+GCDE 1230 14
+   -> g = 2
+   -> x = -1
+   -> y = 88
+GCDE 1230 123
+   -> g = 123
+   -> x = 0
+   -> y = 1
+GCDE 1230 1230
+   -> g = 1230
+   -> x = 0
+   -> y = 1
+GCDE 1230 123456789456789456789456789456789456789465789465456789465454645789
+   -> g = 1
+   -> x = -4918197303563157221693807059660718197303921694152343645371770442
+   -> y = 49
+GCDE 1230 493827157827157827157827157827157827157863157861827157861818583156
+   -> g = 2
+   -> x = 113620394849663142346069175337468020394857946077152102174711104905
+   -> y = -283
+GCDE 1230 -1
+   -> g = 1
+   -> x = 0
+   -> y = -1
+GCDE 1230 -123
+   -> g = 123
+   -> x = 0
+   -> y = -1
+GCDE 1230 -123456789456789456789456789456789456789465789465456789465454645789
+   -> g = 1
+   -> x = -4918197303563157221693807059660718197303921694152343645371770442
+   -> y = -49
+GCDE 1230 4567897897897897899789897897978978979789
+   -> g = 1
+   -> x = -1741743182206596841464603344839139139448
+   -> y = 469
+GCDE 1230 2988348162058574136915891421498819466320163312926952423791023078876139
+   -> g = 1
+   -> x = -1358119205358327595557710003754341529815423814574119028373318618773790
+   -> y = 559
+GCDE 1230 2351399303373464486466122544523690094744975233415544072992656881240319
+   -> g = 1
+   -> x = 594540799470851589667450497029973674362347396416450574553427878102227
+   -> y = -311
+GCDE 1230 5328841272400314897981163497728751426
+   -> g = 6
+   -> x = 298934998207822543057479903531125080
+   -> y = -69
+GCDE 1230 32052182750761975518649228050096851724
+   -> g = 6
+   -> x = -1928342702078362754780522663176558559
+   -> y = 74
+GCDE 123456789456789456789456789456789456789465789465456789465454645789 0
+   -> g = 123456789456789456789456789456789456789465789465456789465454645789
+   -> x = 1
+   -> y = 0
+GCDE 123456789456789456789456789456789456789465789465456789465454645789 1
+   -> g = 1
+   -> x = 0
+   -> y = 1
+GCDE 123456789456789456789456789456789456789465789465456789465454645789 7
+   -> g = 1
+   -> x = 3
+   -> y = -52910052624338338624052909767195481481199624056624338342337705338
+GCDE 123456789456789456789456789456789456789465789465456789465454645789 14
+   -> g = 1
+   -> x = 3
+   -> y = -26455026312169169312026454883597740740599812028312169171168852669
+GCDE 123456789456789456789456789456789456789465789465456789465454645789 123
+   -> g = 1
+   -> x = 49
+   -> y = -49181973035631572216938070596607181973039216941523436453717704420
+GCDE 123456789456789456789456789456789456789465789465456789465454645789 1230
+   -> g = 1
+   -> x = 49
+   -> y = -4918197303563157221693807059660718197303921694152343645371770442
+GCDE 123456789456789456789456789456789456789465789465456789465454645789 123456789456789456789456789456789456789465789465456789465454645789
+   -> g = 123456789456789456789456789456789456789465789465456789465454645789
+   -> x = 0
+   -> y = 1
+GCDE 123456789456789456789456789456789456789465789465456789465454645789 493827157827157827157827157827157827157863157861827157861818583156
+   -> g = 123456789456789456789456789456789456789465789465456789465454645789
+   -> x = 1
+   -> y = 0
+GCDE 123456789456789456789456789456789456789465789465456789465454645789 -1
+   -> g = 1
+   -> x = 0
+   -> y = -1
+GCDE 123456789456789456789456789456789456789465789465456789465454645789 -123
+   -> g = 1
+   -> x = 49
+   -> y = 49181973035631572216938070596607181973039216941523436453717704420
+GCDE 123456789456789456789456789456789456789465789465456789465454645789 -123456789456789456789456789456789456789465789465456789465454645789
+   -> g = 123456789456789456789456789456789456789465789465456789465454645789
+   -> x = 0
+   -> y = -1
+GCDE 123456789456789456789456789456789456789465789465456789465454645789 4567897897897897899789897897978978979789
+   -> g = 1
+   -> x = -142355531505412253555567593395647545708
+   -> y = 3847449587076097018280777909186630028091235782450380442052224817
+GCDE 123456789456789456789456789456789456789465789465456789465454645789 2988348162058574136915891421498819466320163312926952423791023078876139
+   -> g = 1
+   -> x = 501499981494162622976489092493961483514126808861435716131179868189595
+   -> y = -20718328076357217180814970215022985846592184263422313201087532586
+GCDE 123456789456789456789456789456789456789465789465456789465454645789 2351399303373464486466122544523690094744975233415544072992656881240319
+   -> g = 1
+   -> x = 608000101055682152473830041965606704242079033852469328931798308452101
+   -> y = -31922158162609726789179865549911873484290325403318594248193251952
+GCDE 123456789456789456789456789456789456789465789465456789465454645789 5328841272400314897981163497728751426
+   -> g = 1
+   -> x = -233831227202814412604649442847121617
+   -> y = 5417322661629453658993420651614628087475941267504880682551205239
+GCDE 123456789456789456789456789456789456789465789465456789465454645789 32052182750761975518649228050096851724
+   -> g = 1
+   -> x = 2649042575281623182157985423209129457
+   -> y = -10203432759063496909071922280945854833629276496909075027106202353
+GCDE 493827157827157827157827157827157827157863157861827157861818583156 0
+   -> g = 493827157827157827157827157827157827157863157861827157861818583156
+   -> x = 1
+   -> y = 0
+GCDE 493827157827157827157827157827157827157863157861827157861818583156 1
+   -> g = 1
+   -> x = 0
+   -> y = 1
+GCDE 493827157827157827157827157827157827157863157861827157861818583156 7
+   -> g = 1
+   -> x = -1
+   -> y = 70546736832451118165403879689593975308266165408832451123116940451
+GCDE 493827157827157827157827157827157827157863157861827157861818583156 14
+   -> g = 2
+   -> x = -2
+   -> y = 70546736832451118165403879689593975308266165408832451123116940451
+GCDE 493827157827157827157827157827157827157863157861827157861818583156 123
+   -> g = 1
+   -> x = 43
+   -> y = -172638762492421029006394860053396638762505006406980225919172350209
+GCDE 493827157827157827157827157827157827157863157861827157861818583156 1230
+   -> g = 2
+   -> x = -283
+   -> y = 113620394849663142346069175337468020394857946077152102174711104905
+GCDE 493827157827157827157827157827157827157863157861827157861818583156 123456789456789456789456789456789456789465789465456789465454645789
+   -> g = 123456789456789456789456789456789456789465789465456789465454645789
+   -> x = 0
+   -> y = 1
+GCDE 493827157827157827157827157827157827157863157861827157861818583156 493827157827157827157827157827157827157863157861827157861818583156
+   -> g = 493827157827157827157827157827157827157863157861827157861818583156
+   -> x = 0
+   -> y = 1
+GCDE 493827157827157827157827157827157827157863157861827157861818583156 -1
+   -> g = 1
+   -> x = 0
+   -> y = -1
+GCDE 493827157827157827157827157827157827157863157861827157861818583156 -123
+   -> g = 1
+   -> x = 43
+   -> y = 172638762492421029006394860053396638762505006406980225919172350209
+GCDE 493827157827157827157827157827157827157863157861827157861818583156 -123456789456789456789456789456789456789465789465456789465454645789
+   -> g = 123456789456789456789456789456789456789465789465456789465454645789
+   -> x = 0
+   -> y = -1
+GCDE 493827157827157827157827157827157827157863157861827157861818583156 4567897897897897899789897897978978979789
+   -> g = 1
+   -> x = -35588882876353063388891898348911886427
+   -> y = 3847449587076097018280777909186630028091235782450380442052224817
+GCDE 493827157827157827157827157827157827157863157861827157861818583156 2988348162058574136915891421498819466320163312926952423791023078876139
+   -> g = 1
+   -> x = -621712045141102878484850582251214495701509126016379176914960802671636
+   -> y = 102738461380432239608641819241766470942873605202034476264367113203
+GCDE 493827157827157827157827157827157827157863157861827157861818583156 2351399303373464486466122544523690094744975233415544072992656881240319
+   -> g = 1
+   -> x = 739849851107286659734988146622324199746763566817003350481113797423105
+   -> y = -155378947619399183578636655006701330273756114868775383713647897741
+GCDE 493827157827157827157827157827157827157863157861827157861818583156 5328841272400314897981163497728751426
+   -> g = 2
+   -> x = 1215294704498671518192966153008627048
+   -> y = -112622144133530549471469948153560200614513906930447028100352235311
+GCDE 493827157827157827157827157827157827157863157861827157861818583156 32052182750761975518649228050096851724
+   -> g = 4
+   -> x = 2649042575281623182157985423209129457
+   -> y = -40813731036253987636287689123783419334517105987636300108424809412
+GCDE -1 0
+   -> g = 1
+   -> x = -1
+   -> y = 0
+GCDE -1 1
+   -> g = 1
+   -> x = 0
+   -> y = 1
+GCDE -1 7
+   -> g = 1
+   -> x = -1
+   -> y = 0
+GCDE -1 14
+   -> g = 1
+   -> x = -1
+   -> y = 0
+GCDE -1 123
+   -> g = 1
+   -> x = -1
+   -> y = 0
+GCDE -1 1230
+   -> g = 1
+   -> x = -1
+   -> y = 0
+GCDE -1 123456789456789456789456789456789456789465789465456789465454645789
+   -> g = 1
+   -> x = -1
+   -> y = 0
+GCDE -1 493827157827157827157827157827157827157863157861827157861818583156
+   -> g = 1
+   -> x = -1
+   -> y = 0
+GCDE -1 -1
+   -> g = 1
+   -> x = 0
+   -> y = -1
+GCDE -1 -123
+   -> g = 1
+   -> x = -1
+   -> y = 0
+GCDE -1 -123456789456789456789456789456789456789465789465456789465454645789
+   -> g = 1
+   -> x = -1
+   -> y = 0
+GCDE -1 4567897897897897899789897897978978979789
+   -> g = 1
+   -> x = -1
+   -> y = 0
+GCDE -1 2988348162058574136915891421498819466320163312926952423791023078876139
+   -> g = 1
+   -> x = -1
+   -> y = 0
+GCDE -1 2351399303373464486466122544523690094744975233415544072992656881240319
+   -> g = 1
+   -> x = -1
+   -> y = 0
+GCDE -1 5328841272400314897981163497728751426
+   -> g = 1
+   -> x = -1
+   -> y = 0
+GCDE -1 32052182750761975518649228050096851724
+   -> g = 1
+   -> x = -1
+   -> y = 0
+GCDE -123 0
+   -> g = 123
+   -> x = -1
+   -> y = 0
+GCDE -123 1
+   -> g = 1
+   -> x = 0
+   -> y = 1
+GCDE -123 7
+   -> g = 1
+   -> x = -2
+   -> y = -35
+GCDE -123 14
+   -> g = 1
+   -> x = 5
+   -> y = 44
+GCDE -123 123
+   -> g = 123
+   -> x = 0
+   -> y = 1
+GCDE -123 1230
+   -> g = 123
+   -> x = -1
+   -> y = 0
+GCDE -123 123456789456789456789456789456789456789465789465456789465454645789
+   -> g = 1
+   -> x = 49181973035631572216938070596607181973039216941523436453717704420
+   -> y = 49
+GCDE -123 493827157827157827157827157827157827157863157861827157861818583156
+   -> g = 1
+   -> x = 172638762492421029006394860053396638762505006406980225919172350209
+   -> y = 43
+GCDE -123 -1
+   -> g = 1
+   -> x = 0
+   -> y = -1
+GCDE -123 -123
+   -> g = 123
+   -> x = 0
+   -> y = -1
+GCDE -123 -123456789456789456789456789456789456789465789465456789465454645789
+   -> g = 1
+   -> x = 49181973035631572216938070596607181973039216941523436453717704420
+   -> y = -49
+GCDE -123 4567897897897897899789897897978978979789
+   -> g = 1
+   -> x = -854159769525623184513558143524524524676
+   -> y = -23
+GCDE -123 2988348162058574136915891421498819466320163312926952423791023078876139
+   -> g = 1
+   -> x = -1360548756709594729002357069950682033446578418893571835221929206642795
+   -> y = -56
+GCDE -123 2351399303373464486466122544523690094744975233415544072992656881240319
+   -> g = 1
+   -> x = 1108789915411877562723862663271333540611451736082126473443691862698687
+   -> y = 58
+GCDE -123 5328841272400314897981163497728751426
+   -> g = 3
+   -> x = -606534778972393565623872268034166829
+   -> y = -14
+GCDE -123 32052182750761975518649228050096851724
+   -> g = 3
+   -> x = -1042347406528844732313796034149491113
+   -> y = -4
+GCDE -123456789456789456789456789456789456789465789465456789465454645789 0
+   -> g = 123456789456789456789456789456789456789465789465456789465454645789
+   -> x = -1
+   -> y = 0
+GCDE -123456789456789456789456789456789456789465789465456789465454645789 1
+   -> g = 1
+   -> x = 0
+   -> y = 1
+GCDE -123456789456789456789456789456789456789465789465456789465454645789 7
+   -> g = 1
+   -> x = -3
+   -> y = -52910052624338338624052909767195481481199624056624338342337705338
+GCDE -123456789456789456789456789456789456789465789465456789465454645789 14
+   -> g = 1
+   -> x = -3
+   -> y = -26455026312169169312026454883597740740599812028312169171168852669
+GCDE -123456789456789456789456789456789456789465789465456789465454645789 123
+   -> g = 1
+   -> x = -49
+   -> y = -49181973035631572216938070596607181973039216941523436453717704420
+GCDE -123456789456789456789456789456789456789465789465456789465454645789 1230
+   -> g = 1
+   -> x = -49
+   -> y = -4918197303563157221693807059660718197303921694152343645371770442
+GCDE -123456789456789456789456789456789456789465789465456789465454645789 123456789456789456789456789456789456789465789465456789465454645789
+   -> g = 123456789456789456789456789456789456789465789465456789465454645789
+   -> x = 0
+   -> y = 1
+GCDE -123456789456789456789456789456789456789465789465456789465454645789 493827157827157827157827157827157827157863157861827157861818583156
+   -> g = 123456789456789456789456789456789456789465789465456789465454645789
+   -> x = -1
+   -> y = 0
+GCDE -123456789456789456789456789456789456789465789465456789465454645789 -1
+   -> g = 1
+   -> x = 0
+   -> y = -1
+GCDE -123456789456789456789456789456789456789465789465456789465454645789 -123
+   -> g = 1
+   -> x = -49
+   -> y = 49181973035631572216938070596607181973039216941523436453717704420
+GCDE -123456789456789456789456789456789456789465789465456789465454645789 -123456789456789456789456789456789456789465789465456789465454645789
+   -> g = 123456789456789456789456789456789456789465789465456789465454645789
+   -> x = 0
+   -> y = -1
+GCDE -123456789456789456789456789456789456789465789465456789465454645789 4567897897897897899789897897978978979789
+   -> g = 1
+   -> x = 142355531505412253555567593395647545708
+   -> y = 3847449587076097018280777909186630028091235782450380442052224817
+GCDE -123456789456789456789456789456789456789465789465456789465454645789 2988348162058574136915891421498819466320163312926952423791023078876139
+   -> g = 1
+   -> x = -501499981494162622976489092493961483514126808861435716131179868189595
+   -> y = -20718328076357217180814970215022985846592184263422313201087532586
+GCDE -123456789456789456789456789456789456789465789465456789465454645789 2351399303373464486466122544523690094744975233415544072992656881240319
+   -> g = 1
+   -> x = -608000101055682152473830041965606704242079033852469328931798308452101
+   -> y = -31922158162609726789179865549911873484290325403318594248193251952
+GCDE -123456789456789456789456789456789456789465789465456789465454645789 5328841272400314897981163497728751426
+   -> g = 1
+   -> x = 233831227202814412604649442847121617
+   -> y = 5417322661629453658993420651614628087475941267504880682551205239
+GCDE -123456789456789456789456789456789456789465789465456789465454645789 32052182750761975518649228050096851724
+   -> g = 1
+   -> x = -2649042575281623182157985423209129457
+   -> y = -10203432759063496909071922280945854833629276496909075027106202353
+GCDE 4567897897897897899789897897978978979789 0
+   -> g = 4567897897897897899789897897978978979789
+   -> x = 1
+   -> y = 0
+GCDE 4567897897897897899789897897978978979789 1
+   -> g = 1
+   -> x = 0
+   -> y = 1
+GCDE 4567897897897897899789897897978978979789 7
+   -> g = 1
+   -> x = 2
+   -> y = -1305113685113685114225685113708279708511
+GCDE 4567897897897897899789897897978978979789 14
+   -> g = 1
+   -> x = -5
+   -> y = 1631392106392106392782106392135349635639
+GCDE 4567897897897897899789897897978978979789 123
+   -> g = 1
+   -> x = -23
+   -> y = 854159769525623184513558143524524524676
+GCDE 4567897897897897899789897897978978979789 1230
+   -> g = 1
+   -> x = 469
+   -> y = -1741743182206596841464603344839139139448
+GCDE 4567897897897897899789897897978978979789 123456789456789456789456789456789456789465789465456789465454645789
+   -> g = 1
+   -> x = 3847449587076097018280777909186630028091235782450380442052224817
+   -> y = -142355531505412253555567593395647545708
+GCDE 4567897897897897899789897897978978979789 493827157827157827157827157827157827157863157861827157861818583156
+   -> g = 1
+   -> x = 3847449587076097018280777909186630028091235782450380442052224817
+   -> y = -35588882876353063388891898348911886427
+GCDE 4567897897897897899789897897978978979789 -1
+   -> g = 1
+   -> x = 0
+   -> y = -1
+GCDE 4567897897897897899789897897978978979789 -123
+   -> g = 1
+   -> x = -23
+   -> y = -854159769525623184513558143524524524676
+GCDE 4567897897897897899789897897978978979789 -123456789456789456789456789456789456789465789465456789465454645789
+   -> g = 1
+   -> x = 3847449587076097018280777909186630028091235782450380442052224817
+   -> y = 142355531505412253555567593395647545708
+GCDE 4567897897897897899789897897978978979789 4567897897897897899789897897978978979789
+   -> g = 4567897897897897899789897897978978979789
+   -> x = 0
+   -> y = 1
+GCDE 4567897897897897899789897897978978979789 2988348162058574136915891421498819466320163312926952423791023078876139
+   -> g = 1
+   -> x = -1015458101705415789288140664792006324531958465967800433101537202119645
+   -> y = 1552198297064637650702543759558133740654
+GCDE 4567897897897897899789897897978978979789 2351399303373464486466122544523690094744975233415544072992656881240319
+   -> g = 1
+   -> x = 683642522828502349233122722282318495240860998440822891959775694494728
+   -> y = -1328064203498637654577318574253233256089
+GCDE 4567897897897897899789897897978978979789 5328841272400314897981163497728751426
+   -> g = 1
+   -> x = 729028905639966888803280268153493563
+   -> y = -624925651816157654399317122483041604031
+GCDE 4567897897897897899789897897978978979789 32052182750761975518649228050096851724
+   -> g = 1
+   -> x = -12910967943414004413956938074429250463
+   -> y = 1839998972523827338782593728961148005767
+GCDE 2988348162058574136915891421498819466320163312926952423791023078876139 0
+   -> g = 2988348162058574136915891421498819466320163312926952423791023078876139
+   -> x = 1
+   -> y = 0
+GCDE 2988348162058574136915891421498819466320163312926952423791023078876139 1
+   -> g = 1
+   -> x = 0
+   -> y = 1
+GCDE 2988348162058574136915891421498819466320163312926952423791023078876139 7
+   -> g = 1
+   -> x = -3
+   -> y = 1280720640882246058678239180642351199851498562682979610196152748089774
+GCDE 2988348162058574136915891421498819466320163312926952423791023078876139 14
+   -> g = 1
+   -> x = -3
+   -> y = 640360320441123029339119590321175599925749281341489805098076374044887
+GCDE 2988348162058574136915891421498819466320163312926952423791023078876139 123
+   -> g = 1
+   -> x = -56
+   -> y = 1360548756709594729002357069950682033446578418893571835221929206642795
+GCDE 2988348162058574136915891421498819466320163312926952423791023078876139 1230
+   -> g = 1
+   -> x = 559
+   -> y = -1358119205358327595557710003754341529815423814574119028373318618773790
+GCDE 2988348162058574136915891421498819466320163312926952423791023078876139 123456789456789456789456789456789456789465789465456789465454645789
+   -> g = 1
+   -> x = -20718328076357217180814970215022985846592184263422313201087532586
+   -> y = 501499981494162622976489092493961483514126808861435716131179868189595
+GCDE 2988348162058574136915891421498819466320163312926952423791023078876139 493827157827157827157827157827157827157863157861827157861818583156
+   -> g = 1
+   -> x = 102738461380432239608641819241766470942873605202034476264367113203
+   -> y = -621712045141102878484850582251214495701509126016379176914960802671636
+GCDE 2988348162058574136915891421498819466320163312926952423791023078876139 -1
+   -> g = 1
+   -> x = 0
+   -> y = -1
+GCDE 2988348162058574136915891421498819466320163312926952423791023078876139 -123
+   -> g = 1
+   -> x = -56
+   -> y = -1360548756709594729002357069950682033446578418893571835221929206642795
+GCDE 2988348162058574136915891421498819466320163312926952423791023078876139 -123456789456789456789456789456789456789465789465456789465454645789
+   -> g = 1
+   -> x = -20718328076357217180814970215022985846592184263422313201087532586
+   -> y = -501499981494162622976489092493961483514126808861435716131179868189595
+GCDE 2988348162058574136915891421498819466320163312926952423791023078876139 4567897897897897899789897897978978979789
+   -> g = 1
+   -> x = 1552198297064637650702543759558133740654
+   -> y = -1015458101705415789288140664792006324531958465967800433101537202119645
+GCDE 2988348162058574136915891421498819466320163312926952423791023078876139 2988348162058574136915891421498819466320163312926952423791023078876139
+   -> g = 2988348162058574136915891421498819466320163312926952423791023078876139
+   -> x = 0
+   -> y = 1
+GCDE 2988348162058574136915891421498819466320163312926952423791023078876139 2351399303373464486466122544523690094744975233415544072992656881240319
+   -> g = 1
+   -> x = -238164827888328100873319793437342927637138278785737103723156342382925
+   -> y = 302679100340807588460107986194035692812415103244388831792688023418704
+GCDE 2988348162058574136915891421498819466320163312926952423791023078876139 5328841272400314897981163497728751426
+   -> g = 1
+   -> x = 88969837841661133174308363831195241
+   -> y = -49893182739334638874406212208356173614356037934509167748717979955473
+GCDE 2988348162058574136915891421498819466320163312926952423791023078876139 32052182750761975518649228050096851724
+   -> g = 1
+   -> x = -2926808101621088968857550652617123241
+   -> y = 272877565911469778893036529750941765793334087149670477404511983087875
+GCDE 2351399303373464486466122544523690094744975233415544072992656881240319 0
+   -> g = 2351399303373464486466122544523690094744975233415544072992656881240319
+   -> x = 1
+   -> y = 0
+GCDE 2351399303373464486466122544523690094744975233415544072992656881240319 1
+   -> g = 1
+   -> x = 0
+   -> y = 1
+GCDE 2351399303373464486466122544523690094744975233415544072992656881240319 7
+   -> g = 1
+   -> x = 2
+   -> y = -671828372392418424704606441292482884212850066690155449426473394640091
+GCDE 2351399303373464486466122544523690094744975233415544072992656881240319 14
+   -> g = 1
+   -> x = -5
+   -> y = 839785465490523030880758051615603605266062583362694311783091743300114
+GCDE 2351399303373464486466122544523690094744975233415544072992656881240319 123
+   -> g = 1
+   -> x = 58
+   -> y = -1108789915411877562723862663271333540611451736082126473443691862698687
+GCDE 2351399303373464486466122544523690094744975233415544072992656881240319 1230
+   -> g = 1
+   -> x = -311
+   -> y = 594540799470851589667450497029973674362347396416450574553427878102227
+GCDE 2351399303373464486466122544523690094744975233415544072992656881240319 123456789456789456789456789456789456789465789465456789465454645789
+   -> g = 1
+   -> x = -31922158162609726789179865549911873484290325403318594248193251952
+   -> y = 608000101055682152473830041965606704242079033852469328931798308452101
+GCDE 2351399303373464486466122544523690094744975233415544072992656881240319 493827157827157827157827157827157827157863157861827157861818583156
+   -> g = 1
+   -> x = -155378947619399183578636655006701330273756114868775383713647897741
+   -> y = 739849851107286659734988146622324199746763566817003350481113797423105
+GCDE 2351399303373464486466122544523690094744975233415544072992656881240319 -1
+   -> g = 1
+   -> x = 0
+   -> y = -1
+GCDE 2351399303373464486466122544523690094744975233415544072992656881240319 -123
+   -> g = 1
+   -> x = 58
+   -> y = 1108789915411877562723862663271333540611451736082126473443691862698687
+GCDE 2351399303373464486466122544523690094744975233415544072992656881240319 -123456789456789456789456789456789456789465789465456789465454645789
+   -> g = 1
+   -> x = -31922158162609726789179865549911873484290325403318594248193251952
+   -> y = -608000101055682152473830041965606704242079033852469328931798308452101
+GCDE 2351399303373464486466122544523690094744975233415544072992656881240319 4567897897897897899789897897978978979789
+   -> g = 1
+   -> x = -1328064203498637654577318574253233256089
+   -> y = 683642522828502349233122722282318495240860998440822891959775694494728
+GCDE 2351399303373464486466122544523690094744975233415544072992656881240319 2988348162058574136915891421498819466320163312926952423791023078876139
+   -> g = 1
+   -> x = 302679100340807588460107986194035692812415103244388831792688023418704
+   -> y = -238164827888328100873319793437342927637138278785737103723156342382925
+GCDE 2351399303373464486466122544523690094744975233415544072992656881240319 2351399303373464486466122544523690094744975233415544072992656881240319
+   -> g = 2351399303373464486466122544523690094744975233415544072992656881240319
+   -> x = 0
+   -> y = 1
+GCDE 2351399303373464486466122544523690094744975233415544072992656881240319 5328841272400314897981163497728751426
+   -> g = 1
+   -> x = 1320061761887019753142991170712833225
+   -> y = -582489165775607532361449347744188527071103823360367325716372563952699
+GCDE 2351399303373464486466122544523690094744975233415544072992656881240319 32052182750761975518649228050096851724
+   -> g = 1
+   -> x = -3459287250911140032199362006422486237
+   -> y = 253778836069059554551347740010931350716760250644753514181097821250371
+GCDE 5328841272400314897981163497728751426 0
+   -> g = 5328841272400314897981163497728751426
+   -> x = 1
+   -> y = 0
+GCDE 5328841272400314897981163497728751426 1
+   -> g = 1
+   -> x = 0
+   -> y = 1
+GCDE 5328841272400314897981163497728751426 7
+   -> g = 1
+   -> x = -3
+   -> y = 2283789116742992099134784356169464897
+GCDE 5328841272400314897981163497728751426 14
+   -> g = 2
+   -> x = 1
+   -> y = -380631519457165349855797392694910816
+GCDE 5328841272400314897981163497728751426 123
+   -> g = 3
+   -> x = -14
+   -> y = 606534778972393565623872268034166829
+GCDE 5328841272400314897981163497728751426 1230
+   -> g = 6
+   -> x = -69
+   -> y = 298934998207822543057479903531125080
+GCDE 5328841272400314897981163497728751426 123456789456789456789456789456789456789465789465456789465454645789
+   -> g = 1
+   -> x = 5417322661629453658993420651614628087475941267504880682551205239
+   -> y = -233831227202814412604649442847121617
+GCDE 5328841272400314897981163497728751426 493827157827157827157827157827157827157863157861827157861818583156
+   -> g = 2
+   -> x = -112622144133530549471469948153560200614513906930447028100352235311
+   -> y = 1215294704498671518192966153008627048
+GCDE 5328841272400314897981163497728751426 -1
+   -> g = 1
+   -> x = 0
+   -> y = -1
+GCDE 5328841272400314897981163497728751426 -123
+   -> g = 3
+   -> x = -14
+   -> y = -606534778972393565623872268034166829
+GCDE 5328841272400314897981163497728751426 -123456789456789456789456789456789456789465789465456789465454645789
+   -> g = 1
+   -> x = 5417322661629453658993420651614628087475941267504880682551205239
+   -> y = 233831227202814412604649442847121617
+GCDE 5328841272400314897981163497728751426 4567897897897897899789897897978978979789
+   -> g = 1
+   -> x = -624925651816157654399317122483041604031
+   -> y = 729028905639966888803280268153493563
+GCDE 5328841272400314897981163497728751426 2988348162058574136915891421498819466320163312926952423791023078876139
+   -> g = 1
+   -> x = -49893182739334638874406212208356173614356037934509167748717979955473
+   -> y = 88969837841661133174308363831195241
+GCDE 5328841272400314897981163497728751426 2351399303373464486466122544523690094744975233415544072992656881240319
+   -> g = 1
+   -> x = -582489165775607532361449347744188527071103823360367325716372563952699
+   -> y = 1320061761887019753142991170712833225
+GCDE 5328841272400314897981163497728751426 5328841272400314897981163497728751426
+   -> g = 5328841272400314897981163497728751426
+   -> x = 0
+   -> y = 1
+GCDE 5328841272400314897981163497728751426 32052182750761975518649228050096851724
+   -> g = 92889294
+   -> x = 115110207004456909698806038261
+   -> y = -19137667681784054624628973533
+GCDE 32052182750761975518649228050096851724 0
+   -> g = 32052182750761975518649228050096851724
+   -> x = 1
+   -> y = 0
+GCDE 32052182750761975518649228050096851724 1
+   -> g = 1
+   -> x = 0
+   -> y = 1
+GCDE 32052182750761975518649228050096851724 7
+   -> g = 1
+   -> x = 3
+   -> y = -13736649750326560936563954878612936453
+GCDE 32052182750761975518649228050096851724 14
+   -> g = 2
+   -> x = -1
+   -> y = 2289441625054426822760659146435489409
+GCDE 32052182750761975518649228050096851724 123
+   -> g = 3
+   -> x = -4
+   -> y = 1042347406528844732313796034149491113
+GCDE 32052182750761975518649228050096851724 1230
+   -> g = 6
+   -> x = 74
+   -> y = -1928342702078362754780522663176558559
+GCDE 32052182750761975518649228050096851724 123456789456789456789456789456789456789465789465456789465454645789
+   -> g = 1
+   -> x = -10203432759063496909071922280945854833629276496909075027106202353
+   -> y = 2649042575281623182157985423209129457
+GCDE 32052182750761975518649228050096851724 493827157827157827157827157827157827157863157861827157861818583156
+   -> g = 4
+   -> x = -40813731036253987636287689123783419334517105987636300108424809412
+   -> y = 2649042575281623182157985423209129457
+GCDE 32052182750761975518649228050096851724 -1
+   -> g = 1
+   -> x = 0
+   -> y = -1
+GCDE 32052182750761975518649228050096851724 -123
+   -> g = 3
+   -> x = -4
+   -> y = -1042347406528844732313796034149491113
+GCDE 32052182750761975518649228050096851724 -123456789456789456789456789456789456789465789465456789465454645789
+   -> g = 1
+   -> x = -10203432759063496909071922280945854833629276496909075027106202353
+   -> y = -2649042575281623182157985423209129457
+GCDE 32052182750761975518649228050096851724 4567897897897897899789897897978978979789
+   -> g = 1
+   -> x = 1839998972523827338782593728961148005767
+   -> y = -12910967943414004413956938074429250463
+GCDE 32052182750761975518649228050096851724 2988348162058574136915891421498819466320163312926952423791023078876139
+   -> g = 1
+   -> x = 272877565911469778893036529750941765793334087149670477404511983087875
+   -> y = -2926808101621088968857550652617123241
+GCDE 32052182750761975518649228050096851724 2351399303373464486466122544523690094744975233415544072992656881240319
+   -> g = 1
+   -> x = 253778836069059554551347740010931350716760250644753514181097821250371
+   -> y = -3459287250911140032199362006422486237
+GCDE 32052182750761975518649228050096851724 5328841272400314897981163497728751426
+   -> g = 92889294
+   -> x = -19137667681784054624628973533
+   -> y = 115110207004456909698806038261
+GCDE 32052182750761975518649228050096851724 32052182750761975518649228050096851724
+   -> g = 32052182750761975518649228050096851724
+   -> x = 0
+   -> y = 1
+GCDE 2 36893488147419103233
+   -> g = 1
+   -> x = -18446744073709551616
+   -> y = 1
+GCDE 2 -36893488147419103233
+   -> g = 1
+   -> x = -18446744073709551616
+   -> y = -1
+GCDE -2 36893488147419103233
+   -> g = 1
+   -> x = 18446744073709551616
+   -> y = 1
+GCDE -2 -36893488147419103233
+   -> g = 1
+   -> x = 18446744073709551616
+   -> y = -1
+GCDE 36893488147419103233 2
+   -> g = 1
+   -> x = 1
+   -> y = -18446744073709551616
+GCDE 36893488147419103233 -2
+   -> g = 1
+   -> x = 1
+   -> y = 18446744073709551616
+GCDE -36893488147419103233 2
+   -> g = 1
+   -> x = -1
+   -> y = -18446744073709551616
+GCDE -36893488147419103233 -2
+   -> g = 1
+   -> x = -1
+   -> y = 18446744073709551616
diff --git a/testsuite/tests/lib/integer/integerGcdExt.hs b/testsuite/tests/lib/integer/integerGcdExt.hs
index d060c2d3b2..2457b1ced2 100644
--- a/testsuite/tests/lib/integer/integerGcdExt.hs
+++ b/testsuite/tests/lib/integer/integerGcdExt.hs
@@ -9,10 +9,10 @@ import Control.Monad
 
 import GHC.Word
 import GHC.Base
-import qualified GHC.Integer.GMP.Internals as I
+import qualified GHC.Num.Integer as I
 
 gcdExtInteger :: Integer -> Integer -> (Integer, Integer)
-gcdExtInteger a b = case I.gcdExtInteger a b of (# g, s #) -> (g, s)
+gcdExtInteger a b = case I.integerGcde a b of ( g, s, _t ) -> (g, s)
 
 main :: IO ()
 main = do