8.14.0.3

4Number TheoryðŸ”—â„¹

 (require math/number-theory) package: math-lib

4.1Congruences and Modular ArithmeticðŸ”—â„¹

Wikipedia: Divisor

 procedure(divides? m n) → Boolean m : Integer n : Integer
Returns #t if m divides n, #f otherwise.

Formally, an integer m divides an integer n when there exists a unique integer k such that (* m k) = n.

Examples:
 > (divides? 2 9) #f > (divides? 2 8) #t

Note that 0 cannot divide anything:
 > (divides? 0 5) #f > (divides? 0 0) #f

Practically, if (divides? m n) is #t, then (/ n m) will return an integer and will not raise exn:fail:contract:divide-by-zero.

 procedure(bezout a b c ...) → (Listof Integer) a : Integer b : Integer c : Integer
Given integers a b c ... returns a list of integers (list u v w ...) such that (gcd a b c ...) = (+ (* a u) (* b v) (* c w) ...).

Examples:
 > (bezout 6 15) '(-2 1) > (+ (* -2 6) (* 1 15)) 3 > (gcd 6 15) 3

Wikipedia: Coprime

 procedure(coprime? a b ...) → Boolean a : Integer b : Integer
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

 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

 procedure 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:

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.

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

 procedure 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.1Parameterized 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
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.2PrimesðŸ”—â„¹

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 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 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) 5 > (random-prime 10) 3 > (random-prime 10) 5

 procedure z : Integer
Returns the first prime larger than z.

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

 procedure 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)

 procedure 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 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 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 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.3RootsðŸ”—â„¹

 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.4PowersðŸ”—â„¹

 procedure 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 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 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 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.5Multiplicative 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.

 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

OEIS: Big Omega

 procedure n : Natural
Counting multiplicities the number of prime factors of n is returned.

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

 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.6Number SequencesðŸ”—â„¹

Wikipedia: Bernoulli Number

 procedure 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 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 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 a : Integer b : Integer
Like make-fibonacci, but makes a modular Fibonacci sequence.

Wikipedia: Farey Sequence

 procedure 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 n : Integer
Returns the nth tangent number; n must be nonnegative.

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

4.7CombinatoricsðŸ”—â„¹

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

 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

 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 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.8Special NumbersðŸ”—â„¹

4.8.1Polygonal NumbersðŸ”—â„¹

Wikipedia: Polygonal Number

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

 procedure n : Natural
 procedure(sqr n) → Natural n : Natural
 procedure n : Natural
 procedure n : Natural
 procedure n : Natural
 procedure n : Natural
These functions return the nth polygonal number of the corresponding type of polygonal number.

Wikipedia: Mediant

4.9FractionsðŸ”—â„¹

 procedure 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

 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 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 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.

'(0-1i 0+1i)

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

'(0-1i 0+1i)

Added in version 1.1 of package math-lib.

4.11The 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 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 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 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 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 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 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)