The exact precision integer and rational arithmetic provided by Derive make it ideal for explorations into the theory of numbers.  The built-in Piecewise Continuous FunctionsPiecewise_Continuous_Functions and Probability FunctionsProbability_Functions are especially useful for this purpose.  The file NumberTheoryFunctions.mth defines additional number theory functions in terms of the built-in functions.  The function definitions in the file are automatically loaded when any of its functions are first used.


EXTENDED_GCD(a, b) simplifies for integers a and b to a vector [d, [x, y]] of integers such that

d = gcd(a, b) = x·a + y·b

using the extended Euclidean gcd algorithm.  For example, to find the extended gcd of 20580 and 85176, simplify the expression

EXTENDED_GCD(20580, 85176)


SOLVE_MOD(u, x, m) simplifies to a vector of solutions of the linear congruence equation u(x) mod m.  For example, to solve the equation 3·x = 30 mod 9, simplify either of the expressions

SOLVE_MOD(3·x = 30, x, 9)

SOLVE_MOD(3·x - 30, x, 9)


CRT(a, m) simplifies to the solution of the system of linear congruence equations x = ai mod mi, where the elements of m must be pairwise coprime, using the Chinese Remainder Theorem (CRT).  For example, to solve the congruences x = 1 mod 4, x = 2 mod 5, and x = 3 mod 11, simplify the expression

CRT([1, 2, 3], [4, 5, 11])


NTH_PRIME(n) simplifies to the nth prime number.  For example, to make a table of the first 50 primes, simplify the expression

VECTOR(VECTOR(NTH_PRIME(n+m), m, 0, 40, 10), n, 1, 10)


PRIMEPI(x, d, a) simplifies to the number of primes p ≤ x, where x is a positive real number, such that p is of the form p = k·d + a for some k ≥ 0.  d and a must be coprime natural numbers.  PRIMEPI(x) simplifies to the number of primes up to x.  For example,

[PRIMEPI(10000, 6, 1), PRIMEPI(10000, 6, 5) + 2, PRIMEPI(10000)]

simplifies to [611, 618, 1229].


FAREY(n) simplifies to a vector of Farey fractions of order n (i.e. all the fractions in the interval (0,1] whose denominator is not greater than n).  For example, to determine the Farey fractions of order 6, simplify the expression

FAREY(6)


DIVISORS(n) simplifies to the ordered vector of all the positive divisors of n.  For example, to determine the divisors of 28, simplify the expression

DIVISORS(28)


DIVISOR_SIGMA(k, n) simplifies to the sum of the kth powers of the positive divisors of n where k is a nonnegative integer.  For example, to determine the sum of the cubes of the divisors of 1000, simplify the expression

DIVISOR_SIGMA(3, 1000)


DIVISOR_TAU(n) simplifies to the number of divisors of n (i.e. it is equivalent to DIVISOR_SIGMA(0, n) ).  For example, to determine the number of divisors of 28, simplify the expression

DIVISOR_TAU(28)


EULER_PHI(n) simplifies to the Euler's totient function ϕ(n) (i.e. the number of positive integers not greater than n that are relatively prime to n).  For example, to determine ϕ(100), simplify the expression

EULER_PHI(100)


PRIME_POWER?(n) simplifies to true, if n is a power of a prime; otherwise it simplifies to false.  For example, to determine all prime powers not greater than 100, simplify the expression

SELECT(PRIME_POWER?(n), n, 1, 100)


PRIMITIVE_ROOT(n) simplifies to the smallest primitive root modulo n, if one exists; otherwise it simplifies to a question mark.  For example, to determine the primitive root modulo 54, simplify the expression

PRIMITIVE_ROOT(54)


MOEBIUS_MU(n) simplifies to the Moebius mu function of n.  For example, to determine the Moebius mu function of 100, simplify the expression

MOEBIUS_MU(100)


SQUAREFREE(n) simplifies to true, if n is square free (i.e. not divisible by the square of a prime); otherwise it simplifies to false.  For example, to determine if 837 is square free, simplify the expression

SQUAREFREE(837)


CYCLOTOMIC(n, x) simplifies to the nth cyclotomic polynomial in x.  For example, to determine the first 6 cyclotomic polynomials, simplify the expression

VECTOR([n, CYCLOTOMIC(n,x)], n, 1, 6)


GEN_LUCAS(n, p, q, L0, L1) simplifies to the nth term of the generalized Lucas sequence L(n) where L(0) = L0, L(1) = L1, and L(n+2) = p·L(n+1) - q·L(n).


U_LUCAS(n, p, q) simplifies to the nth term of the Lucas sequence U(n) where U(0)=0, U(1)=1, and U(n+2)=p·U(n+1)-q·U(n).  For example, to determine U(30) with p=1 and q=-1, simplify the expression

U_LUCAS(30, 1, -1)


V_LUCAS(n, p, q) simplifies to the nth term of the Lucas sequence V(n) where V(0)=2, V(1)=p, and V(n+2)=p·V(n+1)-q·V(n).  For example, to determine V(30) with p=1 and q=-1, simplify the expression

V_LUCAS(31, 1, -1)


U_MOD(n, p, q, m) simplifies to U_LUCAS(n, p, q) mod m, but is much more efficient.  If the discriminant p²-4·q is 0 mod m, a question mark is returned.  For example, to show that U(30) is divisible by 31 with p=1 and q=-1, simplify the expression

U_MOD(30, 1, -1, 31)


V_MOD(n, p, q, m) simplifies to V_LUCAS(n, p, q) mod m, but is much more efficient.  For example, to find V(31) mod 31 with p=1 and q=-1, simplify the expression

V_MOD(31, 1, -1, 31)


LUCAS(n) simplifies to the nth Lucas number (i.e. it is equivalent to V_LUCAS(n,1,-1)).  For example, to determine the first 11 Lucas numbers, simplify the expression

VECTOR(LUCAS(n), n, 0, 10)


FIBONACCI(n) simplifies to the nth Fibonacci number.  For example, to determine the first 11 Fibonacci numbers, simplify the expression

VECTOR(FIBONACCI(n), n, 0, 10)


PELL(n) simplifies to the nth Pell number.  For example, to determine the first 11 Pell numbers, simplify the expression

VECTOR(PELL(n), n, 0, 10)


LUCAS_LEHMER(p) simplifies to true, if the Mersenne number 2^p-1, where p is an odd prime, is prime, otherwise it simplifies to false.  For example, to determine if 2^31-1 is prime, simplify the expression

LUCAS_LEHMER(31)


NEXT_MERSENNE_DEGREE(n) simplifies to the smallest prime p > n such that the Mersenne number 2^p - 1 is prime.  For example, to determine the first prime p > 31 such that 2^p - 1 is prime, simplify the expression

NEXT_MERSENNE_DEGREE(31)


MERSENNE_LIST(n) simplifies to the first n primes p for which the corresponding Mersenne number 2^p - 1 is prime.  For example, to find the 12 smallest exponents of this kind, simplify the expression

MERSENNE_LIST(12)


MERSENNE_DEGREE(n) is the nth exponent (ordered by size) for which the corresponding Mersenne number is known to be prime.  For example, to determine the exponent of the largest known Mersenne prime as of 13 August 1999, simplify the expression

MERSENNE_DEGREE(38)


MERSENNE(n) simplifies to the nth Mersenne prime.  For example, to determine the first 12 Mersenne primes, simplify the expression

VECTOR(MERSENNE(n), n, 1, 12)


PERFECT(n) simplifies to the nth perfect number (i.e. numbers that are equal to the sum of their divisors).  For example, to determine the first 10 perfect numbers, simplify the expression

VECTOR(PERFECT(n), n, 1, 10)


CONTINUED_FRACTION(u, n) approximates to a vector of n+1 partial quotients of the continued fraction of u.  If ?s appear in the result, use the Precision fieldPrecision_field of the Options > Mode Settings > Simplification command19_L5FP to increase the precision.  For example, to determine the first 8 partial quotients of the continued fraction for the base of the natural logarithms e, simplify the expression

CONTINUED_FRACTION(#e, 8)


CONVERGENT(x, k) simplifies to the kth convergent of x based on the continued fraction of x.  For example, to approximate √2 using the 10th convergent, simplify the expression

CONVERGENT(SQRT(2), 10)


CONVERGENTS(x, k) simplifies to a vector of the 0 through kth convergents of x based on the continued fraction for x.  For example, to generate a vector of the first 11 convergents of √2, simplify the expression

CONVERGENTS(SQRT(2), 10)


JACOBI(a, b) simplifies to the Jacobi symbol (a/b), where a is assumed to be an integer and b an odd natural number.  Jacobi symbols play an important role in number theory.  In particular, if b is an odd prime, then 1 + (a/b) is the number of mod b incongruent solutions of the congruence x^2 = a mod b.  For example, to see whether 2 is a square mod 23 or not, simplify the expression

JACOBI(2, 23)


SQUARE_ROOT(a, p) simplifies to a square root of a mod p, where a is an integer and p a prime, if one exists and a question mark otherwise.  For example, to determine a square root of 2 mod 23, simplify the expression

SQUARE_ROOT(2,23)


Other Utility File LibraryG5BS2R 

Created with the Personal Edition of HelpNDoc: Full-featured multi-format Help generator