# Elementary Number Theory

## on the TI-8x Graphing Calculator

### Contents

[Prev] [TI Calc Intro] [Next]

## General

The Texas Instruments calculators sells a line of programmable hand calculators with set of functions and a simple programming language which is, at a simple level, compatible between calculator models. These programs will run on the TI-86/85/83/82/72.

The TI-8x series of calculators runs on a variant of the old Zilog Z80 processor and supports computations with integers as large as 246. (The display will not display integers this large, converting them to floating point for display, but some simple experiments seems to show that the internal representation is still faithful.) This means that, taking into account multiplication and modular reduction, the largest numbers which can be used in these algorithms is 223=8388608.

These programs can be written and saved on the calculator from PRGM mode, entered by typing the [PRGM] key. The basic functions are entered into a program by finding them in the menu structure, usually in MATH mode. On the TI-85/86 the functions may also be entered by typing their names in directly (case is not important).

## Basic Operations

The basic arithmetic operations, `+, -, /`, are available from the keyboard. The factorial operation, `n!`, is available from the `[PROB]` submenu of the `[MATH]` menu.

The TI86/85 have a modular reduction operator. This can either be typed in directly from the keyboard: `MOD(37,5)` (case is not important), or found in the `[NUM]` submenu of the `[MATH]` menu. For the other calculators the same effect as `MOD(n,m)` can be gotten by computing `n-m*int(n/m)` if m is positive.

## GCD

GCD is a built-in function for all but the TI-82. The GCD function found in the `[MISC]` submenu of the `[MATH]` menu.

An extended GCD algorithm can be implemented with the following program.

``` Input "N ",N Input "M ",M [1,0]->K [0,1]->L Repeat (N=0) int(M/N)->Q M-N*int(M/N)->M L-Q*K->L If (M==0) Goto XGCDEnd int (N/M)->Q N-M*int(N/M)->N K-Q*L->K End M->N L->K Lbl XGCDEnd Disp N,K ```

Users of the TI-82 may use the following program to compute the basic GCD program. This is written so it can be used as a subroutine in other programs by placing the operands in x and y and expecting the result in x.

``` Repeat (Y=0) X-Y*int(X/Y)->X If (X==0) Y->X Return End Y-X*int(Y/X)->Y End Return ```

## Exponentiation - PowMod

The Russian Peasant method for modular exponentiation can be implemented with the following program:

``` Input "Modulus ",M Input "Element ",E Input "Power ",P 1->A Repeat (P=0) If ((P-2*int(P/2))=1) E*A-M*int(E*A/M)->A E^2-M*int(E^2/M)->E iPart (P/2)->P End Disp A ```

## Finding Primes - The Sieve of Eratosthenes

The Sieve of Eratosthenes for finding successive primes can be implemented with the following program. The program sieves over the first 255 odd numbers, printing out the primes.

``` 255 -> L L -> dim(L1) Fill(0,L1) For(I,1,L) If (L1(I)==0) Then Disp 2*I+1 For(J,I,L,2*I+1) 1 -> L1(J) End End End DelVar(L1) ```

## Factoring - Pollard Rho

The Pollard Rho method for factorization can be implemented with the following program:

``` Input "Number ",M 2->R 5->S 1->F While (F=1) R^2+1-M*int((R^2+1)/M)->R S^2+1-M*int((S^2+1)/M)->S S^2+1-M*int((S^2+1)/M)->S gcd(abs(R-S),M)->F End Disp F ```

## Computing the Order of Integers

The order of an integer in the group of units mod some other integer (ie the smallest exponent e such that be(mod N)=1) can be computed with the following program:

``` Input "Modulus ",M Input "Element ",E 1 -> O ELT -> A Repeat (A=1) E*A-M*int(E*A/M) -> A ORD+1 -> ORD End Disp ORD ```

## Commands

• abs(n) - Compute the absolute value of a number (or the elements of a list or matrix). (TI-86/85/83/82/73)
• n! - Compute n factorial. [Found in the STAT menu] (TI-86/85/83/82/73)
• gcd(n,m) - Compute the gcd of two numbers. (TI-86/85/83/73, but not TI-82)
• int(n) - Compute the largest integer less than n. (TI-86/85/83/82/73)
• iPart(n) - Compute the integer part of a real number. For positive numbers this will be positive and for negative numbers this will be negative. For positive numbers this will have the same value as int. (TI-86/85/83/82/73)
• mod(n,m) - Compute the value of n(mod m), the smallest postive number a such that a-n is divisible by m. (TI-86/85, but not TI-83/82/73)

Robert Campbell
Last modified: Oct 6, 2002