Arithmetic Algorithms

WarningThese algorithms mostly use single-precision (platform-dependent) arithmetic.

1. Evaluate HCF ( , )

   

2. Solve the congruence   x   ≡     (mod  )    (non-zero modulus)

   

3. Solve the Diophantine equation   x + y   =       (1st entry ≥ 2nd entry > 0)

   

4. Evaluate the Jacobi (/Legendre) symbol ( /  )     (second entry odd and positive)

   

5. Solve the Diophantine equation  x2 + y2   =        (a prime of the form 4k+1)

WarningThis algorithm may terminate abnormally if the input is not an odd prime.

   

6. Find the Continued Fraction equal to /    (0 < 1st entry < 2nd entry)

   

7. Develop the Continued Fraction for  θ :=  (u + v√D) / w    (θ   D   w  > 0,   v ≠ 0,    D not a square)

u    v    D    w   

   

8. Solve the congruence  x2   ≡     (mod  )    (modulus an odd prime)

WarningThis algorithm may terminate abnormally if the modulus is not an odd prime.

   

9. Chinese Remainder Theorem    (Both moduli must be non-zero)

Solve two congruences:   x   ≡     (mod )
 x   ≡     (mod )
   

10. Develop the p-adic expansion of a / b    (p prime;  a, b > 0;  HCF(p, b)=1)

WarningThis algorithm may terminate abnormally if p is not a prime.

p    a    b   

   

11. Qin Jiushao's "reduction"

Given positive integers a   and   b ,  find coprime positive integers x, y such that
  • x divides a
  • y divides b
  • LCM (x, y) = LCM (a, b)