24.2 Elements of the ring $ \mathbf{Z}$ of integers

Module: sage.rings.integer

Elements of the ring $ \mathbf{Z}$ of integers

Author: William Stein (2005): initial version

- Gonzalo Tornaria (2006-03-02): vastly improved python/GMP conversion; hashing - Didier Deshommes <dfdeshom@gmail.com> (2006-03-06): numerous examples and docstrings - William Stein (2006-03-31): changes to reflect GMP bug fixes - William Stein (2006-04-14): added GMP factorial method (since it's now very fast). - David Harvey (2006-09-15): added nth_root, exact_log - David Harvey (2006-09-16): attempt to optimise Integer constructor - Rishikesh (2007-02-25): changed quo_rem so that the rem is positive - David Harvey, Martin Albrecht, Robert Bradshaw (2007-03-01): optimized Integer constructor and pool - Pablo De Napoli (2007-04-01): multiplicative_order should return +infinity for non zero numbers - Robert Bradshaw (2007-04-12): is_perfect_power, Jacobi symbol (with Kronecker extension). Convert some methods to use GMP directly rather than pari, Integer() -> PY_NEW(Integer) - David Roe (2007-03-21): sped up valuation and is_square, added val_unit, is_power, is_power_of and divide_knowing_divisible_by - Robert Bradshaw (2008-03-26): gamma function, multifactorials

Add 2 integers:

sage: a = Integer(3) ; b = Integer(4)
sage: a + b == 7
True

Add an integer and a real number:

sage: a + 4.0
7.00000000000000

Add an integer and a rational number:

sage: a + Rational(2)/5
17/5

Add an integer and a complex number:

sage: b = ComplexField().0 + 1.5
sage: loads((a+b).dumps()) == a+b
True

sage: z = 32
sage: -z
-32
sage: z = 0; -z
0
sage: z = -0; -z
0
sage: z = -1; -z
1

Multiplication:

sage: a = Integer(3) ; b = Integer(4)
sage: a * b == 12
True
sage: loads((a * 4.0).dumps()) == a*b
True
sage: a * Rational(2)/5
6/5

sage: list([2,3]) * 4
[2, 3, 2, 3, 2, 3, 2, 3]

sage: 'sage'*Integer(3)
'sagesagesage'

COERCIONS: Returns version of this integer in the multi-precision floating real field R.

sage: n = 9390823
sage: RR = RealField(200)
sage: RR(n)
9.3908230000000000000000000000000000000000000000000000000000e6

Module-level Functions

GCD_list( )

Return the GCD of a list v of integers. Element of v is converted to a SAGE integer if it isn't one already.

This function is used, e.g., by rings/arith.py

Input:

v
- list or tuple

Output: integer

sage: from sage.rings.integer import GCD_list
sage: w = GCD_list([3,9,30]); w
3
sage: type(w)
<type 'sage.rings.integer.Integer'>

The inputs are converted to SAGE integers.

sage: w = GCD_list([int(3), int(9), '30']); w
3
sage: type(w)
<type 'sage.rings.integer.Integer'>

LCM_list( )

Return the LCM of a list v of integers. Element of v is converted to a SAGE integer if it isn't one already.

This function is used, e.g., by rings/arith.py

Input:

v
- list or tuple

Output: integer

sage: from sage.rings.integer import LCM_list
sage: w = LCM_list([3,9,30]); w
90
sage: type(w)
<type 'sage.rings.integer.Integer'>

The inputs are converted to SAGE integers.

sage: w = LCM_list([int(3), int(9), '30']); w
90
sage: type(w)
<type 'sage.rings.integer.Integer'>

clear_mpz_globals( )

free_integer_pool( )

gmp_randrange( )

init_mpz_globals( )

is_Integer( )

Return true if x is of the SAGE integer type.

sage: is_Integer(2)
True
sage: is_Integer(2/1)
False
sage: is_Integer(int(2))
False
sage: is_Integer(long(2))
False
sage: is_Integer('5')
False

make_integer( )

Create a SAGE integer from the base-32 Python *string* s. This is used in unpickling integers.

sage: from sage.rings.integer import make_integer
sage: make_integer('-29')
-73
sage: make_integer(29)
Traceback (most recent call last):
...
TypeError: expected string or Unicode object, sage.rings.integer.Integer
found

parent( )

Class: int_to_Z

class int_to_Z

Special Functions: __init__,$ \,$ _repr_type

_repr_type( )

Class: Integer

class Integer
The Integer class represents arbitrary precision integers. It derives from the Element class, so integers can be used as ring elements anywhere in SAGE.

Integer() interprets numbers and strings that begin with 0 as octal numbers, and numbers and strings that begin with 0x as hexadecimal numbers.

Note: The class Integer is implemented in Pyrex, as a wrapper of the GMP mpz_t integer type.

sage: Integer(010)
8
sage: Integer(0x10)
16
sage: Integer(10)
10
sage: Integer('0x12')
18
sage: Integer('012')
10
Integer( )

You can create an integer from an int, long, string literal, or integer modulo N.

sage: Integer(495)
495
sage: Integer('495949209809328523')
495949209809328523
sage: Integer(Mod(3,7))
3
sage: 2^3
8

Functions: additive_order,$ \,$ binary,$ \,$ bits,$ \,$ ceil,$ \,$ coprime_integers,$ \,$ crt,$ \,$ denominator,$ \,$ digits,$ \,$ divide_knowing_divisible_by,$ \,$ divides,$ \,$ divisors,$ \,$ exact_log,$ \,$ factor,$ \,$ factorial,$ \,$ floor,$ \,$ gamma,$ \,$ gcd,$ \,$ inverse_mod,$ \,$ inverse_of_unit,$ \,$ is_integral,$ \,$ is_irreducible,$ \,$ is_one,$ \,$ is_perfect_power,$ \,$ is_power,$ \,$ is_power_of,$ \,$ is_prime,$ \,$ is_prime_power,$ \,$ is_pseudoprime,$ \,$ is_square,$ \,$ is_squarefree,$ \,$ is_unit,$ \,$ isqrt,$ \,$ jacobi,$ \,$ kronecker,$ \,$ list,$ \,$ multifactorial,$ \,$ multiplicative_order,$ \,$ ndigits,$ \,$ next_prime,$ \,$ next_probable_prime,$ \,$ nth_root,$ \,$ numerator,$ \,$ ord,$ \,$ powermod,$ \,$ powermodm_ui,$ \,$ prime_divisors,$ \,$ prime_factors,$ \,$ prime_to_m_part,$ \,$ quo_rem,$ \,$ radical,$ \,$ rational_reconstruction,$ \,$ sqrt,$ \,$ sqrt_approx,$ \,$ squarefree_part,$ \,$ str,$ \,$ val_unit,$ \,$ valuation

additive_order( )

Return the additive order of self.

sage: ZZ(0).additive_order()
1
sage: ZZ(1).additive_order()
+Infinity

binary( )

Return the binary digits of self as a string.

sage: print Integer(15).binary()
1111
sage: print Integer(16).binary()
10000
sage: print Integer(16938402384092843092843098243).binary()
110110101110110001111000111001001010011101000110101000111111100010100000000
0101111000010000011

bits( )

Return the number of bits in self.

sage: 500.bits()
9
sage: 5.bits()
3
sage: 12345.bits() == len(12345.binary())
True

ceil( )

Return the ceiling of self, which is self since self is an integer.

sage: n = 6
sage: n.ceil()
6

coprime_integers( )

Return the positive integers $ < m$ that are coprime to self.

sage: n = 8
sage: n.coprime_integers(8)
[1, 3, 5, 7]
sage: n.coprime_integers(11)
[1, 3, 5, 7, 9]
sage: n = 5; n.coprime_integers(10)
[1, 2, 3, 4, 6, 7, 8, 9]
sage: n.coprime_integers(5)
[1, 2, 3, 4]
sage: n = 99; n.coprime_integers(99)
[1, 2, 4, 5, 7, 8, 10, 13, 14, 16, 17, 19, 20, 23, 25, 26, 28, 29, 31, 32,
34, 35, 37, 38, 40, 41, 43, 46, 47, 49, 50, 52, 53, 56, 58, 59, 61, 62, 64,
65, 67, 68, 70, 71, 73, 74, 76, 79, 80, 82, 83, 85, 86, 89, 91, 92, 94, 95,
97, 98]

Author: Naqi Jaffery (2006-01-24): examples

ALGORITHM: Naive - compute lots of GCD's. If this isn't good enough for you, please code something better and submit a patch.

crt( )

Return the unique integer between 0 and $ mn$ that is congruent to the integer modulo $ m$ and to $ y$ modulo $ n$ . We assume that $ m$ and $ n$ are coprime.

sage: n = 17
sage: m = n.crt(5, 23, 11); m
247
sage: m%23
17
sage: m%11
5

denominator( )

Return the denominator of this integer.

sage: x = 5
sage: x.denominator()
1
sage: x = 0
sage: x.denominator()
1

digits( )

Return a list of digits for self in the given base in little endian order.

The return is unspecified if self is a negative number and the digits are given.

Input:

base
- integer (default: 2)
digits
- optional indexable object as source for the digits
padto
- the minimal length of the returned list, sufficient number of zeros are added to make the list minimum that length (default: 0)

sage: 5.digits()
[1, 0, 1]
sage: 5.digits(digits=["zero","one"])
['one', 'zero', 'one']
sage: 5.digits(3)
[2, 1]
sage: 0.digits(base=10)  # 0 has 0 digits
[]
sage: 0.digits(base=2)  # 0 has 0 digits
[]
sage: 10.digits(16,'0123456789abcdef')
['a']
sage: 0.digits(16,'0123456789abcdef')
[]
sage: 0.digits(16,'0123456789abcdef',padto=1)
['0']
sage: 123.digits(base=10,padto=5)
[3, 2, 1, 0, 0]
sage: 123.digits(base=2,padto=3)       # padto is the minimal length
[1, 1, 0, 1, 1, 1, 1]
sage: 123.digits(base=2,padto=10,digits=(1,-1))
[-1, -1, 1, -1, -1, -1, -1, 1, 1, 1]
sage: a=9939082340; a.digits(10)
[0, 4, 3, 2, 8, 0, 9, 3, 9, 9]
sage: a.digits(512)
[100, 302, 26, 74]
sage: (-12).digits(10)
[-2, -1]
sage: (-12).digits(2)
[0, 0, -1, -1]

We support large bases

sage: n=2^6000
sage: n.digits(2^3000)
[0, 0, 1]

sage: base=3; n=25
sage: l=n.digits(base)
sage: # the next relationship should hold for all n,base
sage: sum(base^i*l[i] for i in range(len(l)))==n
True
sage: base=3; n=-30; l=n.digits(base); sum(base^i*l[i] for i in range(len(l)))==n
True

Note: In some cases it is faster to give a digits collection. This would be particularly true for computing the digits of a series of small numbers. In these cases, the code is careful to allocate as few python objects as reasonably possible.

sage: digits = range(15)
sage: l=[ZZ(i).digits(15,digits) for i in range(100)]
sage: l[16]
[1, 1]

This function is comparable to str for speed.

sage: n=3^100000
sage: n.digits(base=10)[-1]  # slightly slower than str
1
sage: n=10^10000
sage: n.digits(base=10)[-1]  # slightly faster than str
1

Author: Joel B. Mohler significantly rewrote this entire function (2008-03-02)

divide_knowing_divisible_by( )

Returns the integer self / right when self is divisible by right.

If self is not divisible by right, the return value is undefined, and may not even be close to self/right for multi-word integers.

sage: a = 8; b = 4
sage: a.divide_knowing_divisible_by(b)
2
sage: (100000).divide_knowing_divisible_by(25)
4000
sage: (100000).divide_knowing_divisible_by(26) # close (random)
3846

However, often it's way off.

sage: a = 2^70; a
1180591620717411303424
sage: a // 11  # floor divide
107326510974310118493
sage: a.divide_knowing_divisible_by(11) # way off and possibly random
43215361478743422388970455040

divides( )

Return True if self divides n.

sage: Z = IntegerRing()
sage: Z(5).divides(Z(10))
True
sage: Z(0).divides(Z(5))
False
sage: Z(10).divides(Z(5))
False

divisors( )

Returns a list of all positive integer divisors of the integer self.

sage: a = -3; a.divisors()
[1, 3]
sage: a = 6; a.divisors()
[1, 2, 3, 6]
sage: a = 28; a.divisors()
[1, 2, 4, 7, 14, 28]
sage: a = 2^5; a.divisors()
[1, 2, 4, 8, 16, 32]
sage: a = 100; a.divisors()
[1, 2, 4, 5, 10, 20, 25, 50, 100]
sage: a = 1; a.divisors()
[1]
sage: a = 0; a.divisors()
Traceback (most recent call last):
...
ValueError: n must be nonzero
sage: a = 2^3 * 3^2 * 17; a.divisors()
[1, 2, 3, 4, 6, 8, 9, 12, 17, 18, 24, 34, 36, 51, 68, 72, 102, 136, 153,
204, 306, 408, 612, 1224]

exact_log( )

Returns the largest integer $ k$ such that $ m^k \leq$   self , i.e., the floor of $ \log_m($self$ )$ .

This is guaranteed to return the correct answer even when the usual log function doesn't have sufficient precision.

Input:

m
- integer >= 2

Author: David Harvey (2006-09-15)

TODO: - Currently this is extremely stupid code (although it should always work). Someone needs to think about doing this properly by estimating errors in the log function etc.

sage: Integer(125).exact_log(5)
3
sage: Integer(124).exact_log(5)
2
sage: Integer(126).exact_log(5)
3
sage: Integer(3).exact_log(5)
0
sage: Integer(1).exact_log(5)
0

sage: x = 3^100000
sage: RR(log(RR(x), 3))
100000.000000000
sage: RR(log(RR(x + 100000), 3))
100000.000000000

sage: x.exact_log(3)
100000
sage: (x+1).exact_log(3)
100000
sage: (x-1).exact_log(3)
99999

sage: x.exact_log(2.5)
Traceback (most recent call last):
...
TypeError: Attempt to coerce non-integral RealNumber to Integer

factor( )

Return the prime factorization of the integer as a list of pairs $ (p,e)$ , where $ p$ is prime and $ e$ is a positive integer.

Input:

algorithm
- string
* 'pari'
- (default) use the PARI c library
* 'kash'
- use KASH computer algebra system (requires the optional kash package be installed)
proof
- bool (default: True) whether or not to prove primality of each factor (only applicable for PARI).
limit
- int or None (default: None) if limit is given it must fit in a signed int, and the factorization is done using trial divsion and primits up to limit.

sage: n = 2^100 - 1; n.factor()
3 * 5^3 * 11 * 31 * 41 * 101 * 251 * 601 * 1801 * 4051 * 8101 * 268501

We using proof=False, which doesn't prove correctness of the primes that appear in the factorization:

sage: n = 920384092842390423848290348203948092384082349082
sage: n.factor(proof=False)
2 * 11 * 1531 * 4402903 * 10023679 * 619162955472170540533894518173
sage: n.factor(proof=True)
2 * 11 * 1531 * 4402903 * 10023679 * 619162955472170540533894518173

We factor using trial division only:

sage: n.factor(limit=1000)
2 * 11 * 41835640583745019265831379463815822381094652231

factorial( )

Return the factorial $ n! = 1 \cdot 2 \cdot 3 \cdots n$ . Self must fit in an unsigned long int.

sage: for n in srange(7):
...    print n, n.factorial()
0 1
1 1
2 2
3 6
4 24
5 120
6 720

floor( )

Return the floor of self, which is just self since self is an integer.

sage: n = 6
sage: n.floor()
6

gamma( )

The gamma function on integers is the factorial function (shifted by one) on positive integers, and $ \pm \infty$ on non-positive integers.

sage: gamma(5)
24
sage: gamma(0)
-Infinity
sage: gamma(-1)
+Infinity
sage: gamma(-2^150)
-Infinity

gcd( )

Return the greatest common divisor of self and $ n$ .

sage: gcd(-1,1)
1
sage: gcd(0,1)
1
sage: gcd(0,0)
0
sage: gcd(2,2^6)
2
sage: gcd(21,2^6)
1

inverse_mod( )

Returns the inverse of self modulo $ n$ , if this inverse exists. Otherwise, raises a ZeroDivisionError exception.

Input:

self
- Integer
n
- Integer
Output:
x
- Integer such that x*self = 1 (mod m), or raises ZeroDivisionError. IMPLEMENTATION: Call the mpz_invert GMP library function.

sage: a = Integer(189)
sage: a.inverse_mod(10000)
4709
sage: a.inverse_mod(-10000)
4709
sage: a.inverse_mod(1890)
Traceback (most recent call last):
...
ZeroDivisionError: Inverse does not exist.
sage: a = Integer(19)**100000
sage: b = a*a
sage: c = a.inverse_mod(b)
Traceback (most recent call last):
...
ZeroDivisionError: Inverse does not exist.

inverse_of_unit( )

Return inverse of self if self is a unit in the integers, i.e., self is -1 or 1. Otherwise, raise a ZeroDivisionError.

sage: (1).inverse_of_unit()
1
sage: (-1).inverse_of_unit()
-1
sage: 5.inverse_of_unit()
Traceback (most recent call last):
...
ZeroDivisionError: Inverse does not exist.
sage: 0.inverse_of_unit()
Traceback (most recent call last):
...
ZeroDivisionError: Inverse does not exist.

is_integral( )

Return True since integers are integral, i.e., satisfy a monic polynomial with integer coefficients.

sage: Integer(3).is_integral()
True

is_irreducible( )

Returns True if self is irreducible, i.e. +/- prime

sage: z = 2^31 - 1
sage: z.is_irreducible()
True
sage: z = 2^31
sage: z.is_irreducible()
False
sage: z = 7
sage: z.is_irreducible()
True
sage: z = -7
sage: z.is_irreducible()
True

is_one( )

Returns True if the integers is $ 1$ , otherwise False.

sage: Integer(1).is_one()
True
sage: Integer(0).is_one()
False

is_perfect_power( )

Returns True if self is a perfect power.

sage: z = 8
sage: z.is_perfect_power()
True
sage: z = 144
sage: z.is_perfect_power()
True
sage: z = 10
sage: z.is_perfect_power()
False

is_power( )

Returns True if self is a perfect power, ie if there exist integers a and b, $ b > 1$ with $ self = a^b$ .

sage: Integer(-27).is_power()
True
sage: Integer(12).is_power()
False

is_power_of( )

Returns True if there is an integer b with $ self = n^b$ .

sage: Integer(64).is_power_of(4)
True
sage: Integer(64).is_power_of(16)
False

TESTS:

sage: Integer(-64).is_power_of(-4)
True
sage: Integer(-32).is_power_of(-2)
True
sage: Integer(1).is_power_of(1)
True
sage: Integer(-1).is_power_of(-1)
True
sage: Integer(0).is_power_of(1)
False
sage: Integer(0).is_power_of(0)
True
sage: Integer(1).is_power_of(0)
True
sage: Integer(1).is_power_of(8)
True
sage: Integer(-8).is_power_of(2)
False

NOTES:

For large integers self, is_power_of() is faster than is_power(). The following examples gives some indication of how much faster.

sage: b = lcm(range(1,10000))
sage: b.exact_log(2)
14446
sage: t=cputime()
sage: for a in range(2, 1000): k = b.is_power()
sage: cputime(t)      # random
0.53203299999999976 
sage: t=cputime()
sage: for a in range(2, 1000): k = b.is_power_of(2)
sage: cputime(t)      # random
0.0
sage: t=cputime()
sage: for a in range(2, 1000): k = b.is_power_of(3)
sage: cputime(t)      # random
0.032002000000000308

sage: b = lcm(range(1, 1000))
sage: b.exact_log(2)
1437
sage: t=cputime()
sage: for a in range(2, 10000): k = b.is_power() # note that we change the range from the example above
sage: cputime(t)      # random
0.17201100000000036 
sage: t=cputime(); TWO=int(2)
sage: for a in range(2, 10000): k = b.is_power_of(TWO)
sage: cputime(t)      # random
0.0040000000000000036
sage: t=cputime()
sage: for a in range(2, 10000): k = b.is_power_of(3)
sage: cputime(t)      # random
0.040003000000000011
sage: t=cputime()
sage: for a in range(2, 10000): k = b.is_power_of(a)
sage: cputime(t)      # random
0.02800199999999986

is_prime( )

Returns True if self is prime.

NOTE: Integer primes are by definition positive! This is different than Magma, but the same as in Pari. See also the is_irreducible() method.

sage: z = 2^31 - 1
sage: z.is_prime()
True
sage: z = 2^31
sage: z.is_prime()
False
sage: z = 7
sage: z.is_prime()
True
sage: z = -7
sage: z.is_prime()
False
sage: z.is_irreducible()
True

is_prime_power( )

Returns True if $ x$ is a prime power, and False otherwise.

Input:

flag (for primality testing)
- int 0 (default): use a combination of algorithms. 1: certify primality using the Pocklington-Lehmer Test. 2: certify primality using the APRCL test.

sage: (-10).is_prime_power()
False
sage: (10).is_prime_power()
False
sage: (64).is_prime_power()
True
sage: (3^10000).is_prime_power()
True
sage: (10000).is_prime_power(flag=1)
False

is_pseudoprime( )

Returns True if self is a pseudoprime

sage: z = 2^31 - 1
sage: z.is_pseudoprime()
True
sage: z = 2^31
sage: z.is_pseudoprime()
False

is_square( )

Returns True if self is a perfect square

sage: Integer(4).is_square()
True
sage: Integer(41).is_square()
False

is_squarefree( )

Returns True if this integer is not divisible by the square of any prime and False otherwise.

sage: Integer(100).is_squarefree()
False
sage: Integer(102).is_squarefree()
True

is_unit( )

Returns true if this integer is a unit, i.e., 1 or $ -1$ .

sage: for n in srange(-2,3):
...    print n, n.is_unit()
-2 False
-1 True
0 False
1 True
2 False

isqrt( )

Returns the integer floor of the square root of self, or raises an ValueError if self is negative.

sage: a = Integer(5)
sage: a.isqrt()
2

sage: Integer(-102).isqrt()
Traceback (most recent call last):
...
ValueError: square root of negative integer not defined.

jacobi( )

Calculate the Jacobi symbol $ \left(\frac{self}{b}\right)$ .

sage: z = -1
sage: z.jacobi(17)
1
sage: z.jacobi(19)
-1
sage: z.jacobi(17*19)
-1
sage: (2).jacobi(17)
1
sage: (3).jacobi(19)
-1
sage: (6).jacobi(17*19)
-1
sage: (6).jacobi(33)
0
sage: a = 3; b = 7
sage: a.jacobi(b) == -b.jacobi(a)
True

kronecker( )

Calculate the Kronecker symbol $ \left(\frac{self}{b}\right)$ with the Kronecker extension $ (self/2)=(2/self)$ when self odd, or $ (self/2)=0$ when $ self$ even.

sage: z = 5
sage: z.kronecker(41)
1
sage: z.kronecker(43)
-1
sage: z.kronecker(8)
-1
sage: z.kronecker(15)
0
sage: a = 2; b = 5
sage: a.kronecker(b) == b.kronecker(a)
True

list( )

Return a list with this integer in it, to be compatible with the method for number fields.

sage: m = 5
sage: m.list()
[5]

multifactorial( )

Computes the k-th factorial $ n!^{(k)}$ of self. For k=1 this is the standard factorial, and for k greater than one it is the product of every k-th terms down from self to k. The recursive definition is used to extend this function to the negative integers.

sage: 5.multifactorial(1)
120
sage: 5.multifactorial(2)
15
sage: 23.multifactorial(2)
316234143225
sage: prod([1..23, step=2])
316234143225
sage: (-29).multifactorial(7)
1/2640

multiplicative_order( )

Return the multiplicative order of self.

sage: ZZ(1).multiplicative_order()
1
sage: ZZ(-1).multiplicative_order()
2
sage: ZZ(0).multiplicative_order()
+Infinity
sage: ZZ(2).multiplicative_order()
+Infinity

ndigits( )

Return the number of digits of self expressed in the given base.

Input:

base
- integer (default: 10)

sage: n = 52
sage: n.ndigits()
2
sage: n = -10003
sage: n.ndigits()
5
sage: n = 15
sage: n.ndigits(2)
4
sage: n=1000**1000000+1
sage: n.ndigits()
3000001
sage: n=1000**1000000-1
sage: n.ndigits()
3000000
sage: n=10**10000000-10**9999990
sage: n.ndigits()
10000000

next_prime( )

Returns the next prime after self.

Input:

proof
- bool or None (default: None, see proof.arithmetic or sage.structure.proof) Note that the global Sage default is proof=True

sage: Integer(100).next_prime()
101

Use Proof = False, which is way faster:

sage: b = (2^1024).next_prime(proof=False)

sage: Integer(0).next_prime()
2
sage: Integer(1001).next_prime()
1009

next_probable_prime( )

Returns the next probable prime after self, as determined by PARI.

sage: (-37).next_probable_prime()
2
sage: (100).next_probable_prime()
101
sage: (2^512).next_probable_prime()
134078079299425970995740249982058461274793658205923933777235614437217640300
735469768018742981669034276900318581864860508537538828119465699464336490060
84171        
sage: 0.next_probable_prime()
2
sage: 126.next_probable_prime()
127
sage: 144168.next_probable_prime()
144169

nth_root( )

Returns the truncated nth root of self.

Input:

n
- integer >= 1 (must fit in C int type)
report_exact
- boolean, whether to report if the root extraction was exact

Output: If report_exact is 0 (default), then returns the truncation of the nth root of self (i.e. rounded towards zero).

If report_exact is 1, then returns the nth root and a boolean indicating whether the root extraction was exact.

Author: David Harvey (2006-09-15)

sage: Integer(125).nth_root(3)
5
sage: Integer(124).nth_root(3)
4
sage: Integer(126).nth_root(3)
5

sage: Integer(-125).nth_root(3)
-5
sage: Integer(-124).nth_root(3)
-4
sage: Integer(-126).nth_root(3)
-5

sage: Integer(125).nth_root(2, True)
(11, False)
sage: Integer(125).nth_root(3, True)
(5, True)

sage: Integer(125).nth_root(-5)
Traceback (most recent call last):
...
ValueError: n (=-5) must be positive

sage: Integer(-25).nth_root(2)
Traceback (most recent call last):
...
ValueError: cannot take even root of negative number

numerator( )

Return the numerator of this integer.

sage: x = 5
sage: x.numerator()
5

sage: x = 0
sage: x.numerator()
0

ord( )
Synonym for valuation

sage: n=12
sage: n.ord(3)
1

powermod( )

Compute self**exp modulo mod.

sage: z = 2
sage: z.powermod(31,31)
2
sage: z.powermod(0,31)
1
sage: z.powermod(-31,31) == 2^-31 % 31
True

As expected, the following is invalid:

sage: z.powermod(31,0)
Traceback (most recent call last):
...
ZeroDivisionError: cannot raise to a power modulo 0

powermodm_ui( )

Computes self**exp modulo mod, where exp is an unsigned long integer.

sage: z = 32
sage: z.powermodm_ui(2, 4)
0
sage: z.powermodm_ui(2, 14)
2
sage: z.powermodm_ui(2^32-2, 14)
2
sage: z.powermodm_ui(2^32-1, 14)
Traceback (most recent call last):                              # 32-bit
...                                                             # 32-bit
OverflowError: exp (=4294967295) must be <= 4294967294          # 32-bit
8              # 64-bit
sage: z.powermodm_ui(2^65, 14)
Traceback (most recent call last):                              
...                                                             
OverflowError: exp (=36893488147419103232) must be <= 4294967294  # 32-bit
OverflowError: exp (=36893488147419103232) must be <= 18446744073709551614 
# 64-bit

prime_divisors( )

The prime divisors of self, sorted in increasing order. If n is negative, we do *not* include -1 among the prime divisors, since -1 is not a prime number.

sage: a = 1; a.prime_divisors()
[]
sage: a = 100; a.prime_divisors()
[2, 5]
sage: a = -100; a.prime_divisors()
[2, 5]
sage: a = 2004; a.prime_divisors()
[2, 3, 167]

prime_factors( )

The prime divisors of self, sorted in increasing order. If n is negative, we do *not* include -1 among the prime divisors, since -1 is not a prime number.

sage: a = 1; a.prime_divisors()
[]
sage: a = 100; a.prime_divisors()
[2, 5]
sage: a = -100; a.prime_divisors()
[2, 5]
sage: a = 2004; a.prime_divisors()
[2, 3, 167]

prime_to_m_part( )

Returns the prime-to-m part of self, i.e., the largest divisor of self that is coprime to m.

Input:

m
- Integer
Output: Integer

sage: z = 43434
sage: z.prime_to_m_part(20)
21717

quo_rem( )

Returns the quotient and the remainder of self divided by other. Note that the remainder returned is always either zero or of the same sign as other.

Input:

other
- the integer the divisor

Output:
q
- the quotient of self/other
r
- the remainder of self/other

sage: z = Integer(231)
sage: z.quo_rem(2)
(115, 1)
sage: z.quo_rem(-2)
(-116, -1)
sage: z.quo_rem(0)
Traceback (most recent call last):
...
ZeroDivisionError: other (=0) must be nonzero

radical( )

Return the product of the prime divisors of self.

If self is 0, returns 1.

sage: Integer(10).radical()
10
sage: Integer(20).radical()
10
sage: Integer(-20).radical()
-10
sage: Integer(0).radical()
1
sage: Integer(36).radical()
6

rational_reconstruction( )

Return the rational reconstruction of this integer modulo m, i.e., the unique (if it exists) rational number that reduces to self modulo m and whose numerator and denominator is bounded by sqrt(m/2).

sage: (3/7)%100
29
sage: (29).rational_reconstruction(100)
3/7

sqrt( )

The square root function.

Input:

prec
- integer (default: None): if None, returns an exact square root; otherwise returns a numerical square root if necessary, to the given bits of precision.
extend
- bool (default: True); if True, return a square root in an extension ring, if necessary. Otherwise, raise a ValueError if the square is not in the base ring.
all
- bool (default: False); if True, return all square roots of self, instead of just one.

sage: Integer(144).sqrt()
12
sage: Integer(102).sqrt()
sqrt(102)

sage: n = 2
sage: n.sqrt(all=True)
[sqrt(2), -sqrt(2)]
sage: n.sqrt(prec=10)
1.4
sage: n.sqrt(prec=100)
1.4142135623730950488016887242
sage: n.sqrt(prec=100,all=True)
[1.4142135623730950488016887242, -1.4142135623730950488016887242]
sage: n.sqrt(extend=False)
Traceback (most recent call last):
...
ValueError: square root of 2 not an integer
sage: Integer(144).sqrt(all=True)
[12, -12]
sage: Integer(0).sqrt(all=True)
[0]

sqrt_approx( )

sage: 5.sqrt_approx(prec=200)
2.2360679774997896964091736687312762354406183596115257242709
sage: 5.sqrt_approx()
2.23606797749979
sage: 4.sqrt_approx()
2

squarefree_part( )

Return the square free part of $ x$ (=self), i.e., the unique integer $ z$ that $ x = z y^2$ , with $ y^2$ a perfect square and $ z$ square-free.

Use self.radical() for the product of the primes that divide self.

If self is 0, just returns 0.

sage: squarefree_part(100)
1
sage: squarefree_part(12)
3
sage: squarefree_part(17*37*37)
17
sage: squarefree_part(-17*32)
-34
sage: squarefree_part(1)
1
sage: squarefree_part(-1)
-1
sage: squarefree_part(-2)
-2
sage: squarefree_part(-4)
-1

str( )

Return the string representation of self in the given base.

sage: Integer(2^10).str(2)
'10000000000'
sage: Integer(2^10).str(17)
'394'

sage: two=Integer(2)
sage: two.str(1)
Traceback (most recent call last):
...
ValueError: base (=1) must be between 2 and 36

sage: two.str(37)
Traceback (most recent call last):
...            
ValueError: base (=37) must be between 2 and 36

sage: big = 10^5000000
sage: s = big.str()                 # long time (> 20 seconds)
sage: len(s)                        # long time (depends on above defn of s)
5000001
sage: s[:10]                        # long time (depends on above defn of s)
'1000000000'

val_unit( )

Returns a pair: the p-adic valuation of self, and the p-adic unit of self.

Input:

p
- an integer at least 2.

Output:
v_p(self)
- the p-adic valuation of self
u_p(self)
- self / $ p^{v_p(\code{self})}$

sage: n = 60
sage: n.val_unit(2)
(2, 15)
sage: n.val_unit(3)
(1, 20)
sage: n.val_unit(7)
(0, 60)
sage: (2^11).val_unit(4)
(5, 2)
sage: 0.val_unit(2)
(+Infinity, 1)

valuation( )

Return the p-adic valuation of self.

Input:

p
- an integer at least 2.

sage: n = 60
sage: n.valuation(2)
2
sage: n.valuation(3)
1
sage: n.valuation(7)
0
sage: n.valuation(1)
Traceback (most recent call last):
...
ValueError: You can only compute the valuation with respect to a integer
larger than 1.

We do not require that p is a prime:

sage: (2^11).valuation(4)
5

Special Functions: __abs__,$ \,$ __and__,$ \,$ __copy__,$ \,$ __eq__,$ \,$ __float__,$ \,$ __floordiv__,$ \,$ __ge__,$ \,$ __gt__,$ \,$ __hex__,$ \,$ __index__,$ \,$ __init__,$ \,$ __int__,$ \,$ __invert__,$ \,$ __le__,$ \,$ __long__,$ \,$ __lshift__,$ \,$ __lt__,$ \,$ __mod__,$ \,$ __ne__,$ \,$ __oct__,$ \,$ __or__,$ \,$ __pos__,$ \,$ __pow__,$ \,$ __rand__,$ \,$ __reduce__,$ \,$ __repr__,$ \,$ __rfloordiv__,$ \,$ __rlshift__,$ \,$ __rmod__,$ \,$ __ror__,$ \,$ __rpow__,$ \,$ __rrshift__,$ \,$ __rshift__,$ \,$ _factor_trial_division,$ \,$ _im_gens_,$ \,$ _interface_init_,$ \,$ _l_action,$ \,$ _latex_,$ \,$ _lcm,$ \,$ _mathml_,$ \,$ _pari_,$ \,$ _r_action,$ \,$ _rpy_,$ \,$ _xgcd

__abs__( )

Computes $ \vert self\vert$

sage: z = -1
sage: abs(z)
1
sage: abs(z) == abs(1)
True

__and__( )

Return the bitwise and two integers.

sage: n = Integer(6);  m = Integer(2)
sage: n \& m
2
sage: n.__and__(m)
2

__copy__( )

Return a copy of the integer.

sage: n = 2
sage: copy(n)
2        
sage: copy(n) is n
False

__float__( )

Return double precision floating point representation of this integer.

sage: n = Integer(17); float(n)
17.0
sage: n = Integer(902834098234908209348209834092834098); float(n)
9.0283409823490813e+35
sage: n = Integer(-57); float(n)
-57.0
sage: n.__float__()
-57.0
sage: type(n.__float__())
<type 'float'>

__floordiv__( )

Computes the whole part of $ \frac{self}{other}$ .

sage: a = Integer(321) ; b = Integer(10)
sage: a // b
32
sage: z = Integer(-231)
sage: z // 2
-116
sage: z = Integer(231)
sage: z // 2
115
sage: z // -2
-116
sage: z // 0
Traceback (most recent call last):
...
ZeroDivisionError: other must be nonzero

__hex__( )

Return the hexadecimal digits of self in lower case.

Note: '0x' is not prepended to the result like is done by the corresponding Python function on int or long. This is for efficiency sake--adding and stripping the string wastes time; since this function is used for conversions from integers to other C-library structures, it is important that it be fast.

sage: print hex(Integer(15))
f
sage: print hex(Integer(16))
10
sage: print hex(Integer(16938402384092843092843098243))
36bb1e3929d1a8fe2802f083
sage: print hex(long(16938402384092843092843098243))
0x36bb1e3929d1a8fe2802f083L

__index__( )

Needed so integers can be used as list indices.

sage: v = [1,2,3,4,5]
sage: v[Integer(3)]
4
sage: v[Integer(2):Integer(4)]
[3, 4]

__int__( )

Return the Python int (or long) corresponding to this SAGE integer.

sage: n = 920938; n
920938
sage: int(n)
920938
sage: type(n.__int__())
<type 'int'>
sage: n = 99028390823409823904823098490238409823490820938; n
99028390823409823904823098490238409823490820938
sage: type(n.__int__())
<type 'long'>

__invert__( )

Return the multiplicative interse of self, as a rational number.

sage: n = 10
sage: 1/n
1/10
sage: n.__invert__()
1/10

__long__( )

Return long integer corresponding to this SAGE integer.

sage: n = 9023408290348092849023849820934820938490234290; n
9023408290348092849023849820934820938490234290
sage: long(n)
9023408290348092849023849820934820938490234290L
sage: n = 920938; n
920938
sage: long(n)
920938L
sage: n.__long__()
920938L

__lshift__( )

Shift x y bits to the left.

sage: 32 << 2
128
sage: 32 << int(2)
128
sage: int(32) << 2
128
sage: 1 << 2.5
Traceback (most recent call last):
...
TypeError: unsupported operands for <<

__mod__( )

Returns self modulo the modulus.

sage: z = 43
sage: z % 2
1
sage: z % 0
Traceback (most recent call last):
...
ZeroDivisionError: Integer modulo by zero
sage: -5 % 7
2
sage: -5 % -7
-5
sage: 5 % -7
-2

__oct__( )

Return the digits of self in base 8.

Note: '0' is not prepended to the result like is done by the corresponding Python function on int or long. This is for efficiency sake--adding and stripping the string wastes time; since this function is used for conversions from integers to other C-library structures, it is important that it be fast.

sage: print oct(Integer(800))
1440
sage: print oct(Integer(8)) 
10
sage: print oct(Integer(-50))
-62
sage: print oct(Integer(-899))
-1603
sage: print oct(Integer(16938402384092843092843098243))
15535436162247215217705000570203

Behavior of Sage integers vs. Python integers:

sage: oct(Integer(10))
'12'
sage: oct(int(10))
'012'
sage: oct(Integer(-23))
'-27'
sage: oct(int(-23))
'-027'

__or__( )

Return the bitwise or of the integers x and y.

sage: n = 8; m = 4
sage: n.__or__(m)
12

__pos__( )

sage: z=43434
sage: z.__pos__()
43434

__reduce__( )

This is used when pickling integers.

sage: n = 5
sage: t = n.__reduce__(); t
(<built-in function make_integer>, ('5',))
sage: t[0](*t[1])
5
sage: loads(dumps(n)) == n
True

__repr__( )

Return string representation of this integer.

sage: n = -5; n.__repr__()
'-5'

__rshift__( )

sage: 32 >> 2
8
sage: 32 >> int(2)
8
sage: int(32) >> 2
8
sage: 1 >> 2.5
Traceback (most recent call last):
...
TypeError: unsupported operands for >>

_factor_trial_division( )

Return partial factorization of self obtained using trial division for all primes up to limit, where limit must fit in a signed int.

Input:

limit
- integer that fits in a signed int

ALGORITHM: Uses Pari.

sage: n = 920384092842390423848290348203948092384082349082
sage: n._factor_trial_division(1000)
2 * 11 * 41835640583745019265831379463815822381094652231
sage: n._factor_trial_division(2^30)
2 * 11 * 1531 * 27325696005058797691594630609938486205809701

_im_gens_( )

Return the image of self under the map that sends the generators of the parent to im_gens. Since ZZ maps canonically in the category of rings, this is just the natural coercion.

sage: n = -10
sage: R = GF(17)
sage: n._im_gens_(R, [R(1)])
7

_interface_init_( )

Return canonical string to coerce this integer to any other math software, i.e., just the string representation of this integer in base 10.

sage: n = 9390823
sage: n._interface_init_()
'9390823'

_l_action( )

sage: [0] * 8 #indirect doctest
[0, 0, 0, 0, 0, 0, 0, 0]
sage: 'hi' * 8
'hihihihihihihihi'

_latex_( )

Return latex representation of this integer. This is just the underlying string representation and nothing more. This is called by the latex function.

sage: n = -5; n._latex_()
'-5'
sage: latex(n)
-5

_lcm( )

Returns the least common multiple of self and $ n$ .

sage: n = 60
sage: n._lcm(150)
300

_mathml_( )

Return mathml representation of this integer.

sage: mathml(-45)
<mn>-45</mn>
sage: (-45)._mathml_()
'<mn>-45</mn>'

_pari_( )

Returns the PARI version of this integer.

sage: n = 9390823
sage: m = n._pari_(); m
9390823
sage: type(m)
<type 'sage.libs.pari.gen.gen'>

TESTS:

sage: n = 10^10000000
sage: m = n._pari_() ## crash from trac 875
sage: m % 1234567
1041334

_r_action( )

sage: 8 * [0] #indirect doctest
[0, 0, 0, 0, 0, 0, 0, 0]
sage: 8 * 'hi'
'hihihihihihihihi'

_rpy_( )

Returns int(self) so that rpy can convert self into an object it knows how to work with.

sage: n = 100
sage: n._rpy_()
100
sage: type(n._rpy_())
<type 'int'>

_xgcd( )

Computes extended gcd of self and $ n$ .

Input:

self
- integer
n
- integer
minimal
- boolean (default false), whether to compute minimal cofactors (see below)

Output: A triple (g, s, t), where $ g$ is the non-negative gcd of self and $ n$ , and $ s$ and $ t$ are cofactors satisfying the Bezout identity

$\displaystyle g = s \cdot$   self$\displaystyle + t \cdot n. $

NOTE: If minimal is False, then there is no guarantee that the returned cofactors will be minimal in any sense; the only guarantee is that the Bezout identity will be satisfied (see examples below).

If minimal is True, the cofactors will satisfy the following conditions. If either self or $ n$ are zero, the trivial solution is returned. If both self and $ n$ are nonzero, the function returns the unique solution such that $ 0 \leq s < \vert n\vert/g$ (which then must also satisfy $ 0 \leq \vert t\vert \leq \vert$self$ \vert/g$ ).

sage: Integer(5)._xgcd(7)
(1, -4, 3)
sage: 5*-4 + 7*3
1
sage: g,s,t = Integer(58526524056)._xgcd(101294172798)
sage: g
22544886
sage: 58526524056 * s + 101294172798 * t
22544886

Without minimality guarantees, weird things can happen:

sage: Integer(3)._xgcd(21)
(3, -20, 3)
sage: Integer(3)._xgcd(24)
(3, -15, 2)
sage: Integer(3)._xgcd(48)
(3, -15, 1)

Weirdness disappears with minimal option:

sage: Integer(3)._xgcd(21, minimal=True)
(3, 1, 0)
sage: Integer(3)._xgcd(24, minimal=True)
(3, 1, 0)
sage: Integer(3)._xgcd(48, minimal=True)
(3, 1, 0)
sage: Integer(21)._xgcd(3, minimal=True)
(3, 0, 1)

Try minimal option with various edge cases:

sage: Integer(5)._xgcd(0, minimal=True)
(5, 1, 0)
sage: Integer(-5)._xgcd(0, minimal=True)
(5, -1, 0)
sage: Integer(0)._xgcd(5, minimal=True)
(5, 0, 1)
sage: Integer(0)._xgcd(-5, minimal=True)
(5, 0, -1)
sage: Integer(0)._xgcd(0, minimal=True)
(0, 1, 0)

Exhaustive tests, checking minimality conditions:

sage: for a in srange(-20, 20):
...     for b in srange(-20, 20):
...       if a == 0 or b == 0: continue
...       g, s, t = a._xgcd(b)
...       assert g > 0
...       assert a % g == 0 and b % g == 0
...       assert a*s + b*t == g
...       g, s, t = a._xgcd(b, minimal=True)
...       assert g > 0
...       assert a % g == 0 and b % g == 0
...       assert a*s + b*t == g
...       assert s >= 0 and s < abs(b)/g
...       assert abs(t) <= abs(a)/g

Author: David Harvey (2007-12-26): added minimality option

Class: IntegerWrapper

class IntegerWrapper
Python classes have problems inheriting from Integer directly, but they don't have issues with inheriting from IntegerWrapper.

Class: long_to_Z

class long_to_Z

sage: f = ZZ.coerce_map_from(long); f
Native morphism:
  From: Set of Python objects of type 'long'
  To:   Integer Ring
sage: f(1rL)
1
sage: f(-10000000000000000000001r)
-10000000000000000000001

Special Functions: __init__,$ \,$ _repr_type

_repr_type( )

See About this document... for information on suggesting changes.