Computational Number Theory in the Modern World

Lusine Sukiasyan, Wolfram Research

(RowDefault[, (Spacer1), , (Spacer1), ])  #WolframTechConf

Overview

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

Factoring & primes

Divisibility & divisors

Congruences & modular arithmetic

Number representations

Diophantine & other equations

Analytic number theory

Algebraic number theory

Factoring & Primes

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

Generating Primes

Prime gives the (n^th) prime number.

Use it to quickly find the millionth prime:

Prime[10^6]

NextPrime gives the smallest prime above x.

Find the next prime after 1000:

NextPrime[1000]

Visualize the gaps between primes below (10^4):

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

NextPrime[1000,-1]

The function MersennePrimeExponent gives the  (n^th) Mersenne prime exponent.

A Mersenne prime exponent is a prime number p for which the Mersenne number (2^p)-1 is prime.

Here are the first 10 Mersenne prime exponents:

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

Another function: RandomPrime

Sequence of Primes

The function PrimePi gives the number of primes π(x) less than or equal to x.

Compute the number of primes up to (10^10):

PrimePi[10^10]

The function Zeta gives the Riemann zeta function ζ(s), defined as

({{ζ(s)=({{1+(2^(-s))+(3^(-s))+(4^(-s))+...}})}})

Plot over a subset of the reals:

Plot[Zeta[x],{x,-4,4}]

Plot over a subset of the complexes:

ComplexPlot3D[Zeta[z],{z,-2-2 I,2+2 I},PlotLegends->Automatic]

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:

PrimeQ[119]

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

Test whether 149 is composite or not:

CompositeQ[149]

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

Test whether 5 is a Mersenne prime exponent:

MersennePrimeExponentQ[5]

Check:

2^5-1

PrimeQ[31]

Highlight Mersenne prime exponents:

Multicolumn[If[MersennePrimeExponentQ[#],Style[#,Red,Bold],#]&/@Range[100],10,]

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:

PrimePowerQ[9]

Recognize Mersenne numbers:

mersenneQ[n_]:=EvenQ[n+1]&&PrimePowerQ[n+1];

The number 2147483647 is a Mersenne number, while 524285 is not:

mersenneQ[2147483647]

mersenneQ[524285]

Another function: CoprimeQ

Factoring & Primes

The prime factorization of integers says that every natural number can be written uniquely as a product of primes.

Factoring

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

Find prime factors of 120 and their exponents:

FactorInteger[120]

2^3*3*5

Compute for large integers:

FactorInteger[10^50+3]

Every integer is a prime or a product of primes.

Manipulate[If[PrimePowerQ[n],First[Superscript@@@FactorInteger[n]],CenterDot@@(Superscript@@@FactorInteger[n])],{{n,2,Style["Random Integer",18]},Button[Style[n,24],n=RandomInteger[100000]]&},ImageMargins->Large,FrameMargins->Large, BaseStyle->24]

IntegerExponent[n,b] gives the highest power of b that divides n.

The number of trailing zeros:

IntegerExponent[1230000,10]

Powers of 2 in successive integers:

ListPlot[IntegerExponent[Range[256],2]]

Another function: SquareFreeQ

Factoring-Related Functions

PrimeNu and PrimeOmega are the prime omega functions. The prime omega functions ω(n) and Ω(n) count the number of prime factors of a natural number n.

PrimeNu counts the number of distinct primes of n.

If ({{n=}})(Subscript[p, 1]^(Subscript[k, 1]))(Subscript[p, 2]^(Subscript[k, 2]))...(Subscript[p, m]^(Subscript[k, m])), then

({{({{ω(n)=m}})}})

Compute PrimeNu for 24:

PrimeNu[24]

PrimeOmega counts the total number of prime factors of n, taking into account their multiplicity.

So, if ({{n=}})(Subscript[p, 1]^(Subscript[k, 1]))(Subscript[p, 2]^(Subscript[k, 2]))...(Subscript[p, m]^(Subscript[k, m])), then

({{({{Ω(n)=(Subscript[k, 1])+...+(Subscript[k, m])}})}})

Compute PrimeOmega for 24:

PrimeOmega[24]

Check:

FactorInteger[24]

LiouvilleLambda gives the Liouville function λ(n), which is defined as follows:

If ({{n=}})(Subscript[p, 1]^(Subscript[k, 1]))(Subscript[p, 2]^(Subscript[k, 2]))...(Subscript[p, m]^(Subscript[k, m])), then

({{({{λ(n)=(((-1))^((Subscript[k, 1])+...+(Subscript[k, m])))}})}})

So it only takes two values: -1 and 1.

Grid[Flatten/@{{"n",Range[10]},{"λ(n)",Table[LiouvilleLambda[n],{n,10}]}},]

Compute the Liouville function at 8:

LiouvilleLambda[8]

Plot the LiouvilleLambda sequence for the first 50 numbers:

DiscretePlot[LiouvilleLambda[n],{n,50},]

Other functions: MoebiusMu, MangoldtLambda

Divisibility & Divisors

Divisibility is one of the key notions in number theory.

The number d divides the number n if there exists an integer k such that

({{({{({{n=d*k}})}})}})

n is a divisor of d, and d is a multiple of n.

Divisibility

Divisible yields True if n is divisible by m and yields False if it is not.

Test whether a number is divisible by 19:

Divisible[437,19]

437/19

(4^n)+(5^n)+(6^n) is divisible by 15, where n is an odd integer:

AllTrue[Table[4^n+5^n+6^n,{n,1,100,2}],Divisible[#,15]&]

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:

GCD[4,18]

LCM[4,18]

EulerPhi gives the Euler totient function ϕ(n), which gives the number of positive integers up to some integer n that are relatively prime to n.

Compute the Euler totient function of 10:

EulerPhi[10]

For any prime number p and natural number r, ϕ((p^r))=(p^r)-(p^(r-1)):

Assuming[p∈Primes&&r∈Integers&&r>0,FunctionExpand[EulerPhi[p^r]]]

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

Divisibility & Divisors

b is a divisor of a if there exists an integer k such that

({{({{({{a=k*b}})}})}})

Divisors

Divisors gives a list of the integers that divide n.

The divisors of 1729:

Divisors[1729]

1729/{1,7,13,19,91,133,247,1729}

DivisorSigma gives the divisor function (Subscript[σ, k])(n), which is the sum of the k(^th) powers of the integer n.

The sum of divisors of 20:

DivisorSigma[1,20]

The sum of squares of divisors of 20:

DivisorSigma[2,20]

Compare the following plots:

DiscretePlot[{DivisorSigma[0,n],DivisorSigma[1,n],DivisorSigma[2,n]},{n,50},]

DivisorSum represents the sum of form[i] for all i that divide n.

DivisorSum[x,f]//TraditionalForm

The sum of squares of divisors of 20:

DivisorSum[20,#^2&]

Other functions: DedekindEta, EllipticTheta

Congruences & Modular Arithmetic

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

Functions Related to Congruences & Modular Arithmetic

Mod gives the remainder on division of m by n.

Compute 5 mod 3:

Mod[5,3]

Plot the sequence with fixed modulus:

DiscretePlot[Mod[n,8],{n,50}]

PowerMod is known as modular exponentiation.

PowerMod[a,b,m] gives (a^b) mod m .

Compute (2^10)mod 3:

PowerMod[2,10,3]

ModularInverse gives the modular inverse of k modulo n.

Compute the inverse of 3 modulo 5:

ModularInverse[3,5]

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

Diophantine & Other Equations

A Diophantine equation is a polynomial equation, usually in two or more unknowns, such that only the integer solutions are sought or studied.

Functions Related to Diophantine & Other Equations

Integers represents the domain of integers.

The number 7 is an integer:

Element[7,Integers]

You can use Reduce to reduce expressions.

Find a Pythagorean triple:

Reduce[x^2+y^2==5^2&&y>x>0,{x,y},Integers]

You can use FindInstance to find solutions of Diophantine equations.

FindInstance[2 x+3 y-5 z==1&&3 x-4 y+7 z==3,{x,y,z},Integers]

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

({{a*x+b*y=c}})

Manipulate[
With[{solutions=If[b===0&&a!=0,If[IntegerQ[c/a],{c/a,#}&/@Range[-zoom,zoom],{}],If[b!=0,{#,(c-a #)/b}&/@Select[Range[-zoom,zoom],IntegerQ[(c-a #)/b]&],{}]]},Plot[If[b===0,None,(c-a x)/b],{x,-zoom,zoom},Frame->True,GridLines->{Range[-zoom,zoom],Range[-zoom,zoom]},AspectRatio->Automatic,GridLinesStyle->Directive[LightGray,Thin],PlotRange->{{-zoom,zoom},{-zoom,zoom}},ImageSize->300,Epilog->{If[b===0&&a!=0,{Blue,Line[{{c/a,-zoom},{c/a,zoom}}]},{}],Red,PointSize[0.08/Sqrt[zoom]],Tooltip[Point[#],Text["("~~ToString[First[#]]~~", "~~ToString[Last[#]]~~")"]]&/@solutions},PlotLabel->If[a===0&&b===0,Row[{Style["a",Italic]," and ",Style["b",Italic]," cannot be zero simultaneously."}],TraditionalForm[a x+b y==c]],ImagePadding->20]],
{a,-10,10,1,Appearance->"Labeled"},
{b,-10,10,1,Appearance->"Labeled"},
{c,-40,40,1,Appearance->"Labeled"},Delimiter,
{zoom,10,50,1},ControlPlacement->Right]

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

Number Representations

DigitRepresentations

IntegerDigits: IntegerDigits[n] gives a list of the decimal digits in the integer n, and IntegerDigits[n,b] gives a list of the base b digits in the integer n.

Find digits in base 10 and 2:

IntegerDigits[58127]

IntegerDigits[58127,2]

FromDigits constructs an integer from a list of decimal digits.

Construct a number from its base-10 digits:

FromDigits[{5,1,2,8}]

You can also use symbolic digits and base:

Expand[FromDigits[{a,b,c,d,e},x]]

BaseForm[expr,n] prints with the numbers in expr given in base n.

A binary integer:

BaseForm[33,2]

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

Table[BaseForm[1/2.,i],{i,2,10}]//TableForm

Other functions: NumberDecompose, 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.

ContinuedFraction[x,n] generates a list of the first n terms in the continued fraction representation of x. FromContinuedFraction reconstructs a number from a list of continued fraction terms.

Find 20 terms in the continued fraction for π:

ContinuedFraction[Pi,20]

Rational number:

ContinuedFraction[47/17]

FromContinuedFraction[%]

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

Give all convergents for a rational number:

Convergents[272/105]

You can see that they tend to the number.

ListLinePlot[Convergents[272/105],Prolog -> {Gray, N[Line[{{0, 272/105}, {10,272/105}}]]},]

Khinchin is Khinchin’s constant.

N[Khinchin]

For almost all real numbers x, terms (Subscript[a, i]) of the continued fraction expansion of x have a finite geometric mean that is independent of the value of x, known as Khinchin’s constant.

({{(Underscript[({{lim}}), n->∞])((((Subscript[a, 0])(Subscript[a, 1])...(Subscript[a, n])))^(1/n))=(Subscript[K, 0])≈2.6854520010...}})

In the plot below, Khinchin’s constant is the red line, and you can see that ((((Subscript[a, 0])(Subscript[a, 1])...(Subscript[a, n])))^(1/n)) indeed, almost for all the numbers, tends to the red line:

Manipulate[ListPlot[Table[GeometricMean[ContinuedFraction[a,k]],{k,1000}],Prolog -> {Red, N[Line[{{0, Khinchin}, {1000, Khinchin}}]]},PlotRange -> {All, {0, 4}}, PlotLabel -> Style[a, 10],ImageSize -> Medium],{a,{Pi,Log[5],GoldenRatio,Sqrt[2],5^(1/3),
Pi^Pi,E^Pi,Pi^E,E^E}}]

Other functions: Rationalize, QuadraticIrrationalQ, ContinunedFractionK

Number Representations

Representations as Sums of Powers

SquaresR[d,n] gives the number of ways to represent the integer n as a sum of d squares.

Number of ways to represent 45 as a sum of two squares:

SquaresR[2,45]

PowersRepresentations[n,k,p] gives the distinct representations of the integer n as a sum of k non-negative (p^th) integer powers.

Find representations of 1729 as a sum of two cubes:

PowersRepresentations[1729,2,3]

1^3+12^3

9^3+10^3

Another function: EllipticTheta

Partitions

IntegerPartitions[n] gives a list of all possible ways to partition the integer n into smaller integers.

All partitions of 5:

IntegerPartitions[5]

PartitionsP[n] gives the number p(n) of unrestricted partitions of the integer n, while PartitionsQ[n] gives the number q(n) of partitions of the integer n into distinct parts:

PartitionsP[20]

PartitionsQ[20]

Analytic Number Theory

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

Multiplicative number theory

Additive number theory

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

ZetaZero[k] represents the (k^th) zero of the Riemann zeta function on the critical line.

Visualize the first 10 zeros:

Plot[{Im[Zeta[1/2+I t]],Re[Zeta[1/2+I t]]},{t,0,50},Epilog->{PointSize[.02],Red,Point[Table[{Im[ZetaZero[n]],0},{n,10}]]}]

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

Dirichlet Series

DirichletTransform[expr,n,s] gives the Dirichlet transform of expr with respect to n. The Dirichlet transform for a discrete function is given by

({{(∑_(n=1)^∞)f(n) (n^(-s))}})

For example,

DirichletTransform[1,n,s]

DirichletTransform[1/2^n,n,s]

Another function: DirichetL

Arithmetic Functions

In number theory, an arithmetic function is any function f(n) whose domain is the positive integers and whose range is a subset of the complex numbers.

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

If n>1, write ({{n=}})(Subscript[p, 1]^(Subscript[k, 1]))(Subscript[p, 2]^(Subscript[k, 2]))...(Subscript[p, m]^(Subscript[k, m])). Then

({{({{μ(n)}})=(((-1))^m), if (Subscript[k, 1])=(Subscript[k, 2])=...=(Subscript[k, m])=1
({{μ(n)}})=0 otherwise}})

So it takes three values: -1, 0 and 1:

Grid[Flatten/@{{"n",Range[10]},{"({{μ(n)}})",Table[MoebiusMu[n],{n,10}]}},]

Other functions: Divisors, DivisorSigma, EulerPhi

Prime Numbers

The function PrimePi[x] gives the number of primes π(x) less than or equal to x.

Plot PrimePi compared with estimates:

Plot[{PrimePi[x],x/Log[x],LogIntegral[x],RiemannR[x]},{x,1.5,100},]

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

Perfect Numbers

PerfectNumber[n] gives the (n^th) perfect number, and PerfectNumberQ tests whether a number is perfect.

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:

DivisorSigma[1,28]-28

The first 10 perfect numbers:

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

PerfectNumberQ/@{6,28,496,8128,33550336,8589869056,137438691328,2305843008139952128,2658455991569831744654692615953842176,191561942608236107294793378084303638130997321548169216}

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

ListPlot[IntegerLength[PerfectNumber[Range[47],"Even"]],ScalingFunctions->"Log",]

Other functions: MersennePrimeExponent, MersennePrimeExponentQ

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.

Algebraic Numbers and Representation

AlgebraicNumber is an algebraic number represented in a particular field.

Represent an algebraic number:

AlgebraicNumber[Root[#^3+#+1&,3],{1,2,1}]

Do arithmetic:

1+%^2

Get a numerical approximation:

N[%]

Other functions: Root, RootApproximant, IsolatingInterval, MinimalPolynomial, AlgebraicNumberPolynomial

Algebraic Number Fields

ToNumberField finds a common field or expresses numbers in a given field.

Express (Sqrt[2]) in the number field generated by (2^(1/4)):

ToNumberField[Sqrt[2],2^(1/4)]

Other functions: NumberFieldIntegralBasis, NumberFieldClassNumber, NumberFieldDiscriminant, NumberFieldRegulator, NumberFieldSignature, NumberFieldNormRepresentatives, NumberFieldFundamentalUnits, NumberFieldRootsOfUnity

Factorization

GaussianIntegers allows factorization over Gaussian integers.

Factor 36 over Gaussian integers:

FactorInteger[36,GaussianIntegers->True]

Compare:

FactorInteger[36]

Other functions: FactorInteger, Factor

Other

Extension is a field extension for number theoretic and polynomial operations.

Factor a polynomial over Q[(Sqrt[2])]:

Factor[x^2-2,Extension->Sqrt[2]]

RootReduce reduces an algebraic number to minimal root form.

RootReduce[Sqrt[2]+Sqrt[3]]

Another function: ToRadicals

What Is Next?

Functionality

Courses, books, ...

Documentation