Arithmetic functions.

These functions are by definition functions whose natural domain of definition is either $\Bbb$Z (or $\Bbb$N), or sometimes polynomials over a base ring. Functions which concern polynomials exclusively will be explained in the next section. The way these functions are used is completely different from transcendental functions: in general only the types integer and polynomial are accepted as arguments.

In the present version 1.35 a primitive but useful version of the [*] method has been implemented. Also, numbers found to be pseudo-primes after 10 successful trials of the [*] test are declared primes.

bezout(x, y): finds u and v minimal in a natural sense such that x*u + y*v = gcd(x, y). The arguments must be both integers or both polynomials, and the result is a row vector with three components u, v, and gcd(x, y).

The library syntax is either $\teb$vecbezout(x, y) to get the vector, or $\teb$gbezout(x, y,&u,&v) which gives as result the address of the created gcd, and puts in u and v the addresses of the corresponding created objects.

bigomega(x): number of prime divisors of x counted with multiplicity. x must be an integer, and the result is a 32-bit C-integer.

The library syntax is $\teb$bigomega(x).

bin(x, y): [*] $\binomxy$. Here y must be an integer, but x can be any PARI object.

The library syntax is $\teb$binome(x, y).

boundcf(x, lmax): creates the row vector whose components are the partial quotients of the [*] expansion of x, the number of partial quotients being limited to lmax. If x is a real number, the expansion stops at the last significant partial quotient or after lmax terms, whichever is smallest. x can also be a rational function or a power series.

The library syntax is $\teb$gboundcf(x, lmax), where lmax is a C integer.

boundfact(x, p): For integer x, finds only the prime factors up to p or to the default bound of the prime table created upon initialization of GP, whichever is lowest (except when p < = 1 where the effect is identical to smallfact. The remaining part is hence not necessarily prime.

The library syntax is $\teb$boundfact(x, p).

cf(x): creates the row vector whose components are the partial quotients of the [*] expansion of x. If x is a real number, the expansion stops at the last significant partial quotient. x can also be a rational function.

The library syntax is $\teb$gcf(x).

cf2(b, x): creates the row vector whose components are the partial quotients of the continued fraction expansion of x, the numerators being equal to the coefficients of the vector b. The length of the result is equal to the length of b unless a partial remainder is encountered which is equal to zero, in which case the expansion stops. In the case of real numbers, the stopping criterion in thus different from that of cf since if b is too long, some partial quotients may not be significant. x can also be a rational function or a power series.

The library syntax is $\teb$gcf2(b, x).

chinese(x, y): x and y being both integermods or polymods, creates (with the same type) a z in the same residue class as x and in the same residue class as y, if it is possible.

The library syntax is $\teb$chinois(x, y).

classno(x): class number of the quadratic field of discriminant x. In the present version 1.35, a simple algorithm is used for x > 0, so x should not be too large (say x < 107) for the time to be reasonable. On the other hand, for x < 0 one can reasonably compute classno(x) for | x| < 1025, since the method used is Shanks' method which is in O(| x|1/4).

The library syntax is $\teb$classno(x).

There also exists the function [*], which computes the class number using the functional equation. However, it is in O(| x|1/2). Finally, in library mode only there exists the function [*] which computes the class number of an imaginary quadratic field by counting reduced forms, a O(| x|) algorithm. See also 3.4.14 below.

content(x): computes the gcd of all the coefficients of x, when this gcd makes sense. If x is a scalar, this simply gives x. If x is a polynomial (and by extension a power series), it gives the usual content of x. If x is a rational function, it gives the ratio of the contents of the numerator and the denominator. Finally, if x is a vector or a matrix, it gives the gcd of all the entries.

The library syntax is $\teb$content(x).

divisors(x): creates a row vector whose components are the positive divisors of the integer x in increasing order.

The library syntax is $\teb$divisors(x).

fact(x) or x!: factorial of x.

The library syntax is $\teb$mpfact(x). x must be a 32-bit C-integer and not a PARI integer.

factfq(x, p, a): factorization in the field $\Bbb$Fq defined by the irreducible polynomial a over $\Bbb$Fp of the polynomial x. The coefficients of x must be operation-compatible with $\Bbb$Z/p$\Bbb$Z. The result is a two column matrix, the first column being the irreducible polynomials dividing x, and the second the exponents. It is advised to use for the variable of a (which will be used as variable of a polymod), a name distinct from the other variables used, so that a lift() of the result will be legible.

The library syntax is $\teb$factmod9(x, p, a).

factmod(x, p): factorization mod p of the polynomial x. The coefficients of x must be operation-compatible with $\Bbb$Z/p$\Bbb$Z. The result is a two column matrix, the first column being the irreducible polynomials dividing x, and the second the exponents.

The library syntax is $\teb$factmod(x, p).

factor(x): general factorization function. If x is of type integer, rational, polynomial or rational function, the result is a two column matrix, the first column being the irreducibles dividing x (prime numbers or polynomials), and the second the exponents. If x is a vector or a matrix, the factoring is done componentwise (hence the result is a vector or matrix of two column matrices).

The polynomials or rational functions to be factored must have coefficients either integers or integermods. Note that PARI does not know how to factor multivariate polynomials.

The library syntax is $\teb$factor(x). See also [*] and [*] (see 3.6.10).

fibo(x): xth fibonacci number.

The library syntax is $\teb$fibo(x). x must be a 32-bit C-integer and not a PARI integer.

gcd(x, y): creates the greatest common divisor of x and y. x and y can be of quite general types; for instance both rational numbers. Experiment will tell you what the result in these cases will be.

The library syntax is $\teb$ggcd(x, y).

hclassno(x): [*] of x, where x is nonnegative and congruent to 0 or 3 modulo 4. See also 3.4.6 above.

The library syntax is $\teb$hclassno(x).

hilb (x, y, p) or hilbp(x, y): [*] of x and y. If x and y are of type integer or fraction, the function hilb must be used with an explicit third parameter p, p = 0 meaning the place at infinity. Otherwise, p need not be given, and x and y can be of compatible types integer, fraction, real, integermod or p-adic.

The library syntax is in both cases $\teb$hil(x, y, p) or $\teb$hil(x, y).

isfund(x): true (1) if x is equal to 1 or to the discriminant of a quadratic field, false (0) otherwise.

The library syntax is $\teb$isfundamental(x).

isprime(x): true (1) if x is a strong pseudo-prime for 10 randomly chosen bases, false (0) otherwise.

The library syntax is $\teb$isprime(x).

ispsp(x): true (1) if x is a strong pseudo-prime for a randomly chosen base, false (0) otherwise.

The library syntax is $\teb$ispsp(x).

isqrt(x): integer square root of x, which must be of PARI type integer. A negative x is allowed, and the result in that case is i*isqrt(-x).

The library syntax is $\teb$racine(x).

issqfree(x): true (1) if x is squarefree, false if not. Here x can be an integer or a polynomial.

The library syntax is $\teb$issquarefree(x).

issquare(x): true (1) if x is square, false if not.

The library syntax is $\teb$carreparfait(x).

kronecker(x, y) or kro(x, y): Kronecker Legendre symbol (i.e. generalized Legendre) symbol $\left(\vphantom{\dfrac{x}{y}}\right.$${\dfrac{{x}}{{y}}}$$\left.\vphantom{\dfrac{x}{y}}\right)$. x and y must be of type integer and the result (0 or ±1) is a 32-bit C-integer.

The library syntax is $\teb$kronecker(x, y).

lcm(x, y): least common multiple of x and y, i.e. such that lcm(x, y)*gcd(x, y) = x*y.

The library syntax is $\teb$glcm(x, y).

mu(x): Möbius μ-function of x. x must be of type integer and the result (0 or ±1) is a 32-bit C-integer.

The library syntax is $\teb$mu(x).

nextprime(x): finds the smallest prime greater than or equal to x. x must be of type integer.

The library syntax is $\teb$bigprem(x).

numdiv(x): number of divisors of x. x must be of type integer, and the result is a 32-bit C-integer.

The library syntax is $\teb$numbdiv(x).

omega(x): number of distinct prime divisors of x. x must be of type integer, and the result is a 32-bit C-integer.

The library syntax is $\teb$omega(x).

order(x): x must be an integer mod n, and the result is the order of x in the multiplicative group ($\Bbb$Z/n$\Bbb$Z)*. Error if x is not invertible.

The library syntax is $\teb$order(x).

pf(x, p): prime binary quadratic form of discriminant x whose first coefficient is the prime number p. Error if x is not a quadratic residue mod p. In the case where x > 0, the ``distance'' component of the form is set equal to zero to the current precision.

The library syntax is $\teb$primeform(x, p, prec), where the third variable prec is a C-integer, but is necessary only when x > 0.

phi(x): Euler's φ-function of x. x must be of type integer.

The library syntax is $\teb$phi(x).

pnqn(x): When x is a vector or a one row matrix, x is considered as the list of partial quotients [a0, a1,..., an] of a rational number, and the result is the 2 by 2 matrix [pn, pn-1;qn, qn-1] in the standard notation of continued fractions, so pn/qn = a0 +1/(a1 + ... +1/an)...). If x is a matrix with two rows [b0, b1,..., bn] and [a0, a1,..., an], this is then considered as a generalized continued fraction and we have similarly pn/qn = 1/b0(a0 + b1/(a1 + ... + bn/an)...). Note that in this case one usually has b0 = 1.

The library syntax is $\teb$pnqn(x).

prime(x): the xth prime number.

The library syntax is $\teb$prime(x). x must be a 32-bit C-integer.

primes(x): creates a row vector whose components are the first x prime numbers.

The library syntax is $\teb$primes(x). x must be a 32-bit C-integer.

primroot(x): returns a primitive root of x, where x is a prime power.

The library syntax is $\teb$gener(x).

qfi(a, b, c): creates the binary quadratic form ax2 + bxy + cy2 with b2 -4ac < 0.

The library syntax is $\teb$qfi(a, b, c). Binary quadratic form

qfr(a, b, c, d ): creates the binary quadratic form ax2 + bxy + cy2 with b2 -4ac > 0 and distance function d.

The library syntax is $\teb$qfr(a, b, c, d ).

regula(x): regulator of the quadratic field of positive discriminant x. Error if x is not a discriminant (fundamental or not) or if x is a square.

The library syntax is $\teb$regula(x, prec).

sigma(x): sum of the positive divisors of x. x must be of type integer.

The library syntax is $\teb$sumdiv(x).

sigmak(k, x): sum of the kth powers of the positive divisors of x. x must be of type integer, but (in library mode) k must be a 32-bit C-integer.

The library syntax is $\teb$sumdivk(k, x).

smallfact(x): For integer x, finds only the prime factors up to the default table created when GP was started (usually 500000). The remaining part is hence not necessarily prime. This never takes more than a few seconds, and is particularly advantageous with respect to factor when one needs only the small prime divisors and not the complete factorisation.

The library syntax is $\teb$smallfact(x).

unit(x): [*] of the real quadratic field $\Bbb$Q($\sqrt{x}$) where x is the positive discriminant of the field. If x is not a fundamental discriminant, this probably gives the fundamental unit of the corresponding order. x must be of type integer, and the result is a quadratic number.

The library syntax is $\teb$fundunit(x).