LLL based extended GCD algorithm in action: gcd(116085838,181081878,314252913,10346840)

This is verbose output from lllgcd() in CALC.

alpha = 1 

1 0 0 0 116085838
0 1 0 0 181081878
0 0 1 0 314252913
0 0 0 1  10346840

Row 2 -> Row 2 + -2 x Row 1 
 1 0 0 0 116085838  
-2 1 0 0 -51089798  
 0 0 1 0 314252913  
 0 0 0 1  10346840  

Swapping Rows 1 and 2 
-2 1 0 0 -51089798  
 1 0 0 0 116085838  
 0 0 1 0 314252913  
 0 0 0 1  10346840  

Row 2 -> Row 2 + 2 x Row 1 
-2 1 0 0 -51089798  
-3 2 0 0  13906242  
 0 0 1 0 314252913  
 0 0 0 1  10346840  

Swapping Rows 1 and 2 
-3 2 0 0  13906242  
-2 1 0 0 -51089798  
 0 0 1 0 314252913  
 0 0 0 1  10346840  

Row 2 -> Row 2 + 4 x Row 1 
 -3 2 0 0  13906242  
-14 9 0 0   4535170  
  0 0 1 0 314252913  
  0 0 0 1  10346840  

Swapping Rows 1 and 2 
-14 9 0 0   4535170  
 -3 2 0 0  13906242  
  0 0 1 0 314252913  
  0 0 0 1  10346840  

Row 2 -> Row 2 + -3 x Row 1 
-14   9 0 0   4535170  
 39 -25 0 0    300732  
  0   0 1 0 314252913  
  0   0 0 1  10346840  

Swapping Rows 1 and 2 
 39 -25 0 0    300732  
-14   9 0 0   4535170  
  0   0 1 0 314252913  
  0   0 0 1  10346840  

Row 2 -> Row 2 + -15 x Row 1 
  39 -25 0 0    300732  
-599 384 0 0     24190  
   0   0 1 0 314252913  
   0   0 0 1  10346840  

Swapping Rows 1 and 2 
-599 384 0 0     24190  
  39 -25 0 0    300732  
   0   0 1 0 314252913  
   0   0 0 1  10346840  

Row 2 -> Row 2 + -12 x Row 1 
-599   384 0 0     24190  
7227 -4633 0 0     10452  
   0     0 1 0 314252913  
   0     0 0 1  10346840  

Swapping Rows 1 and 2 
7227 -4633 0 0     10452  
-599   384 0 0     24190  
   0     0 1 0 314252913  
   0     0 0 1  10346840  

Row 2 -> Row 2 + -2 x Row 1 
  7227 -4633 0 0     10452  
-15053  9650 0 0      3286  
     0     0 1 0 314252913  
     0     0 0 1  10346840  

Swapping Rows 1 and 2 
-15053  9650 0 0      3286  
  7227 -4633 0 0     10452  
     0     0 1 0 314252913  
     0     0 0 1  10346840  

Row 2 -> Row 2 + -3 x Row 1 
-15053   9650 0 0      3286  
 52386 -33583 0 0       594  
     0      0 1 0 314252913  
     0      0 0 1  10346840  

Swapping Rows 1 and 2 
 52386 -33583 0 0       594  
-15053   9650 0 0      3286  
     0      0 1 0 314252913  
     0      0 0 1  10346840  

Row 2 -> Row 2 + -6 x Row 1 
  52386 -33583 0 0       594  
-329369 211148 0 0      -278  
      0      0 1 0 314252913  
      0      0 0 1  10346840  

Swapping Rows 1 and 2 
-329369 211148 0 0      -278  
  52386 -33583 0 0       594  
      0      0 1 0 314252913  
      0      0 0 1  10346840  

Row 2 -> Row 2 + 2 x Row 1 
-329369 211148 0 0      -278  
-606352 388713 0 0        38  
      0      0 1 0 314252913  
      0      0 0 1  10346840  

Swapping Rows 1 and 2 
-606352 388713 0 0        38  
-329369 211148 0 0      -278  
      0      0 1 0 314252913  
      0      0 0 1  10346840  

Row 2 -> Row 2 + 7 x Row 1 
 -606352  388713 0 0        38  
-4573833 2932139 0 0       -12  
       0       0 1 0 314252913  
       0       0 0 1  10346840  

Swapping Rows 1 and 2 
-4573833 2932139 0 0       -12  
 -606352  388713 0 0        38  
       0       0 1 0 314252913  
       0       0 0 1  10346840  

Row 2 -> Row 2 + 3 x Row 1 
 -4573833 2932139 0 0       -12  
-14327851 9185130 0 0         2  
        0       0 1 0 314252913  
        0       0 0 1  10346840  

Swapping Rows 1 and 2 
-14327851 9185130 0 0         2  
 -4573833 2932139 0 0       -12  
        0       0 1 0 314252913  
        0       0 0 1  10346840  

Row 2 -> Row 2 + 6 x Row 1 
-14327851  9185130 0 0         2  
-90540939 58042919 0 0         0  
        0        0 1 0 314252913  
        0        0 0 1  10346840  

Swapping Rows 1 and 2 
-90540939 58042919 0 0         0  
-14327851  9185130 0 0         2  
        0        0 1 0 314252913  
        0        0 0 1  10346840  

Row 3 -> Row 3 + -157126456 x Row 2 
       -90540939          58042919 0 0        0  
       -14327851           9185130 0 0        2  
2251284449726056 -1443226924799280 1 0        1  
               0                 0 0 1 10346840  

Swapping Rows 2 and 3 
       -90540939          58042919 0 0        0  
2251284449726056 -1443226924799280 1 0        1  
       -14327851           9185130 0 0        2  
               0                 0 0 1 10346840  

Row 2 -> Row 2 + 24864823 x Row 1 
-90540939  58042919 0 0        0  
 27237259 -17460943 1 0        1  
-14327851   9185130 0 0        2  
        0         0 0 1 10346840  

Row 3 -> Row 3 + -2 x Row 2 
-90540939  58042919  0 0        0  
 27237259 -17460943  1 0        1  
-68802369  44107016 -2 0        0  
        0         0  0 1 10346840  

Swapping Rows 2 and 3 
-90540939  58042919  0 0        0  
-68802369  44107016 -2 0        0  
 27237259 -17460943  1 0        1  
        0         0  0 1 10346840  

Row 2 -> Row 2 + -1 x Row 1 
-90540939  58042919  0 0        0  
 21738570 -13935903 -2 0        0  
 27237259 -17460943  1 0        1  
        0         0  0 1 10346840  

Swapping Rows 1 and 2 
 21738570 -13935903 -2 0        0  
-90540939  58042919  0 0        0  
 27237259 -17460943  1 0        1  
        0         0  0 1 10346840  

Row 2 -> Row 2 + 4 x Row 1 
21738570 -13935903 -2 0        0  
-3586659   2299307 -8 0        0  
27237259 -17460943  1 0        1  
       0         0  0 1 10346840  

Swapping Rows 1 and 2 
-3586659   2299307 -8 0        0  
21738570 -13935903 -2 0        0  
27237259 -17460943  1 0        1  
       0         0  0 1 10346840  

Row 2 -> Row 2 + 6 x Row 1 
-3586659   2299307  -8 0        0  
  218616   -140061 -50 0        0  
27237259 -17460943   1 0        1  
       0         0   0 1 10346840  

Swapping Rows 1 and 2 
  218616   -140061 -50 0        0  
-3586659   2299307  -8 0        0  
27237259 -17460943   1 0        1  
       0         0   0 1 10346840  

Row 2 -> Row 2 + 16 x Row 1 
  218616   -140061  -50 0        0  
  -88803     58331 -808 0        0  
27237259 -17460943    1 0        1  
       0         0    0 1 10346840  

Swapping Rows 1 and 2 
  -88803     58331 -808 0        0  
  218616   -140061  -50 0        0  
27237259 -17460943    1 0        1  
       0         0    0 1 10346840  

Row 2 -> Row 2 + 2 x Row 1 
  -88803     58331  -808 0        0  
   41010    -23399 -1666 0        0  
27237259 -17460943     1 0        1  
       0         0     0 1 10346840  

Swapping Rows 1 and 2 
   41010    -23399 -1666 0        0  
  -88803     58331  -808 0        0  
27237259 -17460943     1 0        1  
       0         0     0 1 10346840  

Row 2 -> Row 2 + 2 x Row 1 
   41010    -23399 -1666 0        0  
   -6783     11533 -4140 0        0  
27237259 -17460943     1 0        1  
       0         0     0 1 10346840  

Swapping Rows 1 and 2 
   -6783     11533 -4140 0        0  
   41010    -23399 -1666 0        0  
27237259 -17460943     1 0        1  
       0         0     0 1 10346840  

Row 2 -> Row 2 + 3 x Row 1 
   -6783     11533  -4140 0        0  
   20661     11200 -14086 0        0  
27237259 -17460943      1 0        1  
       0         0      0 1 10346840  

Row 3 -> Row 3 + -623 x Row 2 
   -6783     11533   -4140 0        0  
   20661     11200  -14086 0        0  
14365456 -24438543 8775579 0        1  
       0         0       0 1 10346840  

Row 3 -> Row 3 + 2119 x Row 1 
-6783 11533  -4140 0        0  
20661 11200 -14086 0        0  
-7721  -116   2919 0        1  
    0     0      0 1 10346840  

Row 4 -> Row 4 + -10346840 x Row 3 
      -6783      11533        -4140 0 0  
      20661      11200       -14086 0 0  
      -7721       -116         2919 0 1  
79887951640 1200233440 -30202425960 1 0  

Swapping Rows 3 and 4 
      -6783      11533        -4140 0 0  
      20661      11200       -14086 0 0  
79887951640 1200233440 -30202425960 1 0  
      -7721       -116         2919 0 1  

Row 3 -> Row 3 + -2957773 x Row 2 
      -6783        11533       -4140 0 0  
      20661        11200      -14086 0 0  
18777403687 -31926824160 11460764518 1 0  
      -7721         -116        2919 0 1  

Swapping Rows 2 and 3 
      -6783        11533       -4140 0 0  
18777403687 -31926824160 11460764518 1 0  
      20661        11200      -14086 0 0  
      -7721         -116        2919 0 1  

Row 2 -> Row 2 + 2768302 x Row 1 
-6783 11533  -4140 0 0  
11221  2806  -5762 1 0  
20661 11200 -14086 0 0  
-7721  -116   2919 0 1  

Swapping Rows 1 and 2 
11221  2806  -5762 1 0  
-6783 11533  -4140 0 0  
20661 11200 -14086 0 0  
-7721  -116   2919 0 1  

Swapping Rows 2 and 3 
11221  2806  -5762 1 0  
20661 11200 -14086 0 0  
-6783 11533  -4140 0 0  
-7721  -116   2919 0 1  

Row 2 -> Row 2 + -2 x Row 1 
11221  2806 -5762  1 0  
-1781  5588 -2562 -2 0  
-6783 11533 -4140  0 0  
-7721  -116  2919  0 1  

Swapping Rows 1 and 2 
-1781  5588 -2562 -2 0  
11221  2806 -5762  1 0  
-6783 11533 -4140  0 0  
-7721  -116  2919  0 1  

Swapping Rows 2 and 3 
-1781  5588 -2562 -2 0  
-6783 11533 -4140  0 0  
11221  2806 -5762  1 0  
-7721  -116  2919  0 1  

Row 2 -> Row 2 + -2 x Row 1 
-1781 5588 -2562 -2 0  
-3221  357   984  4 0  
11221 2806 -5762  1 0  
-7721 -116  2919  0 1  

Swapping Rows 1 and 2 
-3221  357   984  4 0  
-1781 5588 -2562 -2 0  
11221 2806 -5762  1 0  
-7721 -116  2919  0 1  

Row 3 -> Row 3 + -1 x Row 2 
-3221   357   984  4 0  
-1781  5588 -2562 -2 0  
13002 -2782 -3200  3 0  
-7721  -116  2919  0 1  

Swapping Rows 2 and 3 
-3221   357   984  4 0  
13002 -2782 -3200  3 0  
-1781  5588 -2562 -2 0  
-7721  -116  2919  0 1  

Row 2 -> Row 2 + 4 x Row 1 
-3221   357   984  4 0  
  118 -1354   736 19 0  
-1781  5588 -2562 -2 0  
-7721  -116  2919  0 1  

Swapping Rows 1 and 2 
  118 -1354   736 19 0  
-3221   357   984  4 0  
-1781  5588 -2562 -2 0  
-7721  -116  2919  0 1  

Swapping Rows 2 and 3 
  118 -1354   736 19 0  
-1781  5588 -2562 -2 0  
-3221   357   984  4 0  
-7721  -116  2919  0 1  

Row 2 -> Row 2 + 4 x Row 1 
  118 -1354  736 19 0  
-1309   172  382 74 0  
-3221   357  984  4 0  
-7721  -116 2919  0 1  

Swapping Rows 1 and 2 
-1309   172  382 74 0  
  118 -1354  736 19 0  
-3221   357  984  4 0  
-7721  -116 2919  0 1  

Swapping Rows 2 and 3 
-1309   172  382 74 0  
-3221   357  984  4 0  
  118 -1354  736 19 0  
-7721  -116 2919  0 1  

Row 2 -> Row 2 + -2 x Row 1 
-1309   172  382   74 0  
 -603    13  220 -144 0  
  118 -1354  736   19 0  
-7721  -116 2919    0 1  

Swapping Rows 1 and 2 
 -603    13  220 -144 0  
-1309   172  382   74 0  
  118 -1354  736   19 0  
-7721  -116 2919    0 1  

Row 2 -> Row 2 + -2 x Row 1 
 -603    13  220 -144 0  
 -103   146  -58  362 0  
  118 -1354  736   19 0  
-7721  -116 2919    0 1  

Swapping Rows 1 and 2 
 -103   146  -58  362 0  
 -603    13  220 -144 0  
  118 -1354  736   19 0  
-7721  -116 2919    0 1  

Row 3 -> Row 3 + 1 x Row 1 
 -103   146  -58  362 0  
 -603    13  220 -144 0  
   15 -1208  678  381 0  
-7721  -116 2919    0 1  

Row 4 -> Row 4 + -1 x Row 3 
 -103   146  -58  362 0  
 -603    13  220 -144 0  
   15 -1208  678  381 0  
-7736  1092 2241 -381 1  

Row 4 -> Row 4 + -12 x Row 2 
-103   146  -58  362 0  
-603    13  220 -144 0  
  15 -1208  678  381 0  
-500   936 -399 1347 1  

Row 4 -> Row 4 + -4 x Row 1 
-103   146  -58  362 0  
-603    13  220 -144 0  
  15 -1208  678  381 0  
 -88   352 -167 -101 1  

The unimodular matrix found by LLL is 

-103   146  -58  362  
-603    13  220 -144  
  15 -1208  678  381  
 -88   352 -167 -101  

gcd(116085838,181081878,314252913,10346840)=1

The multipliers found by LLL are (-88,352,-167,-101)  

The Euclidean norm squared = 169738 

These are the smallest multipliers.

Back to LLLGCD examples page