The module arith1 is a module for miscellaneous arithmetic functions.
Historical Note: The suffix "1" was meaningful when there was another module named arith2.
The function expand returns an m-ary expansion of an integer n. n and m should satisfy n > m > 0.
The returned value is a list. For example, expand(30, 7) returns [2, 4], which means 30 = 2 + 4*7.
The function floorpowerroot returns the floor of k-th power root of the given integer n.
The returned value is an integer.
The function floorsqrt returns the floor of square root of the given integer n.
The returned value is an integer.
The function inverse returns the inverse of x modulo n.
The returned value is an integer.
The function issquare determines whether the given integer n is a square or not.
If the number is a square number, the function returns its square root as an integer. Otherwise zero is returned.
The Legendre symbol (a / p) determines whether a is quadratic residue modulo a prime p or not. The Jacobi symbol is an extension of the Legendre symbol to arbitrary modulus m, although loosing direct connection with quadratic residue. The function legendre computes the Legendre-Jacobi symbol.
The returned value is 1, -1 or 0.
The function log returns the integer part of logarithm of the given natural number n to the given base (default to 2).
The returned value is an integer.
The function modsqrt returns one of the square root of n modulo a prime p.
The returned value is an integer.
The function vp returns p-adic valuation and indivisible part of given integer.
For example, vp(100, 2) returns (2, 25). That means, 100 is 2 times divisible by 2, and the factor 25 of 100 is indivisible by 2.
The returned value is a list.
The name crt stands for Chinese remainder theorem. The function returns a representative element of residue class, which satisfies the all given modulus conditions. The modulus conditions are given in a list like [[1, 2], [2, 3], [3, 5]], which means the number should be 1 mod 2, 2 mod 3 and 3 mod 5. All moduli must be pairwise coprime.
The returned value is an integer.