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