Home Search   What's New Index Books Links Q & A Newsletter Banners   Feedback Tip Jar MSDN Visual Basic Community

Title Compute the greatest common divisor, least common multiple, and Bezout equality of two numbers LCM, GCD, Bezout, least common multiple, greatest common divisor Algorithms

By Patrice Goyer.

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```