site logo
TI-89 Programs: Number Theory
horizontal bar
Functions
  • Prime factorization of x in [l,u]
  • Fibonacci
  • GCD (iterative)
  • GCD (recursive)
  • Euclidean algorithm
  • Inverse mod n
  • Nearest smaller odd integer
Prime factorization of x in [l,u]
primes(l,u)
Prgm
@lower,upper
ClrIO
Local t
If l>u Then
 u→t
 l→u
 t→l
EndIf
newMat(u-l+1,1)→r
1→i
While i≤u
 string(factor(i))→r[i-l+1,1]
 i+1→i
EndWhile
Pause r
EndPrgm
Fibonacci
fib(i)
Func
If i<3 Then
 Return 1
Else
 Return fib(i-1)+fib(i-2)
EndIf
EndFunc
GCD (iterative)
xgcd(a,b)
Func
@int a, int b
Local flip,c,m
o→flip
If a=0 and b=0 Then
 Return 0
EndIf
If a<b Then
 1→flip
 a→c
 b→a
 c→b
EndIf
identity(2)→m
[[a,b]]→c
While dotP(m[2],c)>0
 [[0,1][1,-intDiv(dotP(
m[1],c),dotP(m[2],c))]]*m→m
EndWhile
If flip=1 Then
 (rowSwap(cT,1,2))T→c
 (rowSwap(mT,1,2))T→m
EndIf
Return augment([[dotP(
m[1],c)]],m[1])
EndFunc
GCD (recursive)
gcde(a,b)
Func
@a,b
Local temp
abs(a)→a
abs(b)→b
If a=0 and b=0 Then
 Return 0
EndIf
If a>b Then
 b→temp
 a→b
 temp→a
EndIf
If mod(b,a)=0 Then
 Return a
Else
 Return gcde(a,mod(b,a))
EndIf
EndFunc
Euclidean algorithm
euclidxy(a,b,x,y)
Prgm
@a,b,x,y
@ax+by=(a,b)
ClrIO
Local g,bp,ap,temp,as,bs
Disp "a= "&string(a)
Disp "b= "&string(b)
gcd(a,b)→g
sign(a)→as
sign(b)→bs
abs(a)→a
abs(b)→b
If a=0 and b=0 Then
 Disp 0
 Stop
EndIf
x→ap
y→bp
1→i
While i<25 and mod(bp|x=a and y=b,ap|x=a and y=b)≠0
 bp→temp
 ap→bp
 temp-intDiv(temp|x=a and y=b,ap|x=a and y=b)*ap→ap
i+1→i
EndWhile
If i=25 Then
 Disp "Algorthm overflow"
EndIf
ap→temp
Disp "gcd= "&string(g)
Disp "m= "&string(-as*a/
(bs*b))
Disp "x= "&string(as*temp|x=1 and y=0)&"+"&string(b/g)&"k"
Disp "y= "&string(bs*temp|x=0 and y=1)&"+"&string(-1*as*bs*
a/g)&"k"
EndPrgm
Inverse mod n
invmod(a,n)
Func
@int a, modulus n
Local v
main\xgcd(a,n)→v
If v[1,1]=1 Then
 Return mod(v[1,2],n)
Else
 Return 0
EndIf
EndFunc
Nearest smaller odd integer
odd(n)
Func
If mod(int(n),2)=0 Then
 Return int(n)-1
Else
 Return int(n)
EndIf
EndFunc