24.1 Ring $ \mathbf{Z}$ of Integers

Module: sage.rings.integer_ring

Ring $ \mathbf{Z}$ of Integers

The class
classIntegerRing represents the ring $ \mathbf{Z}$ of (arbitrary precision) integers. Each integer is an instance of the class
classInteger, which is defined in a Pyrex extension module that wraps GMP integers (the
classmpz_t type in GMP).

sage: Z = IntegerRing(); Z
Integer Ring
sage: Z.characteristic()
0
sage: Z.is_field()
False

There is a unique instances of class
classIntegerRing. To create an
classInteger, coerce either a Python int, long, or a string. Various other types will also coerce to the integers, when it makes sense.

sage: a = Z(1234); b = Z(5678); print a, b
1234 5678
sage: type(a)
<type 'sage.rings.integer.Integer'>
sage: a + b
6912
sage: Z('94803849083985934859834583945394')
94803849083985934859834583945394

TESTS:

sage: Z = IntegerRing()
sage: Z == loads(dumps(Z))
True

Module-level Functions

IntegerRing( )

Return the integer ring

sage: IntegerRing()
Integer Ring
sage: ZZ==IntegerRing()
True

clear_mpz_globals( )

crt_basis( )

Compute and return a Chinese Remainder Theorem basis for the list X of coprime integers.

Input:

X
- a list of Integers that are coprime in pairs
Output:
E
- a list of Integers such that E[i] = 1 (mod X[i]) and E[i] = 0 (mod X[j]) for all j!=i.

The E[i] have the property that if A is a list of objects, e.g., integers, vectors, matrices, etc., where A[i] is moduli X[i], then a CRT lift of A is simply sum E[i] * A[i].

ALGORITHM: To compute E[i], compute integers s and t such that

s * X[i] + t * (prod over i!=j of X[j]) = 1. (*)

Then E[i] = t * (prod over i!=j of X[j]). Notice that equation (*) implies that E[i] is congruent to 1 modulo X[i] and to 0 modulo the other X[j] for j!=i.

COMPLEXITY: We compute len(X) extended GCD's.

sage: X = [11,20,31,51]
sage: E = crt_basis([11,20,31,51])
sage: E[0]%X[0]; E[1]%X[0]; E[2]%X[0]; E[3]%X[0]
1
0
0
0
sage: E[0]%X[1]; E[1]%X[1]; E[2]%X[1]; E[3]%X[1]
0
1
0
0
sage: E[0]%X[2]; E[1]%X[2]; E[2]%X[2]; E[3]%X[2]
0
0
1
0
sage: E[0]%X[3]; E[1]%X[3]; E[2]%X[3]; E[3]%X[3]
0
0
0
1

factor( )

Return the factorization of the positive integer $ n$ as a sorted list of tuples $ (p_i, e_i)$ such that $ n=\prod p_i^{e_i}$ .

For further documentation see sage.rings.arith.factor()

sage: sage.rings.integer_ring.factor(420)
2^2 * 3 * 5 * 7

gmp_randrange( )

init_mpz_globals( )

is_IntegerRing( )

Internal funtion: returns true iff x is the ring ZZ of integers

sage: from sage.rings.integer_ring import  is_IntegerRing
sage: is_IntegerRing(ZZ)
True          
sage: is_IntegerRing(QQ)
False
sage: is_IntegerRing(parent(3))
True  
sage: is_IntegerRing(parent(1/3))
False

Class: IntegerRing_class

class IntegerRing_class
The ring of integers.

In order to introduce the ring $ \mathbf{Z}$ of integers, we illustrate creation, calling a few functions, and working with its elements.

sage: Z = IntegerRing(); Z
Integer Ring
sage: Z.characteristic()
0
sage: Z.is_field()
False

We next illustrate basic arithmetic in $ \mathbf{Z}$ :

sage: a = Z(1234); b = Z(5678); print a, b
1234 5678
sage: type(a)
<type 'sage.rings.integer.Integer'>
sage: a + b
6912
sage: b + a
6912
sage: a * b
7006652
sage: b * a
7006652
sage: a - b
-4444
sage: b - a
4444

When we divide to integers using /, the result is automatically coerced to the field of rational numbers, even if the result is an integer.

sage: a / b
617/2839
sage: type(a/b)
<type 'sage.rings.rational.Rational'>
sage: a/a
1
sage: type(a/a)
<type 'sage.rings.rational.Rational'>

For floor division, instead using the // operator:

sage: a // b
0
sage: type(a//b)
<type 'sage.rings.integer.Integer'>

Next we illustrate arithmetic with automatic coercion. The types that coerce are: str, int, long, Integer.

sage: a + 17
1251
sage: a * 374
461516
sage: 374 * a
461516
sage: a/19
1234/19
sage: 0 + Z(-64)
-64

Integers can be coerced:

sage: a = Z(-64)
sage: int(a)
-64

Functions: absolute_degree,$ \,$ characteristic,$ \,$ degree,$ \,$ extension,$ \,$ fraction_field,$ \,$ gen,$ \,$ gens,$ \,$ is_atomic_repr,$ \,$ is_field,$ \,$ is_finite,$ \,$ is_noetherian,$ \,$ is_subring,$ \,$ krull_dimension,$ \,$ ngens,$ \,$ order,$ \,$ parameter,$ \,$ quotient,$ \,$ random_element,$ \,$ range,$ \,$ zeta

absolute_degree( )

Return the absolute degree of the integers, which is 1

sage: ZZ.absolute_degree()
1

characteristic( )

Return the characteristic of the integers, which is 0

sage: ZZ.characteristic()
0

degree( )

Return the degree of the integers, which is 1

sage: ZZ.degree()
1

extension( )

Returns the order in the number field defined by poly generated (as a ring) by a root of poly.

sage: ZZ.extension(x^2-5, 'a')
Order in Number Field in a with defining polynomial x^2 - 5
sage: ZZ.extension([x^2 + 1, x^2 + 2], 'a,b')
Relative Order in Number Field in a with defining polynomial x^2 + 1 over
its base field

fraction_field( )

Returns the field of rational numbers - the fraction field of the integers.

sage: ZZ.fraction_field()
Rational Field
sage: ZZ.fraction_field() == QQ
True

gen( )

Returns the additive generator of the integers, which is 1.

sage: ZZ.gen()
1
sage: type(ZZ.gen())
<type 'sage.rings.integer.Integer'>

gens( )

Returns the tuple (1,) containing a single element, the additive generator of the integers, which is 1.

sage: ZZ.gens(); ZZ.gens()[0]
(1,)
1
sage: type(ZZ.gens()[0])
<type 'sage.rings.integer.Integer'>

is_atomic_repr( )

Return True, since elements of the integers do not have to be printed with parentheses around them, when they are coefficients, e.g., in a polynomial.

sage: ZZ.is_atomic_repr()
True

is_field( )

Return False - the integers are not a field.

sage: ZZ.is_field()
False

is_finite( )

Return False - the integers are an infinite ring.

sage: ZZ.is_finite()
False

is_noetherian( )

Return True - the integers are a Noetherian ring.

sage: ZZ.is_noetherian()
True

is_subring( )

Return True if ZZ is a subring of other in a natural way.

Every ring of characteristic 0 contains ZZ as a subring.

sage: ZZ.is_subring(QQ)
True

krull_dimension( )

Return the Krull dimension of the integers, which is 1.

sage: ZZ.krull_dimension()
1

ngens( )

Returns the number of additive generators of the ring, which is 1.

sage: ZZ.ngens()
1
sage: len(ZZ.gens())
1

order( )

Return the order (cardinality) of the integers, which is +Infinity.

sage: ZZ.order()
+Infinity

parameter( )

Returns an integer of degree 1 for the Euclidean property of ZZ, namely 1.

sage: ZZ.parameter()
1

quotient( )

Return the quotient of $ \mathbf{Z}$ by the ideal $ I$ or integer $ I$ .

sage: ZZ.quo(6*ZZ)
Ring of integers modulo 6
sage: ZZ.quo(0*ZZ)
Integer Ring
sage: ZZ.quo(3)
Ring of integers modulo 3
sage: ZZ.quo(3*QQ)
Traceback (most recent call last):
...
TypeError: I must be an ideal of ZZ

random_element( )

Return a random integer.

ZZ.random_element() - return an integer using the default distribution described below ZZ.random_element(n) - return an integer uniformly distributed between 0 and n-1, inclusive. ZZ.random_element(min, max) - return an integer uniformly destributed between min and max-1, inclusive.

The default distribution for ZZ.random_element() is based on $ X =$   trunc$ (4/(5R))$ , where $ R$ is a random variable uniformly distributed between -1 and 1. This gives Pr$ (X = 0) = 1/5$ , and Pr$ (X = n) = 2/(5\vert n\vert(\vert n\vert+1))$ for $ n \neq 0$ . Most of the samples will be small; -1, 0, and 1 occur with probability 1/5 each. But we also have a small but non-negligible proportion of ``outliers''; Pr$ (\vert X\vert \geq n) = 4/(5n)$ , so for instance, we expect that $ \vert X\vert \geq 1000$ on one in 1250 samples.

We actually use an easy-to-compute truncation of the above distribution; the probabilities given above hold fairly well up to about $ \vert n\vert = 10000$ , but around $ \vert n\vert = 30000$ some values will never be returned at all, and we will never return anything greater than $ 2^{30}$ .

The default distribution is on average 50

sage: [ZZ.random_element() for _ in range(10)]
[-8, 2, 0, 0, 1, -1, 2, 1, -95, -1]

The default uniform distribution is integers between -2 and 2 inclusive:

sage: [ZZ.random_element(distribution="uniform") \
        for _ in range(10)]
[2, -2, 2, -2, -1, 1, -1, 2, 1, 0]

If a range is given, the distribution is uniform in that range:

sage: ZZ.random_element(-10,10)
-5
sage: ZZ.random_element(10)
7
sage: ZZ.random_element(10^50)
62498971546782665598023036522931234266801185891699
sage: [ZZ.random_element(5) for _ in range(10)]
[1, 3, 4, 0, 3, 4, 0, 3, 0, 1]

Notice that the right endpoint is not included:

sage: [ZZ.random_element(-2,2) for _ in range(10)]
[-1, -2, 0, -2, 1, -1, -1, -2, -2, 1]

We compute a histogram over 1000 samples of the default distribution:

sage: from collections import defaultdict
sage: d = defaultdict(lambda: 0)
sage: for _ in range(1000): 
...       samp = ZZ.random_element()
...       d[samp] = d[samp] + 1
sage: sorted(d.items())
[(-1026, 1), (-248, 1), (-145, 1), (-81, 1), (-80, 1), (-79, 1), (-75, 1),
(-69, 1), (-68, 1), (-63, 2), (-61, 1), (-57, 1), (-50, 1), (-37, 1), (-35,
1), (-33, 1), (-29, 2), (-27, 2), (-25, 1), (-23, 2), (-22, 2), (-20, 1),
(-19, 1), (-18, 1), (-16, 4), (-15, 3), (-14, 1), (-13, 2), (-12, 2), (-11,
2), (-10, 7), (-9, 3), (-8, 3), (-7, 7), (-6, 8), (-5, 13), (-4, 24), (-3,
34), (-2, 75), (-1, 207), (0, 209), (1, 189), (2, 64), (3, 35), (4, 13),
(5, 11), (6, 10), (7, 4), (8, 4), (10, 1), (11, 1), (12, 1), (13, 1), (14,
1), (16, 3), (18, 1), (19, 1), (26, 2), (27, 1), (28, 1), (29, 1), (30, 1),
(32, 1), (33, 2), (35, 1), (37, 1), (39, 1), (41, 1), (42, 1), (52, 1),
(91, 1), (94, 1), (106, 1), (111, 1), (113, 2), (132, 1), (134, 1), (232,
1), (240, 1), (2133, 1), (3636, 1)]

range( )

Optimized range function for SAGE integer.

Author: Robert Bradshaw (2007-09-20)

sage: ZZ.range(10)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
sage: ZZ.range(-5,5)
[-5, -4, -3, -2, -1, 0, 1, 2, 3, 4]
sage: ZZ.range(0,50,5)
[0, 5, 10, 15, 20, 25, 30, 35, 40, 45]
sage: ZZ.range(0,50,-5)
[]
sage: ZZ.range(50,0,-5)
[50, 45, 40, 35, 30, 25, 20, 15, 10, 5]
sage: ZZ.range(50,0,5)
[]
sage: ZZ.range(50,-1,-5)
[50, 45, 40, 35, 30, 25, 20, 15, 10, 5, 0]

It uses different code if the step doesn't fit in a long:

sage: ZZ.range(0,2^83,2^80)
[0, 1208925819614629174706176, 2417851639229258349412352,
3626777458843887524118528, 4835703278458516698824704,
6044629098073145873530880, 7253554917687775048237056,
8462480737302404222943232]

zeta( )

Return a primitive n'th root of unity in the integers, or raise an error if none exists

Input:

n
- a positive integer (default 2)
Output: an n'th root of unity in ZZ

sage: ZZ.zeta()
-1
sage: ZZ.zeta(1)
1
sage: ZZ.zeta(3)
Traceback (most recent call last):
...
ValueError: no nth root of unity in integer ring
sage: ZZ.zeta(0)
Traceback (most recent call last):
...
ValueError: n must be positive in zeta()

Special Functions: __call__,$ \,$ __eq__,$ \,$ __ge__,$ \,$ __getitem__,$ \,$ __gt__,$ \,$ __init__,$ \,$ __iter__,$ \,$ __le__,$ \,$ __len__,$ \,$ __lt__,$ \,$ __ne__,$ \,$ _div,$ \,$ _gap_init_,$ \,$ _is_valid_homomorphism_,$ \,$ _latex_,$ \,$ _magma_init_,$ \,$ _repr_

__call__( )

sage: ZZ(17/1)
17
sage: ZZ(Mod(19,23))
19
sage: ZZ(2 + 3*5 + O(5^3))
17

__getitem__( )

Return the ring ZZ[...] obtained by adjoing to the integers a list x of several elements.

sage: ZZ[ sqrt(2), sqrt(3) ]
Relative Order in Number Field in sqrt2 with defining polynomial x^2 - 2
over its base field
sage: ZZ[x]
Univariate Polynomial Ring in x over Integer Ring
sage: ZZ['x,y']
Multivariate Polynomial Ring in x, y over Integer Ring
sage: R = ZZ[ sqrt(5) + 1]; R
Order in Number Field in a with defining polynomial x^2 - 2*x - 4
sage: R.is_maximal()
False
sage: R = ZZ[ (1+sqrt(5))/2 ]; R
Order in Number Field in a with defining polynomial x^2 - x - 1
sage: R.is_maximal()
True

__iter__( )

Iterate over all integers. 0 1 -1 2 -2 3 -3 ...

sage: for n in ZZ:
...    if n < 3: print n
...    else: break
0
1
-1
2
-2

_div( )

_gap_init_( )

sage: gap(ZZ)
Integers

_is_valid_homomorphism_( )

_latex_( )

_magma_init_( )

sage: magma(ZZ)           # optional
Integer Ring

_repr_( )

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