Chapter 11 : Number Theoretic Algorithms

(July 22, 2009) [Japanese]


Several number theoretic functions are prepared in UBASIC as embedded functions from the start.
But in case of usual computer languages, we have to implement those functions by ourselves.

In this chapter, I explain computing methods for number theoretic functions and algorithms used for number theoretic computation.


  1. Euclidean algorithm for GCD
  2. Power
  3. Moebius function, Euler function
  4. Fibonacci and Lucas number, definition of Lucas sequence
  5. Computation of Lucas sequence
  6. Bernoulli and Euler number

  7. Cyclotomic polynomial and cyclotomic number
  8. Wieferich prime (April 01, 2009)
  9. an=c mod n (July 22, 2009)
  10. Hilbert and Weber class polynomial

Chapter 10
Congruent Numbers (Congruum)
"Mathematician's Secret Room" Chapter 12
Integer Factorization Algorithms
Chapter 10 (Japanese) index (Japanese) Chapter 12 (Japanese)

E-mail :
Hisanori Mishima