On this page:
4.1 Congruences and Modular Arithmetic
divides?
bezout
coprime?
pairwise-coprime?
solve-chinese
quadratic-residue?
quadratic-character
jacobi-symbol
modular-inverse
modular-expt
4.1.1 Parameterized Modular Arithmetic
with-modulus
current-modulus
mod
mod+
mod*
modsqr
modexpt
mod-
mod/
mod=
mod<
mod<=
mod>
mod>=
4.2 Primes
prime?
odd-prime?
nth-prime
random-prime
next-prime
prev-prime
next-primes
prev-primes
factorize
defactorize
divisors
prime-divisors
prime-exponents
4.3 Roots
integer-root
integer-root/  remainder
4.4 Powers
max-dividing-power
perfect-power
perfect-power?
prime-power
prime-power?
odd-prime-power?
as-power
perfect-square
4.5 Multiplicative and Arithmetic Functions
totient
moebius-mu
divisor-sum
prime-omega
mangoldt-lambda
4.6 Number Sequences
bernoulli-number
eulerian-number
fibonacci
make-fibonacci
modular-fibonacci
make-modular-fibonacci
farey-sequence
tangent-number
4.7 Combinatorics
factorial
binomial
permutations
multinomial
partitions
4.8 Special Numbers
4.8.1 Polygonal Numbers
triangle-number?
square-number?
pentagonal-number?
hexagonal-number?
heptagonal-number?
octagonal-number?
triangle-number
sqr
pentagonal-number
hexagonal-number
heptagonal-number
octagonal-number
4.9 Fractions
mediant
4.10 The Quadratic Equation
quadratic-solutions
quadratic-integer-solutions
quadratic-natural-solutions
4.11 The group Zn and Primitive Roots
unit-group
unit-group-order
unit-group-orders
primitive-root?
exists-primitive-root?
primitive-root
primitive-roots
6.11

4 Number Theory

Jens Axel Søgaard <[email protected]>

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

    4.1 Congruences and Modular Arithmetic

      4.1.1 Parameterized 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.8.1 Polygonal Numbers

    4.9 Fractions

    4.10 The Quadratic Equation

    4.11 The group Zn and Primitive Roots

4.1 Congruences 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 xk)

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

(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

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, and the exponent b must be nonnegative.

Examples:
> (modulo (expt -6 523) 19)

13

> (modular-expt -6 523 19)

13

> (modular-expt 9 158235208 19)

4

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

Returns the current modulus.

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)

2

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

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.

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

(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

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

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

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

'()

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.

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.

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.

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)