4 Number Theory

Returns #t if the integers a b ... are coprime. Formally, a set of integers is considered coprime (also called relatively prime) if their greatest common divisor is 1.

Example:

> (coprime? 2 6 15)
#t

Wikipedia: Pairwise Coprime

procedure
(pairwise-coprime? a b ...) → Boolean
a : Integer
b : Integer

Returns #t if the integers a b ... are pairwise coprime, meaning that each pair of integers is coprime.

The numbers 2, 6 and 15 are coprime, but not pairwise coprime, because 6 and 15 share the factor 3:

> (pairwise-coprime? 2 6 15)
#f

Wikipedia: Chinese Remainder Theorem

procedure
(solve-chinese as ns) → Natural
as : (Listof Integer)
ns : (Listof Integer)

Given a length-k list of integers as and a length-k list of coprime moduli ns, (solve-chinese as ns) returns the least natural number x that is a solution to the equations

x = a1 (mod n1)
...
x = ak (mod nk)

The solution x is less than (* n1 ... nk).

The moduli ns must all be positive.

What is the least number x that when divided by 3 leaves a remainder of 2, when divided by 5 leaves a remainder of 3, and when divided by 7 leaves a remainder of 2?

> (solve-chinese '(2 3 2) '(3 5 7))
23

Wikipedia: Quadratic Residue

procedure
(quadratic-residue? a n) → Boolean
a : Integer
n : Integer

Returns #t if a is a quadratic residue modulo n, otherwise #f. The modulus n must be positive, and a must be nonnegative.

Formally, a is a quadratic residue modulo n if there exists a number x such that (* x x) = a (mod n). In other words, (quadratic-residue? a n) is #t when a is a perfect square modulo n.

Examples:

> (quadratic-residue? 0 4)
#f
> (quadratic-residue? 1 4)
#t
> (quadratic-residue? 2 4)
#f
> (quadratic-residue? 3 4)
#f

Wikipedia: Legendre Symbol

procedure
(quadratic-character a p) → (U -1 0 1)
a : Integer
p : Integer

Returns the value of the quadratic character modulo the prime p. That is, for a non-zero a the number 1 is returned when a is a quadratic residue, and -1 is returned when a is a non-residue. If a is zero, then 0 is returned.

If a is negative or p is not positive, quadratic-character raises an error. If p is not prime, (quadratic-character a p) is indeterminate.

This function is also known as the Legendre symbol.

> (quadratic-character 0 5)
0
> (quadratic-character 1 5)
1
> (quadratic-character 2 5)
-1
> (quadratic-character 3 5)
-1

Wikipedia: Jacobi Symbol

procedure
(jacobi-symbol a n) → (U -1 0 1)
a : Nonnegative-Integer
n : Positive-Integer

Computes the Jacobi symbol for any nonnegative integer a and any positive odd integer n.

If n is not an odd positive integer, (jacobi-symbol a n) throws an exception.

> (jacobi-symbol 1 1)
1
> (jacobi-symbol 8 11)
-1
> (jacobi-symbol 39 27)
0
> (jacobi-symbol 22 59)
1
> (jacobi-symbol 32 8)
jacobi: contract violation
  expected: odd?
  given: 8
  argument position: 2nd
  other arguments...:
   32

Wikipedia: Multiplicative Inverse

procedure
(modular-inverse a n) → Natural
a : Integer
n : Integer

Returns the inverse of a modulo n if a and n are coprime, otherwise raises an error. The modulus n must be positive, and a must be nonzero.

Formally, if a and n are coprime, b = (modular-inverse a n) is the unique natural number less than n such that (* a b) = 1 (mod n).

> (modular-inverse 2 5)
3
> (modulo (* 2 3) 5)
1

procedure
(modular-expt a b n) → Natural
  a : Integer
  b : Integer
  n : Integer

Computes (modulo (expt a b) n), but much more efficiently. The modulus n must be positive.

Examples:

> (modulo (expt -6 523) 19)
13
> (modular-expt -6 523 19)
13
> (modular-expt 9 158235208 19)
4
> (modular-expt 2 -1 11)
6
> ; don't try this at home!
(modulo (expt 9 158235208) 19)
4

4.1.1 Parameterized Modular Arithmetic🔗ℹ

Wikipedia: Modular Arithmetic

The math/number-theory library supports modular arithmetic parameterized on a current modulus. For example, the code

(with-modulus n
((modexpt a b) . mod= . c))

corresponds with the mathematical statement ab = c (mod n).

The current modulus is stored in a parameter that, for performance reasons, can only be set using with-modulus. (The basic modular operators cache parameter reads, and this restriction guarantees that the cached values are current.)

syntax
(with-modulus n body ...)

n : Integer

Alters the current modulus within the dynamic extent of body. The expression n must evaluate to a positive integer.

By default, the current modulus is 1, meaning that every modular arithmetic expression that does not raise an error returns 0.

procedure
(current-modulus) → Positive-Integer

Returns the current modulus.

Examples:

> (current-modulus)
1
> (with-modulus 5 (current-modulus))
5

procedure
(mod x) → Natural
x : Exact-Rational

Converts a rational number x to a natural number less than the current modulus.

If x is an integer, this is equivalent to (modulo x n). If x is a fraction, an integer input is generated by multiplying its numerator by its denominator’s modular inverse.

Examples:

> (with-modulus 7 (mod (* 218 7)))
0
> (with-modulus 7 (mod 3/2))
5
> (with-modulus 7 (mod/ 3 2))
5
> (with-modulus 7 (mod 3/7))
modular-inverse: expected argument that is coprime to
modulus 7; given 7

procedure
(mod+ a ...) → Natural
a : Integer
procedure
(mod* a ...) → Natural
a : Integer

Equivalent to (modulo (+ a ...) (current-modulus)) and (modulo (* a ...) (current-modulus)), respectively, but generate smaller intermediate values.

procedure
(modsqr a) → Natural
  a : Integer
procedure
(modexpt a b) → Natural
  a : Integer
  b : Integer

Equivalent to (mod* a a) and (modular-expt a b (current-modulus)), respectively.

procedure
(mod- a b ...) → Natural
a : Integer
b : Integer

Equivalent to (modulo (- a b ...) (current-modulus)), but generates smaller intermediate values. Note that (mod- a) = (mod (- a)).

procedure
(mod/ a b ...) → Natural
a : Integer
b : Integer

Divides a by (* b ...), by multiplying a by the multiplicative inverse of (* b ...). The one-argument variant returns the modular inverse of a.

Note that (mod/ a b ...) is not equivalent to (modulo (/ a b ...) (current-modulus)); see mod= for a demonstration.

procedure
(mod= a b ...) → Boolean
  a : Integer
  b : Integer
procedure
(mod< a b ...) → Boolean
  a : Integer
  b : Integer
procedure
(mod<= a b ...) → Boolean
  a : Integer
  b : Integer
procedure
(mod> a b ...) → Boolean
  a : Integer
  b : Integer
procedure
(mod>= a b ...) → Boolean
  a : Integer
  b : Integer

Each of these is equivalent to (op (mod a) (mod b) ...), where op is the corresponding numeric comparison function. Additionally, when given one argument, the inequality tests always return #t.

Suppose we wanted to know why 17/4 = 8 (mod 15), but 51/12 (mod 15) is undefined, even though normally 51/12 = 17/4. In code,

> (with-modulus 15 (mod/ 17 4))
8
> (/ 51 12)
17/4
> (with-modulus 15 (mod/ 51 12))
modular-inverse: expected argument that is coprime to
modulus 15; given 12

We could try to divide by brute force: find, modulo 15, all the numbers a for which (mod* a 4) is 17, then find all the numbers b for which (mod* a 12) is 51.

> (with-modulus 15
    (for/list ([a  (in-range 15)]
               #:when (mod= (mod* a 4) 17))
      a))
'(8)
> (with-modulus 15
    (for/list ([b  (in-range 15)]
               #:when (mod= (mod* b 12) 51))
      b))
'(3 8 13)

So the problem isn’t that b doesn’t exist, it’s that b isn’t unique.

4.2 Primes🔗ℹ

Wikipedia: Prime Number

procedure
(prime? z) → Boolean
z : Integer

Returns #t if z is a prime, #f otherwise.

Formally, an integer z is prime when the only positive divisors of z are 1 and (abs z).

The positive primes below 20 are:

> (filter prime? (range 1 21))
'(2 3 5 7 11 13 17 19)

The corresponding negative primes are:

> (filter prime? (range 1 -21 -1))
'(-2 -3 -5 -7 -11 -13 -17 -19)

procedure
(odd-prime? z) → Boolean
z : Integer

Returns #t if z is a odd prime, #f otherwise.

> (odd-prime? 2)
#f
> (odd-prime? 3)
#t

procedure
(nth-prime n) → Natural
n : Integer

Returns the nth positive prime; n must be nonnegative.

> (nth-prime 0)
2
> (nth-prime 1)
3
> (nth-prime 2)
5

procedure
(random-prime n) → Natural
n : Integer

Returns a random prime smaller than n, which must be greater than 2.

The function random-prime picks random numbers below n until a prime is found.

> (random-prime 10)
2
> (random-prime 10)
7
> (random-prime 10)
5

procedure
(next-prime z) → Integer
z : Integer

Returns the first prime larger than z.

> (next-prime 4)
5
> (next-prime 5)
7

procedure
(prev-prime z) → Integer
z : Integer

Returns the first prime smaller than z.

> (prev-prime 4)
3
> (prev-prime 5)
3

procedure
(next-primes z n) → (Listof Integer)
z : Integer
n : Integer

Returns list of the next n primes larger than z; n must be nonnegative.

> (next-primes 2 4)
'(3 5 7 11)

procedure
(prev-primes z n) → (Listof Integer)
z : Integer
n : Integer

Returns list of the next n primes smaller than z; n must be nonnegative.

> (prev-primes 13 4)
'(11 7 5 3)

Wikipedia: Integer Factorization

procedure
(factorize n) → (Listof (List Natural Natural))
n : Natural

Returns the factorization of a natural number n. The factorization consists of a list of corresponding primes and exponents. The primes will be in ascending order.

The prime factorization of 600 = 2^3 * 3^1 * 5^2:

> (factorize 600)
'((2 3) (3 1) (5 2))

procedure
(defactorize f) → Natural
f : (Listof (List Natural Natural))

Returns the natural number, whose factorization is given by f. The factorization f is represented as described in factorize.

> (defactorize '((2 3) (3 1) (5 2)))
600

procedure
(divisors z) → (Listof Natural)
z : Integer

Returns a list of all positive divisors of the integer z. The divisors appear in ascending order.

> (divisors 120)
'(1 2 3 4 5 6 8 10 12 15 20 24 30 40 60 120)
> (divisors -120)
'(1 2 3 4 5 6 8 10 12 15 20 24 30 40 60 120)

procedure
(prime-divisors z) → (Listof Natural)
z : Natural

Returns a list of all positive prime divisors of the integer z. The divisors appear in ascending order.

> (prime-divisors 120)
'(2 3 5)

procedure
(prime-exponents z) → (Listof Natural)
z : Natural

Returns a list of the exponents of in a factorization of the integer z.

> (define z (* 2 2 2 3 5 5))
> (prime-divisors z)
'(2 3 5)
> (prime-exponents z)
'(3 1 2)

4.3 Roots🔗ℹ

procedure
(integer-root n m) → Natural
n : Natural
m : Natural

Returns the mth integer root of n. This is the largest integer r such that (expt r m) <= n.

> (integer-root (expt 3 4) 4)
3
> (integer-root (+ (expt 3 4) 1) 4)
3

procedure
(integer-root/remainder n m) →
Natural Natural
n : Natural
m : Natural

Returns two values. The first, r, is the mth integer root of n. The second is n-r^m.

> (integer-root/remainder (expt 3 4) 4)
3
0
> (integer-root/remainder (+ (expt 3 4) 1) 4)
3
1

4.4 Powers🔗ℹ

procedure
(max-dividing-power a b) → Natural
a : Integer
b : Integer

Returns the largest exponent, n, of a power with base a that divides b.

That is, (expt a n) divides b but (expt a (+ n 1)) does not divide b.

> (max-dividing-power 3 (expt 3 4))
4
> (max-dividing-power 3 5)
0

procedure
(perfect-power m) → (U (List Natural Natural) #f)
m : Integer

If m is a perfect power, a list with two elements b and n such that (expt b n) = m is returned, otherwise #f is returned.

> (perfect-power (expt 3 4))
'(3 4)
> (perfect-power (+ (expt 3 4) 1))
#f

Wikipedia: Perfect Power

procedure
(perfect-power? m) → Boolean
m : Integer

Returns #t if m is a perfect power, otherwise #f.

> (perfect-power? (expt 3 4))
#t
> (perfect-power? (+ (expt 3 4) 1))
#f

procedure
(prime-power m) → (U (List Natural Natural) #f)
m : Natural

If m is a power of the form (expt p n) where p is prime, then a list with the prime and the exponent is returned, otherwise #f is returned.

> (prime-power (expt 3 4))
'(3 4)
> (prime-power (expt 6 4))
#f

procedure
(prime-power? m) → Boolean
m : Natural

Returns #t if m is a prime power, otherwise #f.

> (prime-power? (expt 3 4))
#t
> (prime-power? (expt 6 4))
#f
> (prime-power? 1)
#f
> (prime-power? 0)
#f

procedure
(odd-prime-power? m) → Boolean
m : Natural

Returns #t if m is a power of an odd prime, otherwise #f.

> (odd-prime-power? (expt 2 4))
#f
> (odd-prime-power? (expt 3 4))
#t
> (odd-prime-power? (expt 15 4))
#f

procedure
(as-power m) →
Natural Natural
m : Positive-Integer

Returns two values b and n such that m = (expt b n) and n is maximal.

> (as-power (* (expt 2 4) (expt 3 4)))
6
4
> (expt 6 4)
1296
> (* (expt 2 4) (expt 3 4))
1296
> (as-power (* (expt 2 4) (expt 3 5)))
3888
1

procedure
(perfect-square m) → (U Natural #f)
m : Natural

Returns (sqrt m) if m is perfect square, otherwise #f.

> (perfect-square 9)
3
> (perfect-square 10)
#f

4.5 Multiplicative and Arithmetic Functions🔗ℹ

The functions in this section are multiplicative (with exception of the Von Mangoldt function). In number theory, a multiplicative function is a function f such that (f (* a b)) = (* (f a) (f b)) for all coprime natural numbers a and b.

Wikipedia: Euler’s Totient

procedure
(totient n) → Natural
n : Natural

Returns the number of integers from 1 to n that are coprime with n.

This function is known as Eulers totient or phi function.

> (totient 9)
6
> (length (filter (curry coprime? 9) (range 10)))
6

Wikipedia: Moebius Function

procedure
(moebius-mu n) → (U -1 0 1)
n : Natural

Returns:

1 if n is a square-free product of an even number of primes
-1 if n is a square-free product of an odd number of primes
0 if n has a multiple prime factor

> (moebius-mu (* 2 3 5))
-1
> (moebius-mu (* 2 3 5 7))
1
> (moebius-mu (* 2 2 3 5 7))
0

Wikipedia: Divisor Function

procedure
(divisor-sum n k) → Natural
n : Natural
k : Natural

Returns sum of the kth powers of all divisors of n.

> (divisor-sum 12 2)
210
> (apply + (map sqr (divisors 12)))
210

OEIS: Big Omega

procedure
(prime-omega n) → natural?
n : Natural

Counting multiplicities the number of prime factors of n is returned.

> (prime-omega (* 2 2 2 3 3 5))
6

Wikipedia: Von Mangoldt Function

procedure
(mangoldt-lambda n) → Real
n : Natural

The von Mangoldt function. If n=p^k for a prime p and an integer k>=1 then (log n) is returned. Otherwise 0 is returned.

Note: The Von Mangoldt function is not multiplicative.

> (mangoldt-lambda (* 3 3))
1.0986122886681098
> (log 3)
1.0986122886681098

4.6 Number Sequences🔗ℹ

Wikipedia: Bernoulli Number

procedure
(bernoulli-number n) → Exact-Rational
n : Integer

Returns the nth Bernoulli number; n must be nonnegative.

> (map bernoulli-number (range 9))
'(1 -1/2 1/6 0 -1/30 0 1/42 0 -1/30)

Note that these are the first Bernoulli numbers, since (bernoulli-number 1) = -1/2.

MathWorld: Eulerian Number

procedure
(eulerian-number n k) → Natural
n : Integer
k : Integer

Returns the Eulerian number <n,k>; both arguments must be nonnegative.

> (eulerian-number 5 2)
66

Wikipedia: Fibonacci Number

procedure
(fibonacci n) → Natural
n : Integer

Returns the nth Fibonacci number; n must be nonnegative.

The ten first Fibonacci numbers.

> (map fibonacci (range 10))
'(0 1 1 2 3 5 8 13 21 34)

procedure
(make-fibonacci a b) → (Integer -> Integer)
a : Integer
b : Integer

Returns a function representing a Fibonacci sequence with the first two numbers a and b. The fibonacci function is defined as (make-fibonacci 0 1).

Wikipedia: Lucas Number

The Lucas numbers are defined as a Fibonacci sequence starting with 2 and 1:

> (map (make-fibonacci 2 1) (range 10))
'(2 1 3 4 7 11 18 29 47 76)

procedure
(modular-fibonacci n m) → Natural
n : Integer
m : Integer

Returns the nth Fibonacci number modulo m; n must be nonnegative and m must be positive.

The ten first Fibonacci numbers modulo 5.

> (map (λ (n) (modular-fibonacci n 5)) (range 10))
'(0 1 1 2 3 0 3 3 1 4)

procedure
(make-modular-fibonacci a b) → (Integer Integer -> Integer)
a : Integer
b : Integer

Like make-fibonacci, but makes a modular Fibonacci sequence.

Wikipedia: Farey Sequence

procedure
(farey-sequence n) → (Listof Exact-Rational)
n : Integer

Returns a list of the numbers in the nth Farey sequence; n must be positive.

The nth Farey sequence is the sequence of all completely reduced rational numbers from 0 to 1 which denominators are less than or equal to n.

> (farey-sequence 1)
'(0 1)
> (farey-sequence 2)
'(0 1/2 1)
> (farey-sequence 3)
'(0 1/3 1/2 2/3 1)

MathWorld: Tangent Number

procedure
(tangent-number n) → Integer
n : Integer

Returns the nth tangent number; n must be nonnegative.

> (tangent-number 1)
1
> (tangent-number 2)
0
> (tangent-number 3)
2

4.7 Combinatorics🔗ℹ

Wikipedia: Factorial

procedure
(factorial n) → Natural
n : Integer

Returns the factorial of n, which must be nonnegative. The factorial of n is the number (* n (- n 1) (- n 2) ... 1).

> (factorial 3)
6
> (factorial 0)
1

Wikipedia: Binomial Coefficient

procedure
(binomial n k) → Natural
n : Integer
k : Integer

Returns the number of ways to choose a set of k items from a set of n items; i.e. the order of the k items is not significant. Both arguments must be nonnegative.

When k > n, (binomial n k) = 0. Otherwise, (binomial n k) is equivalent to (/ (factorial n) (factorial k) (factorial (- n k))), but computed more quickly.

> (binomial 5 3)
10

Wikipedia: Permutations

procedure
(permutations n k) → Natural
n : Integer
k : Integer

Returns the number of ways to choose a sequence of k items from a set of n items; i.e. the order of the k items is significant. Both arguments must be nonnegative.

When k > n, (permutations n k) = 0. Otherwise, (permutations n k) is equivalent to (/ (factorial n) (factorial (- n k))).

> (permutations 5 3)
60

Wikipedia: Multinomial Coeffecient

procedure
(multinomial n ks) → Natural
n : Integer
ks : (Listof Integer)

A generalization of binomial to multiple sets of choices; e.g. (multinomial n (list k0 k1 k2)) is the number of ways to choose a set of k0 items, a set of k1 items, and a set of k2 items from a set of n items. All arguments must be nonnegative.

When (apply + ks) = n, this is equivalent to (apply / (factorial n) (map factorial ks)). Otherwise, multinomial returns 0.

> (multinomial 5 '(3 2))
10
> (= (multinomial 8 '(5 3))
(binomial 8 5)
(binomial 8 3))
#t
> (multinomial 10 '(5 3 2))
2520
> (multinomial 0 '())
1
> (multinomial 4 '(1 1))
0

Wikipedia: Partition

procedure
(partitions n) → Natural
n : Integer

Returns the number of partitions of n, which must be nonnegative. A partition of a positive integer n is a way of writing n as a sum of positive integers. The number 3 has the partitions (+ 1 1 1), (+ 1 2) and (+ 3).

> (partitions 3)
3
> (partitions 4)
5

4.8 Special Numbers🔗ℹ

4.8.1 Polygonal Numbers🔗ℹ

Wikipedia: Polygonal Number

procedure
(triangle-number? n) → Boolean
  n : Natural
procedure
(square-number? n) → Boolean
  n : Natural
procedure
(pentagonal-number? n) → Boolean
  n : Natural
procedure
(hexagonal-number? n) → Boolean
  n : Natural
procedure
(heptagonal-number? n) → Boolean
  n : Natural
procedure
(octagonal-number? n) → Boolean
  n : Natural

These functions check whether the input is a polygonal number of the types triangle, square, pentagonal, hexagonal, heptagonal and octogonal respectively.

procedure
(triangle-number n) → Natural
  n : Natural
procedure
(sqr n) → Natural
  n : Natural
procedure
(pentagonal-number n) → Natural
  n : Natural
procedure
(hexagonal-number n) → Natural
  n : Natural
procedure
(heptagonal-number n) → Natural
  n : Natural
procedure
(octagonal-number n) → Natural
  n : Natural

These functions return the nth polygonal number of the corresponding type of polygonal number.

Wikipedia: Mediant

4.9 Fractions🔗ℹ

procedure
(mediant x y) → Exact-Rational
x : Exact-Rational
y : Exact-Rational

Computes the mediant of the numbers x and y. The mediant of two fractions p/q and r/s in their lowest term is the number (p+r)/(q+s).

> (mediant 1/2 5/6)
3/4

4.10 The Quadratic Equation🔗ℹ

procedure
(quadratic-solutions a b c) → (Listof Real)
  a : Real
  b : Real
  c : Real

Returns a list of all real solutions to the equation a x^2 + b x +c = 0.

> (quadratic-solutions 1 0 -1)
'(-1 1)
> (quadratic-solutions 1 2 1)
'(-1)
> (quadratic-solutions 1 0 1)
'()

The implementation of quadratic-solutions handles cancellation and overflow intelligently:

> (quadratic-solutions 1e+200 2e+200 1e+200)
'(-1.0)
> (quadratic-solutions 1e-200 -2e-200 1e-200)
'(1.0)

For exact inputs, if the output can be exactly represented, it will be:

> (quadratic-solutions -1 2/3 1/3)
'(1 -1/3)

procedure
(quadratic-integer-solutions a b c) → (Listof Integer)
  a : Real
  b : Real
  c : Real

Returns a list of all integer solutions to the equation a x^2 + b x +c = 0.

> (quadratic-integer-solutions 1 0 -1)
'(-1 1)
> (quadratic-integer-solutions 1 0 -2)
'()

procedure
(quadratic-natural-solutions a b c) → (Listof Natural)
  a : Real
  b : Real
  c : Real

Returns a list of all natural solutions to the equation a x^2 + b x +c = 0.

> (quadratic-natural-solutions 1 0 -1)
'(1)
> (quadratic-natural-solutions 1 0 -2)
'()

procedure
(complex-quadratic-solutions a b c) → (Listof Complex)
  a : Complex
  b : Complex
  c : Complex

Returns a list of all complex solutions to the equation a x^2 + b x +c = 0. This function allows complex coeffecients.

> (complex-quadratic-solutions 1 0 1)
'(0-1i 0+1i)
> (complex-quadratic-solutions 1 0 (sqrt -1))
'(-0.7071067811865476+0.7071067811865475i
0.7071067811865476-0.7071067811865475i)
> (complex-quadratic-solutions 1 0 1)
'(0-1i 0+1i)

Added in version 1.1 of package math-lib.

4.11 The group Zn and Primitive Roots🔗ℹ

Wikipedia: The Group Zn

The numbers 0, 1, ..., n-1 with addition and multiplication modulo n is a ring called Zn.

The group of units in Zn with respect to multiplication modulo n is called Un.

The order of an element x in Un is the least k>0 such that x^k=1 mod n.

A generator the group Un is called a primitive root modulo n. Note that g is a primitive root if and only if order(g)=totient(n). A group with a generator is called cyclic.

procedure
(unit-group n) → (Listof Positive-Integer)
n : Integer

Returns a list of all elements of Un, the unit group modulo n. The modulus n must be positive.

> (unit-group 5)
'(1 2 3 4)
> (unit-group 6)
'(1 5)

procedure
(unit-group-order x n) → Positive-Integer
x : Integer
n : Integer

Returns the order of x in the group Un; both arguments must be positive. If x and n are not coprime, (unit-group-order x n) raises an error.

> (unit-group-order 2 5)
4
> (unit-group-order 2 6)
unit-group-order: expected coprime arguments; given 2 and 6

procedure
(unit-group-orders n) → (Listof Positive-Integer)
n : Integer

Returns a list (list (unit-group-order x0 n) (unit-group-order x1 n) ...) where x0, x1, ... are the elements of Un. The modulus n must be positive.

> (unit-group-orders 5)
'(1 4 4 2)
> (map (curryr unit-group-order 5) (unit-group 5))
'(1 4 4 2)

procedure
(primitive-root? x n) → Boolean
x : Integer
n : Integer

Returns #t if the element x in Un is a primitive root modulo n, otherwise #f is returned. An error is signaled if x is not a member of Un. Both arguments must be positive.

> (primitive-root? 1 5)
#f
> (primitive-root? 2 5)
#t
> (primitive-root? 5 5)
primitive-root?: expected coprime arguments; given 5 and 5

procedure
(exists-primitive-root? n) → Boolean
n : Integer

Returns #t if the group Un has a primitive root (i.e. it is cyclic), otherwise #f is returned. In other words, #t is returned if n is one of 1, 2, 4, p^e, 2*p^e where p is an odd prime, and #f otherwise. The modulus n must be positive.

> (exists-primitive-root? 5)
#t
> (exists-primitive-root? 6)
#t
> (exists-primitive-root? 12)
#f

procedure
(primitive-root n) → (Union Natural #f)
n : Integer

Returns a primitive root of Un if one exists, otherwise #f is returned. The modulus n must be positive.

> (primitive-root 5)
2
> (primitive-root 6)
5

procedure
(primitive-roots n) → (Listof Natural)
n : Integer

Returns a list of all primitive roots of Un. The modulus n must be positive.

> (primitive-roots 3)
'(2)
> (primitive-roots 5)
'(2 3)
> (primitive-roots 6)
'(5)

1	Constants and Elementary Functions
2	Flonums
3	Special Functions
4	Number Theory
5	Arbitrary-Precision Floating-Point Numbers (Bigfloats)
6	Arrays
7	Matrices and Linear Algebra
8	Statistics Functions
9	Probability Distributions
10	Stuff That Doesn’t Belong Anywhere Else

4.1	Congruences and Modular Arithmetic
4.2	Primes
4.3	Roots
4.4	Powers
4.5	Multiplicative and Arithmetic Functions
4.6	Number Sequences
4.7	Combinatorics
4.8	Special Numbers
4.9	Fractions
4.10	The Quadratic Equation
4.11	The group Zn and Primitive Roots