Module: sage.rings.integer_ring
Ring
of Integers
The class
classIntegerRing represents
the ring
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
) |
Return the integer ring
sage: IntegerRing() Integer Ring sage: ZZ==IntegerRing() True
) |
) |
Compute and return a Chinese Remainder Theorem basis for the list X of coprime integers.
Input:
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
) |
Return the factorization of the positive integer
as a sorted
list of tuples
such that
.
For further documentation see sage.rings.arith.factor()
sage: sage.rings.integer_ring.factor(420) 2^2 * 3 * 5 * 7
) |
) |
) |
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
In order to introduce the ring
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
:
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
) |
Return the absolute degree of the integers, which is 1
sage: ZZ.absolute_degree() 1
) |
Return the characteristic of the integers, which is 0
sage: ZZ.characteristic() 0
) |
Return the degree of the integers, which is 1
sage: ZZ.degree() 1
) |
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
) |
Returns the field of rational numbers - the fraction field of the integers.
sage: ZZ.fraction_field() Rational Field sage: ZZ.fraction_field() == QQ True
) |
Returns the additive generator of the integers, which is 1.
sage: ZZ.gen() 1 sage: type(ZZ.gen()) <type 'sage.rings.integer.Integer'>
) |
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'>
) |
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
) |
Return False - the integers are not a field.
sage: ZZ.is_field() False
) |
Return False - the integers are an infinite ring.
sage: ZZ.is_finite() False
) |
Return True - the integers are a Noetherian ring.
sage: ZZ.is_noetherian() True
) |
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
) |
Return the Krull dimension of the integers, which is 1.
sage: ZZ.krull_dimension() 1
) |
Returns the number of additive generators of the ring, which is 1.
sage: ZZ.ngens() 1 sage: len(ZZ.gens()) 1
) |
Return the order (cardinality) of the integers, which is +Infinity.
sage: ZZ.order() +Infinity
) |
Returns an integer of degree 1 for the Euclidean property of ZZ, namely 1.
sage: ZZ.parameter() 1
) |
Return the quotient of
by the ideal
or integer
.
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
) |
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
trunc
, where
is a random variable
uniformly distributed between -1 and 1. This gives
Pr
, and
Pr
for
.
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
,
so for instance, we expect that
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
, but around
some
values will never be returned at all, and we will never return
anything greater than
.
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)]
) |
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]
) |
Return a primitive n'th root of unity in the integers, or raise an error if none exists
Input:
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_
) |
sage: ZZ(17/1) 17 sage: ZZ(Mod(19,23)) 19 sage: ZZ(2 + 3*5 + O(5^3)) 17
) |
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
) |
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
) |
) |
sage: gap(ZZ) Integers
) |
) |
) |
sage: magma(ZZ) # optional Integer Ring
) |