Wolfram Cloud Document

Number Theory

Number theory is one of the oldest and most intuitive fields of mathematics. It studies integers and their properties.

“Mathematics is the queen of sciences and arithmetic the queen of mathematics.”— Carl Friedrich Gauss

Packing a large number of sophisticated algorithms, many recent and original, into a powerful collection of functions, Wolfram Language draws on almost every major result in number theory.

A key tool for two decades in the advance of the field, Wolfram Language’s symbolic architecture and web of highly efficient algorithms make it a unique platform for number theoretic experiments, discoveries and proofs.

Factoring & primes

Divisibility & divisors

Congruences & modular arithmetic

Number representations

Diophantine & other equations

Analytic number theory

Algebraic number theory

Factoring & Primes

“God may not play dice with the universe, but something strange is going on with the prime numbers.”—Paul Erdos

The primes have been a focal point for investigations of numbers for more than two millennia.

Wolfram Language implements state-of-the-art algorithms for handling both primes and the advanced mathematics that has grown up around their study.

Generating Primes

◼

Prime gives the

prime number.

Use it to quickly find the millionth prime:

In[]:=

Prime[10^6]

Out[]=

15485863

◼

NextPrime gives the smallest prime above

Find the next prime after 1000:

In[]:=

NextPrime[1000]

Out[]=

1009

Visualize the gaps between primes below

In[]:=

Histogram[Table[NextPrime[s]-NextPrime[s,-1],{s,10^4}]]

Out[]=

In[]:=

NextPrime[1000,-1]

Out[]=

997

◼

The function RandomPrime gives a pseudorandom prime number in the given range.

A random 10-digit prime:

In[]:=

RandomPrime[{10^9,10^10}]

Out[]=

8270303057

◼

The function MersennePrimeExponent gives the

Mersenne prime exponent.

A Mersenne prime exponent is a prime number

for which the Mersenne number

-1

is prime.

Here are the first 10 Mersenne prime exponents:

In[]:=

Table[MersennePrimeExponent[n],{n,10}]

Out[]=

{2,3,5,7,13,17,19,31,61,89}

Sequence of Primes

◼

The function PrimePi gives the number of primes

π(x)

less than or equal to

Compute the number of primes up to

Generate a path based on the PrimePi function:

Plot over a subset of the reals:

Plot over a subset of the complexes:

Other functions: ZetaZero, LogIntegral, RiemannR, RiemannSiegelZ, PrimeZetaP

Primality Testing

◼

PrimeQ is used to test whether an integer is a prime number.

Test whether 119 is prime or not:

Similarly, CompositeQ is used to test whether an integer is a composite number.

Test whether 149 is composite or not:

◼

CoprimeQ is used to test whether two numbers are relatively prime.

Two integers are called relatively prime (mutually prime, coprime) when the only positive integer that can be used to divide both of them is 1.

Test whether two numbers are relatively prime:

Integers are relatively prime if their greatest common divisor is 1.

◼

MersennePrimeExponentQ is used to test whether an integer is a Mersenne prime exponent.

Test whether 5 is a Mersenne prime exponent:

Check:

Highlight Mersenne prime exponents:

◼

PrimePowerQ is used to test whether a number is a power of a prime number.

Test whether 9 is a power of a prime number:

Recognize Mersenne numbers:

Theorems & Equations

◼

Primes represents the domain of prime numbers.

◼

You can use Reduce to reduce expressions over the primes, or FullSimplify to simplify assuming numbers are prime.

Wilson's theorem:

◼

The function FindInstance can be used to find solutions over the primes.

Factoring & Primes

The prime factorization of integers is one of the most important results in number theory. It says that every natural number can be written uniquely as a product of primes.

The unique factorization is needed to establish much of what comes later. It gives an alternative, conceptually simpler way to find a lot of numerical characteristics of a number.

Factoring

◼

FactorInteger gives a list of the prime factors of an integer, together with their exponents.

Compute for large integers:

Every integer is a prime or a product of primes.

The number of trailing zeros:

◼

SquareFreeQ is used to test whether a number or a polynomial is square free.

Test whether 10 is square free:

Check:

Factoring-Related Functions

Compute PrimeNu for 24:

Compute PrimeOmega for 24:

Check:

Compute the Liouville function at 8:

Compute the Mangoldt function at 25:

Plot the MangoldtLambda sequence for the first 100 numbers:

Another function: MoebiusMu

Divisibility & Divisors

Divisibility is one of the key notions in number theory.

Divisibility

Test whether a number is divisible by 19:

Highlight numbers divisible by 3:

◼

GCD gives the greatest common divisor of numbers, and LCM gives the least common multiple of numbers.

Find the GCD and LCM of two numbers:

Other functions: CoprimeQ, ExtendedGCD, ModularInverse, MoebiusMu, JacobiSymbol, KroneckerSymbol

Divisibility & Divisors

Divisors

The divisors of 1729:

Compare the following plots:

Other functions: DedekindEta, EllipticTheta

Congruences & Modular Arithmetic

Congruences are of great practical importance in both number theory and everyday life.

The theory of congruences was introduced by Gauss. He created a new branch of number theory by introducing a remarkable notation.

Congruences satisfy a number of important properties and are extremely useful in many areas of number theory.

Functions Related to Congruences & Modular Arithmetic

Plot the sequence with fixed modulus:

◼

PowerMod is known as modular exponentiation.

Plot the sequence with a fixed modulus:

Other functions: MultiplicativeOrder, PrimitiveRoot, ChineseRemainder, PowerModList, CarmichaelLambda, PrimitivePolynomialQ

Diophantine & Other Equations

Functions Related to Diophantine & Other Equations

◼

Integers represents the domain of integers.

◼

You can use Reduce to reduce expressions.

Find a Pythagorean triple:

◼

You can use FindInstance to find solutions of Diophantine equations.

A linear Diophantine equation in two variables is an equation of the form

Geometrically, a linear Diophantine equation gives a line.

The solutions to this equation are the integer points that are on the line:

Other functions: Element, Rationals, Reals, Algebraic, Primes

Number Representations

DigitRepresentations

Wolfram Language can handle numbers of essentially unlimited length, in any base, using state-of-the-art platform-optimized algorithms, including several developed at Wolfram Research.

For rational numbers, it uses number theoretic methods to efficiently find the exact forms of repeating digit sequences.

◼

FromDigits constructs an integer from a list of decimal digits.

You can also use symbolic digits and base:

A binary integer:

Expansions in different bases can be terminating or non-terminating for the same number:

Decompose an amount of money in different denominations:

Decompose an amount of seconds in days, hours, minutes and seconds:

Other functions: RealDigits, IntegerReverse, IntegerPart, IntegerName

Continued Fractions & Rational Approximations

A continued fraction is an expression obtained through an iterative process of representing a number as the sum of its integer part and the reciprocal of another number, then writing this other number as the sum of its integer part and another reciprocal and so on.

Wolfram Language has highly efficient original algorithms for finding large numbers of terms in continued fractions, as well as for handling exact continued fractions for quadratic irrationals.

Rational number:

◼

Convergents gives a list of the convergents corresponding to the continued fraction terms list.

Give all convergents for a rational number:

You can see that they tend to the number.

◼

Khinchin is Khinchin’s constant.

Other functions: Rationalize, QuadraticIrrationalQ, ContinunedFractionK

Number Representations

Representations as Sums of Powers

Another function: EllipticTheta

Partitions

All partitions of 5:

Analytic Number Theory

Analytic number theory is a branch of number theory that uses methods from mathematical analysis to solve problems about the integers.

Analytic number theory can be split up into two major parts, divided more by the types of problems they attempt to solve than fundamental differences in technique:

◼

Multiplicative number theory

◼

Additive number theory

Building on its broad strengths in mathematics in general and in special functions in particular, Wolfram Language provides a unique level of support for analytic number theory, including not only highly general function evaluation but also symbolic simplification.

Multiplicative Number Theory

Multiplicative number theory is a subfield of analytic number theory that deals with prime numbers and with factorization and divisors. The focus is usually on developing approximate formulas for counting these objects in various contexts.

Zeta Functions

Wolfram Language supports zeta and polylogarithm functions of a complex variable in full generality, performing efficient arbitrary-precision evaluation and implementing extensive symbolic transformations.

Other functions: Zeta, RiemannSiegelZ, RiemannSiegelTheta, StieltjesGamma, RiemannXi, PolyLog, LerchPhi, HurwitzZeta, HurwitzLerchPhi, DirichletBeta, DirichletEta, DirichletLambda, PrimeZetaP

Dirichlet Series

For example,

Another function: DirichetL

Arithmetic Functions

◼

MoebiusMu gives the Moebius function μ(n), which is defined as follows:

Other functions: Divisors, DivisorSigma, EulerPhi

Prime Numbers

Plot PrimePi compared with estimates:

Other functions: PrimeNu, PrimeOmega, Prime, LiouvilleLambda, MangoldtLambda

Perfect Numbers

A perfect number is a positive integer that is equal to the sum of its positive divisors, excluding the number itself.

28 is a perfect number:

Here is the plot of the length of the first 47 even perfect numbers, with log-scaled values:

There is a peculiar connection between perfect numbers and Mersenne primes.

The following is the table of the first 8 Mersenne primes and corresponding perfect numbers:

Other functions: MersennePrimeExponent, MersennePrimeExponentQ

Operations

DivisorSum, DirichletConvolve, Sum, Product, Integrate, Series, Limit

Additive Number Theory

Additive number theory is the subfield of number theory concerning the study of subsets of integers and their behavior under addition.

Integer Partitions

IntegerPartitions, PartitionsP, PartitionsQ

Base-like Representations

IntegerDigits, MixedRadix, NumberDecompose

Representation in Terms of Powers

PowersRepresentations, SquaresR , FrobeniusNumber , FrobeniusSolve, Reduce, Solve

Summation-Related Operations

Sum, Product, DirichletConvolve, DivisorSum, DiscreteConvolve

Arithmetic Functions

PrimeOmega, PrimeNu, Mod, EulerPhi, MoebiusMu, DivisorSigma

Algebraic Number Theory

Algebraic number theory is a branch of number theory that uses the techniques of abstract algebra to study the integers, rational numbers and their generalizations.

With its convenient symbolic representation of algebraic numbers, Wolfram Language’s state-of-the-art algebraic number theory capabilities provide a concrete implementation of one of the historically richest areas of pure mathematics—all tightly integrated with Wolfram Language’s powerful unified environment.