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  a₀ = a  &  a₁ = b , we perform the successive Euclidean divisions

    a₀ = a₁ q₁ + a₂                     and we                u₀ = 1  ,  u₁ = 0  ,  u_k+1 = u_k-1 - q_k u_k
    a₁ = a₂ q₂ + a₃                      define                 v₀ = 0  ,  v₁ = 1  ,  v_k+1 = v_k-1 - q_k v_k
    ......................

  a_k-1 = a_k q_k + a_k+1
   .......................

  a_n-1 = a_n q_n + 0                      it yields                   a_n = gcd(a,b)        u = c u_n/ a_n         v = c v_n/ a_n
 
 

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