hp41programs

Bezout

GCD , LCM and Bezout's Identity for the HP-41


Overview
 

 1°)  Greatest Common Divisor & Lowest Common Multiple
 2°)  Bezout's Identity
 
 

1°)  Greatest Common Divisor & Lowest Common Multiple
 

-This routine computes GCD(a,b) & LCM(a,b)  and  calculates  a' = a/GCD(a,b)  & b' = b/GCD(a,b)
-Thus,  a'/b' = a/b  and  a'/b'  is irreductible.
-The Euclidean algorithm is used.
 

Data Registers: /
Flags: /
Subroutines: /
 
 

 01  LBL "GCD"
 02  RCL Y
 03  RCL Y
 04  LBL 01
 05  MOD
 06  LASTX
 07  X<>Y
 08  X#0?
 09  GTO 01
 10  +
 11  ST/ T
 12  /
 13  ST* Y
 14  X<>Y
 15  LASTX
 16  END

 
 ( 29 bytes / SIZE 000 )
 
 

      STACK        INPUTS      OUTPUTS
           T             /    a'= a/gcd(a,b)
           Z             /    b'= b/gcd(a,b)
           Y             a        lcm(a,b)
           X             b        gcd(a,b)
           L             /        gcd(a,b)

 
Example:

  950796  ENTER^
  107016  XEQ "GCD"  >>>>  GCD(950796,107016) =   4116
                                      RDN   LCM(950796,107016) = 24720696
                                      RDN       b' = 26
                                      RDN       a' = 231

-Thus,   950796/107016 = 231/26
 

2°)  Bezout's Identity
 

-The equation  a u + b v = c   where  a , b , c  are known integers and u , v are 2 unknowns
  has integer solutions iff c is a multiple of GCD(a,b)
-"UV" computes 2 numbers u & v that satisfy this equation.
-GCD(a,b) is also returned in Z-register & T-register.

-The extended Euclidean algorithm is used:  let  a0 = a  &  a1 = b , we perform the successive Euclidean divisions

    a0 = a1 q1 + a2                     and we                u0 = 1  ,  u1 = 0  ,  uk+1 = uk-1 - qk uk
    a1 = a2 q2 + a3                      define                 v0 = 0  ,  v1 = 1  ,  vk+1 = vk-1 - qk vk
    ......................

  ak-1 = ak qk + ak+1
   .......................

  an-1 = an qn + 0                      it yields                   an = gcd(a,b)        u = c un/ an         v = c vn/ an
 
 

Data Registers:      R00 thru R04: temp           When the program stops,   R02 = -b & R04 = a  or   R02 = b & R04 = -a
Flags: /
Subroutines: /
 
 

01  LBL "UV"
02  STO 00   
03  CLX
04  STO 02
05  STO 03
06  1
07  STO 01
08  STO 04		 09  *
10  +
11  LBL 01   
12  STO T
13  MOD
14  ST- Y
15  X<> Z
16  /		 17  RCL 01
18  X<> 02
19  STO 01   
20  X<>Y
21  *
22  ST- 02
23  CLX
24  RCL 03		 25  X<> 04
26  STO 03
27  LASTX   
28  *
29  ST- 04
30  RDN
31  X#0?
32  GTO 01		 33  X<>Y
34  ST/ 00
35  RCL 03   
36  RCL 01
37  RCL 00
38  ST* Z
39  *
40  END

 
    ( 57 bytes / SIZE 005 )
 
 

      STACK        INPUTS      OUTPUTS
           Z             a         gcd(a,b)
           Y             b             v
           X             c             u

 
Example:

  125  ENTER^
   41   ENTER^
    1    XEQ "UV"  >>>>       u = -20                            -20x125 + 61x41 = 1
                             RDN        v =  61
                             RDN   gcd(125,41) = 1

-If c is not a multiple of gcd(a,b)  u and v are not integers.
-When c = gcd(a,b)  , u and v are minimal solutions. Otherwise, they are not!

-For instance, with  a = 125 , b = 41 , c = 7   "UV" gives  u = -140 & v = 427

Note:

-If you want to get minimal solutions,
  add   STO 01  RCL 02  MOD  ENTER^  X<> 01  -  RCL 02  /  RCL 04  *  +  RCL 01   after line 39

-Now,

   125  ENTER^
    41   ENTER^
     7    XEQ "UV"  yields  u = 24   RDN  v = -73  ( and RDN still gives gcd(125,41) = 1 )

-So,        24x125-73x41 = 7