Compute the greatest common divisor D and the least common multiple M of two numbers A and B, and show the "Bezout equality" expressing D as a linear combination of A and B.

Use Euclid's algorithm, recording at each step, into a 2 x 2 matrix, the results needed later.

' COMPUTE THE GCD AND LCM OF TWO NUMBERS
' TOGETHER WITH A BEZOUT EQUALITY

' The rationale is to use the Euclides algorithm
' and to memorize the results in a 2x2 Matrix Dn
' such that
'    a            Rn-1
'          = Dn .
'    b            Rn-2
'
' if Rn = Qn x Rn-1  + Rn+1
' then Dn+1 = Dn . Q  , where
'
'                 Qn      1
'    Q     =
'                 1       0
' (Qo being the identity matrix)
'
' For performance reasons the matrix D is kept in variables
' d1 through d4

Const computeCaption As String = "&Compute GCD(a,b)," & _
    vbCr _
    & "LCM(a,b) and" & vbCr _
    & "Bezout relationship"
Const newValCaption = "Enter &new" & vbCr & "values"

' the numbers whose GDC and LCM are wanted
Dim A As Long, B As Long

' the matrix and temp storage variables
Dim d1 As Long, d2 As Long, d3 As Long, d4 As Long
Dim dPrim1 As Long, dPrim3 As Long
Dim det As Long ' determinant of D

' the inverse of matrix D
Dim b1 As Long, b2 As Long
' Dim b3 As Long, b4 As Long

' the variables for Euclides algorithm
Dim X As Long, Y As Long, Q As Long, R As Long
Dim LCM As Double

' miscellaneous
Dim sizW As Long, sizH As Long
Const minMargin As Long = 200
Const timerTick As Long = 1000 ' 5 seconds

Private Sub cmdCompute_Click()
If cmdCompute.Caption = computeCaption Then
  If txtA.Text = "" Then
    txtA.SetFocus: Exit Sub
  Else
    If txtB.Text = "" Then txtB.SetFocus: Exit Sub
  End If
' compute GCD, etc.
  txtA.Enabled = False
  txtB.Enabled = False
  If getAandB Then
    cmdCompute.Enabled = False
' initialize the matrix to Identity
    d1 = 1: d2 = 0: d3 = 0: d4 = 1
' set A as larger of the numbers
    If A < B Then R = A: A = B: B = R
    X = A: Y = B: Q = 0: R = A
    txtA.Text = CStr(A)
    txtB.Text = CStr(B)
    det = 1
' Euclides algorithm is just in the 6 lines below !
    Do While R <> 0
      euclDiv
      multMat
      X = Y
      Y = R
    Loop
' Here we've got (A,B) = D . (X,0) and X = GCD (A,B)
' and A = d1 * X  ,  B = d3 * X  ,  LCM(A,B) = d1 * d3 * X

' we inverse the matrix (just as much as necessary)
' to get a Bezout relationship
    invMat
    lblResult.Caption = "GCD(" & CStr(A) & "," & CStr(B) & _
        ") = " & CStr(X) & vbCr
    If X = 1 Then
    lblResult.Caption = lblResult.Caption & _
      "(" & CStr(A) & " and " & CStr(B) & " are relatively " & _
          "prime)" & vbCr
    End If
    lblResult.Caption = lblResult.Caption & _
      CStr(A) & " = " & CStr(d1) & " * " & CStr(X) & vbCr & _
          _
      CStr(B) & " = " & CStr(d3) & " * " & CStr(X) & vbCr
' we have GCD(A,B) = X = b1 * A  +  b2 * B
' we check it if we can (using the LCM variable for
' capacity reasons)
    On Error Resume Next
    LCM = b1 * A + b2 * B
    If Err.Number = 0 Then
      If LCM <> X Then
        MsgBox "Fatal error #03 - Must quit", vbCritical, _
            "Fatal error #03 in Bezout"
        End
      End If
    End If
    Err.Clear
    LCM = d1 * d3 * X ' LCM(a,b)
    If Err.Number = 0 Then
      lblResult.Caption = lblResult.Caption & vbCr & _
        "LCM(" & CStr(A) & "," & CStr(B) & ") = " & _
            CStr(LCM) & vbCr & _
        CStr(LCM) & " = " & CStr(A) & " * " & CStr(d3) & _
            vbCr & _
        CStr(LCM) & " = " & CStr(B) & " * " & CStr(d1)
    Else
      lblResult.Caption = lblResult.Caption & vbCr & _
        "LCM(" & CStr(A) & "," & CStr(B) & ") = " & CStr(A) _
            & " * " & CStr(d3) & vbCr & _
        "LCM(" & CStr(A) & "," & CStr(B) & ") = " & CStr(B) _
            & " * " & CStr(d1)
    End If
    Err.Clear
    On Error GoTo 0
    lblResult.Caption = lblResult.Caption & vbCr & _
      vbCr & "Bezout equality:" & vbCr & CStr(X) & " = "
    If b1 >= 0 Then
      lblResult.Caption = lblResult.Caption & CStr(b1)
    Else
      lblResult.Caption = lblResult.Caption & "(-" & _
          CStr(-b1) & ")"
    End If
    lblResult.Caption = lblResult.Caption & " * " & CStr(A) _
        & "  +  "
    If b2 >= 0 Then
      lblResult.Caption = lblResult.Caption & CStr(b2)
    Else
      lblResult.Caption = lblResult.Caption & "(-" & _
          CStr(-b2) & ")"
    End If
    lblResult.Caption = lblResult.Caption & " * " & CStr(B)
    cmdCompute.Caption = newValCaption
    cmdCompute.Enabled = True
    cmdCompute.SetFocus
  Else
    txtA.Enabled = True
    txtB.Enabled = True
  End If

' click on the "enter new value button"
ElseIf cmdCompute.Caption = newValCaption Then
  txtA.Enabled = True
  txtA.Text = ""
  txtB.Enabled = True
  txtB.Text = ""
  lblResult.Caption = ""
  cmdCompute.Caption = computeCaption
  txtA.SetFocus
Else
  MsgBox "Fatal error #01 - Must quit", vbCritical, "Fatal " & _
      "error #01 in Bezout"
  End
End If
End Sub

' inversion of matrix D
Private Sub invMat()
' the determinant of D must be 1 or -1
' as D is a product of matrices whose determinant is -1
' det = (d1 * d4) - (d2 * d3) has already been computed
If (det = 1) Or (det = -1) Then
  b1 = d4 * det
  b2 = (-d2) * det
' we only need b1 and b2
'  b3 = (-d3) / det
'  b4 = d1 / det
Else
  MsgBox "Fatal error #02 - Must quit", vbCritical, "Fatal " & _
      "error #02 in Bezout"
  End
End If
End Sub