In R, the numbers package provides number-theoretic functions for factorization, prime numbers, twin primes, primitive roots, modular logarithm and inverses, extended GCD, Farey series and continuous fractions. It includes Legendre and Jacobi symbols, some divisor functions, Euler’s Phi function, etc. Although R does not have a true integer data type, integers can be represented exactly up to 253 − 1 . The numbers package attempts to provided basic number-theoretic functions that will work correcty and relatively fast up to this level. To load the package type

library(numbers)

Divisibility, Modular Arithmetic

Introduction

If a and b are integers with b ≠ 0, we say that b divides a if there exists an integer c such that a = bc. The notation b ∣ a denotes that b divides a.

Divisors

divisors(n) Generates a list of divisors of an integer number (n). The list of all divisors of an integer n will be calculated and returned in ascending order, including 1 and the number itself. For n ≥ 1000 the list of prime factors of n will be used, for smaller n a total search is applied.

Divisors of 6

divisors(6)
## [1] 1 2 3 6

Divisors of 10

divisors(10)
## [1]  1  2  5 10

Divisors of 12

divisors(12)
## [1]  1  2  3  4  6 12

Divisors of 60

divisors(60)
##  [1]  1  2  3  4  5  6 10 12 15 20 30 60

mod

mod(n, m) is the modulo operator and returns n mod m.

mod(13,2)
## [1] 1

rem(n, m) is the same as the modulo operator and returns n mod m.

rem(13,2)
## [1] 1

GCD & LCM

The functions generate the greatest common divisor and least common multiple of integers. Computation is based on the Euclidean algorithm.

greatest common divisor of 341 and 527

GCD(341,527)
## [1] 31

least common multiple of 341 and 527

LCM(341,527)
## [1] 5797

Primes, Congruences

Introduction

An integer p greater than 1 is called prime if the only positive factors of p are 1 and p. A positive integer that is greater than 1 and is not prime is called composite.

Primes

Primes(n) uses the sieve of Eratosthenes to generate a list of prime numbers less or equal n. This approach is reasonably fast, but may require a lot of main memory when n is large. In double precision arithmetic integers are represented exactly only up to 253 − 1, therefore this is the maximal allowed value.

Primes(100)
##  [1]  2  3  5  7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

Prime Factors

primeFactors(n) computes a vector containing the prime factors of an integer n.

Prime factors of 88

primeFactors(88)
## [1]  2  2  2 11

Trevor. N. Mutusva, February 2020.