   12MODE 12  :  REM MODE 12 :  REM  BBC BASIC.
   15PRINT''"REM  >  prgm 1.5.  06.08.95  21:56, 11.08.95"'" donmcd.calc.NumberThy. PrtvRoots."
   25
   20PRINT ' "Determines the prime factors and"'" their exponents of an integer N."  CHR$7
   21PRINT "Theorem 5.3.9 (Gauss 1801).  Let n> 1 be an integer."'"Then n has a primitive root if and only if n = 2, 4, p^k, or 2p^k,"'"p being an odd prime."
   31
   30DIM  G(32),  M(32)
   40   ON ERROR REPORT : PRINT "  at erl. ";ERL
   41   REM on Error  BBC BASIC.
   50K = 0
   60D = 1
   70INPUT"ENTER N (Don expression N$,"'" 0 < 2 QUIT) ", N$
   80   NN = INT EVAL N$   : REM EVAL.uate formula BBC BASIC.
  130   PRINT N$ " = "; NN
  140   IF NN < 2 THEN PRINT''"REM  >  prgm 1.5.  11.08.95"'" donmcd.calc.NumberThy. PrtvRoots.  e.n.d."   : END
  142   WHILE FALSE : INPUT "Do you want Primitive roots as well, Yy/Nn"; prtv$
  144   IF prtv$ = "Y" OR prtv$ = "y" THEN
  145       prtv= TRUE : PRINT "Yes":
  147    ELSE prtv = FALSE : PRINT "No."
  148    ENDIF
  149    PRINT "Contin.."GET$   :  ENDWHILE
  150   NN -= 1
  160REM  Loop.
  170   NN += 1  :
  180   N = NN : REM PRINT '  "Please factor "; N
  190K = 0  :  M()=(0)  :  REM Zero array.
  200D = 1
  210P = 2
  220REM  remove the factor 2
  230   F = N / P
  240      IF F = INT(F) THEN GOTO 640
  250      IF N < 9 THEN GOTO 390
  260      IF P = 2 THEN
  270            REM P."BUG REMOVES FACTOR 2 ONCE ONLY, " :
  280            P = 3
  290            ENDIF
  300
  310REM  test for factors in the set of odd numbers.
  320      F = N / P
  330         IF F = INT(F) THEN GOTO 640
  340         P = P + 2
  350
  360      IF P <= SQR(N) THEN GOTO 290
  370
  380REM store the last factor
  390      IF N = 1 THEN GOTO 480
  400      IF N = D THEN GOTO 450
  410         K = K + 1
  420         G(K) = N
  430         GOTO 480
  440
  450      M(K) = M(K) + 1
  460
  470REM  display the factors and their exponents
  480      FOR I = 1 TO K
  490         IF I = 1 THEN PRINT
  500         PRINT "."; G(I);
  510         IF M(I) > 1 THEN PRINT "^"; M(I);
  520         NEXT I
  530REM PRINT" Phi Totient function?"
  540  P = NN
  550  FOR I = 1 TO K
  560     P = P * (1-  1/G(I) )
  570     NEXT I
  580  PRINT TAB(14) "N "; NN  "  Phi  "; P" ";  :
  581  IF NN < 8 OR (K=1 AND  G(1) > 2 ) OR (K=2 AND G(1)^M(1) < 3) THEN PROCprtv  :  REM BBC BASIC Procedure Function Subprogram.
  590  IF NN MOD 16 = 4 THEN PRINT CHR$7 ' "  Primitive roots if n = 2,4,p^k,2p^k." ;
  600  GOTO 160
  610         STOP
  620
  630REM store new factor or increase power of the previous one
  640      IF P = D THEN GOTO 710
  650         K = K + 1
  660         G(K) = P
  670         M(K) = 1
  680         D = P
  690         REM PRINT ;K"-TH PR FACTOR = "D
  700      GOTO 720
  710      M(K) = M(K) + 1
  720      N = F
  730      REM  PRINT"POWER = "; M(K)  "  REMAINDER  = "N
  740
  750   GOTO 230
  760DEF PROCprtv :REM  Finds the primitive roots (if any) of any given integer N.
  765 REM  BBC Basic Define Procedure
  770PRINT"Primtv rts= ";
  780REM NN = 33  :  P = 20  :  PRINT "nn = "NN  "  p = ";P
  790FOR a = 2 TO  NN/2 + SQR( NN ) :  REM arbitrary reduced list length.
  795    REM  BBC BASIC square root func.
  800REM check whether a is coprime to NN
  810    a1 = NN
  820    b1 = a
  830    REPEAT
  840    r =  a1 MOD  b1  :  REM  BBC BASIC modulo arithmetic a1%b1 ??
  850      a1 = b1
  860      b1 = r
  870    UNTIL r = 0
  880IF a1 = 1 THEN
  890   REM Compute successive powers of a (mod n)
  900       a1 = a
  910       e = 1
  920       e += 1
  930       a1 = (a1 * a) MOD NN
  940       IF a1 = 1  AND e < P THEN  GOTO 980
  950       IF  e < P THEN GOTO 920
  960       PRINT; a", " ;  :  REM " e") ";     : REM  "primitive root"
  970    GOTO 990
  980    REM PRINT; a "^"  e " ";     :REM  has order
  990    ENDIF
 1000 IF POS > 65 THEN PRINT TAB( 10);
 1010        REM  BBC BASIC if more than 65 chars on print line then newline.
 1020IF a >= 50 THEN a = NN
 1025NEXT a
 1030REM PRINT "Cont..";GET$
 1040ENDPROC