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

Module: sage.rings.integer

Author Log:

Module-level Functions

gmp_randrange( )

integer( x)

make_integer( s)

pmem_malloc( )

Use the Python heap for GMP memory management.

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.

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

Functions: additive_order,$  $ binary,$  $ coprime_integers,$  $ copy,$  $ crt,$  $ denominator,$  $ divides,$  $ factor,$  $ factorial,$  $ inverse_mod,$  $ is_one,$  $ is_prime,$  $ is_square,$  $ is_squarefree,$  $ is_unit,$  $ is_zero,$  $ isqrt,$  $ multiplicative_order,$  $ next_prime,$  $ numerator,$  $ parent,$  $ powermod,$  $ powermodm_ui,$  $ quo_rem,$  $ set_si,$  $ set_str,$  $ sqrt,$  $ square_free_part,$  $ square_root,$  $ str,$  $ valuation

additive_order( self)

Return the additive order of self.

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

binary( self)

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

coprime_integers( self, m)

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

copy( self)

Return a copy of the integer.

crt( self, y, m, n)

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.

denominator( self)

Return the denominator of this integer.

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

divides( self, n)

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

factor( self, algorithm='pari')

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)

factorial( self)

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

inverse_mod( self, n)

Returns the inverse of self modulo $ n$ , if this inverse exists. Otherwise, raises a exceptionZeroDivisionError 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.

is_one( self)

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

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

is_prime( self)

Retuns True if self is prime

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

is_square( self)

Returns True if self is a perfect square

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

is_squarefree( self)

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( self)

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

is_zero( self)

Returns True if the integers is 0 , otherwise False.

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

isqrt( self)

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 number not defined.

multiplicative_order( self)

Return the multiplicative order of self, if self is a unit, or raise ArithmeticError otherwise.

sage: ZZ(1).multiplicative_order()
1
sage: ZZ(-1).multiplicative_order()
2
sage: ZZ(0).multiplicative_order()
Traceback (most recent call last):
...
ArithmeticError: no power of 0 is a unit
sage: ZZ(2).multiplicative_order()
Traceback (most recent call last):
...
ArithmeticError: no power of 2 is a unit

next_prime( self)

Returns the next prime after self

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

numerator( self)

Return the numerator of this integer.

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

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

parent( self)

Return the ring $ \mathbf{Z}$ of integers.

powermod( self, exp, mod)

Compute self**exp modulo mod.

sage: z = Integer(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):
...
RuntimeError

powermodm_ui( self, exp, mod)

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^31-1, 14)
4
sage: z.powermodm_ui(2^31, 14)
Traceback (most recent call last):                              # 32-bit
...                                                             # 32-bit
OverflowError: exp (=2147483648) must be <= 2147483647   # 32-bit
2              # 64-bit
sage: z.powermodm_ui(2^63, 14)
Traceback (most recent call last):                              
...                                                             
OverflowError: exp (=9223372036854775808) must be <= 2147483647           #
32-bit
OverflowError: exp (=9223372036854775808) must be <= 9223372036854775807  #
64-bit

quo_rem( self, other)

Returns the quotient and the remainder of self divided by 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)
(-115, 1)
sage: z.quo_rem(0)
Traceback (most recent call last):
...
ZeroDivisionError: other (=0) must be nonzero

set_si( self, signed long int n)

Coerces $ n$ to a C signed integer if possible, and sets self equal to $ n$ .

sage: n= ZZ(54)
sage: n.set_si(-43344);n
-43344
sage: n.set_si(43344);n
43344

Note that an error occurs when we are not dealing with integers anymore

sage: n.set_si(2^32);n
Traceback (most recent call last):      # 32-bit
...                                     # 32-bit
OverflowError: long int too large to convert to int   # 32-bit
4294967296       # 64-bit
sage: n.set_si(-2^32);n
Traceback (most recent call last):      # 32-bit
...                                     # 32-bit
OverflowError: long int too large to convert to int     # 32-bit
-4294967296      # 64-bit

set_str( self, s, base=10)

Set self equal to the number defined by the string $ s$ in the given base.

sage: n=100
sage: n.set_str('100000',2)
sage: n
32

If the number begins with '0X' or '0x', it is converted to an hex number:

sage: n.set_str('0x13',0)
sage: n
19
sage: n.set_str('0X13',0)
sage: n
19

If the number begins with a '0', it is converted to an octal number:

sage: n.set_str('013',0)
sage: n
11

'13' is not a valid binary number so the following raises an exception:

sage: n.set_str('13',2)
Traceback (most recent call last):
...
TypeError: unable to convert x (=13) to an integer in base 2

sqrt( self, bits=None)

Returns the positive square root of self, possibly as a a real or complex number if self is not a perfect integer square.

INPUT:
    bits -- number of bits of precision.
            If bits is not specified, the number of
            bits of precision is at least twice the
            number of bits of self (the precision
            is always at least 53 bits if not specified).
OUTPUT:
    integer, real number, or complex number.

For the guaranteed integer square root of a perfect square (with error checking), use self.square_root().

sage: Z = IntegerRing()
sage: Z(4).sqrt()
2
sage: Z(4).sqrt(53)
2.0000000000000000
sage: Z(2).sqrt(53)
1.4142135623730951
sage: Z(2).sqrt(100)
1.4142135623730950488016887242092
sage: n = 39188072418583779289; n.square_root()
6260037733
sage: (100^100).sqrt()
100000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000
sage: (-1).sqrt()
1.0000000000000000*I
sage: sqrt(-2)
1.4142135623730951*I
sage: sqrt(97)
9.8488578017961039
sage: n = 97; n.sqrt(200)
9.8488578017961047217462114149176244816961362874427641717231516

square_free_part( self)

Return the square free part of $ x$ , i.e., a divisor z such that $ x = z y^2$ , for a perfect square $ y^2$ .

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

square_root( self)

Return the positive integer square root of self, or raises a ValueError if self is not a perfect square.

sage: Integer(144).square_root()
12
sage: Integer(102).square_root()
Traceback (most recent call last):
...
ValueError: self (=102) is not a perfect square

str( self, int base=10)

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 (> 20 seconds)
sage: len(s)                        # depends on long
5000001
sage: s[:10]                        # depends on long
'1000000000'

Special Functions: __abs__,$  $ __add_,$  $ __add__,$  $ __and__,$  $ __cmp__,$  $ __div_,$  $ __div__,$  $ __eq__,$  $ __float__,$  $ __floordiv,$  $ __floordiv__,$  $ __ge__,$  $ __gt__,$  $ __hex__,$  $ __int__,$  $ __invert__,$  $ __le__,$  $ __long__,$  $ __lshift__,$  $ __lt__,$  $ __mod__,$  $ __mul_,$  $ __mul__,$  $ __ne__,$  $ __neg__,$  $ __or__,$  $ __pos__,$  $ __pow__,$  $ __radd__,$  $ __rand__,$  $ __rdiv__,$  $ __reduce__,$  $ __repr__,$  $ __rfloordiv__,$  $ __rlshift__,$  $ __rmod__,$  $ __rmul__,$  $ __ror__,$  $ __rpow__,$  $ __rrshift__,$  $ __rshift__,$  $ __rsub__,$  $ __str_malloc,$  $ __sub_,$  $ __sub__,$  $ _and,$  $ _gcd,$  $ _im_gens_,$  $ _interface_init_,$  $ _latex_,$  $ _lcm,$  $ _lshift,$  $ _mathml_,$  $ _mpfr_,$  $ _or,$  $ _pari_,$  $ _reduce_set,$  $ _rshift,$  $ _xgcd

__str_malloc( self, int base=10)

Return the string representation of self in the given base. (Uses malloc then PyMem. This is actually slightly faster than self.str() below, but it is unpythonic to use malloc.) However, self.str() below is nice because we know the size of the string ahead of time, and can work around a bug in GMP nicely. There seems to be a bug in GMP, where non-2-power base conversion for very large integers > 10 million digits (?) crashes GMP.

_gcd( self, Integer n)

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

_lcm( self, Integer n)

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

_xgcd( self, Integer n)

Return a triple $ g, s, t \in\mathbf{Z}$ such that

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

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