Ring \(\ZZ\) of Integers

The IntegerRing_class represents the ring \(\ZZ\) of (arbitrary precision) integers. Each integer is an instance of Integer, which is defined in a Pyrex extension module that wraps GMP integers (the mpz_t type in GMP).

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

>>> from sage.all import *
>>> Z = IntegerRing(); Z
Integer Ring
>>> Z.characteristic()
0
>>> Z.is_field()
False

Z = IntegerRing(); Z
Z.characteristic()
Z.is_field()

There is a unique instance of the integer ring. To create an Integer, 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); a
1234
sage: b = Z(5678); b
5678
sage: type(a)
<class 'sage.rings.integer.Integer'>
sage: a + b
6912
sage: Z('94803849083985934859834583945394')
94803849083985934859834583945394

>>> from sage.all import *
>>> a = Z(Integer(1234)); a
1234
>>> b = Z(Integer(5678)); b
5678
>>> type(a)
<class 'sage.rings.integer.Integer'>
>>> a + b
6912
>>> Z('94803849083985934859834583945394')
94803849083985934859834583945394

a = Z(1234); a
b = Z(5678); b
type(a)
a + b
Z('94803849083985934859834583945394')
sage.rings.integer_ring.IntegerRing()[source]

Return the integer ring.

EXAMPLES:

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

>>> from sage.all import *
>>> IntegerRing()
Integer Ring
>>> ZZ==IntegerRing()
True

IntegerRing()
ZZ==IntegerRing()
class sage.rings.integer_ring.IntegerRing_class[source]

Bases: CommutativeRing

The ring of integers.

In order to introduce the ring \(\ZZ\) 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
sage: Z.category()
Join of Category of Dedekind domains
    and Category of euclidean domains
    and Category of noetherian rings
    and Category of infinite enumerated sets
    and Category of metric spaces
sage: Z(2^(2^5) + 1)
4294967297

>>> from sage.all import *
>>> Z = IntegerRing(); Z
Integer Ring
>>> Z.characteristic()
0
>>> Z.is_field()
False
>>> Z.category()
Join of Category of Dedekind domains
    and Category of euclidean domains
    and Category of noetherian rings
    and Category of infinite enumerated sets
    and Category of metric spaces
>>> Z(Integer(2)**(Integer(2)**Integer(5)) + Integer(1))
4294967297

Z = IntegerRing(); Z
Z.characteristic()
Z.is_field()
Z.category()
Z(2^(2^5) + 1)

One can give strings to create integers. Strings starting with 0x are interpreted as hexadecimal, and strings starting with 0o are interpreted as octal:

sage: parent('37')
<... 'str'>
sage: parent(Z('37'))
Integer Ring
sage: Z('0x10')
16
sage: Z('0x1a')
26
sage: Z('0o20')
16

>>> from sage.all import *
>>> parent('37')
<... 'str'>
>>> parent(Z('37'))
Integer Ring
>>> Z('0x10')
16
>>> Z('0x1a')
26
>>> Z('0o20')
16

parent('37')
parent(Z('37'))
Z('0x10')
Z('0x1a')
Z('0o20')

As an inverse to digits(), lists of digits are accepted, provided that you give a base. The lists are interpreted in little-endian order, so that entry i of the list is the coefficient of base^i:

sage: Z([4,1,7], base=100)
70104
sage: Z([4,1,7], base=10)
714
sage: Z([3, 7], 10)
73
sage: Z([3, 7], 9)
66
sage: Z([], 10)
0

>>> from sage.all import *
>>> Z([Integer(4),Integer(1),Integer(7)], base=Integer(100))
70104
>>> Z([Integer(4),Integer(1),Integer(7)], base=Integer(10))
714
>>> Z([Integer(3), Integer(7)], Integer(10))
73
>>> Z([Integer(3), Integer(7)], Integer(9))
66
>>> Z([], Integer(10))
0

Z([4,1,7], base=100)
Z([4,1,7], base=10)
Z([3, 7], 10)
Z([3, 7], 9)
Z([], 10)

Alphanumeric strings can be used for bases 2..36; letters a to z represent numbers 10 to 36. Letter case does not matter.

sage: Z("sage", base=32)
928270
sage: Z("SAGE", base=32)
928270
sage: Z("Sage", base=32)
928270
sage: Z([14, 16, 10, 28], base=32)
928270
sage: 14 + 16*32 + 10*32^2 + 28*32^3
928270

>>> from sage.all import *
>>> Z("sage", base=Integer(32))
928270
>>> Z("SAGE", base=Integer(32))
928270
>>> Z("Sage", base=Integer(32))
928270
>>> Z([Integer(14), Integer(16), Integer(10), Integer(28)], base=Integer(32))
928270
>>> Integer(14) + Integer(16)*Integer(32) + Integer(10)*Integer(32)**Integer(2) + Integer(28)*Integer(32)**Integer(3)
928270

Z("sage", base=32)
Z("SAGE", base=32)
Z("Sage", base=32)
Z([14, 16, 10, 28], base=32)
14 + 16*32 + 10*32^2 + 28*32^3

We next illustrate basic arithmetic in \(\ZZ\):

sage: a = Z(1234); a
1234
sage: b = Z(5678); b
5678
sage: type(a)
<class '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

>>> from sage.all import *
>>> a = Z(Integer(1234)); a
1234
>>> b = Z(Integer(5678)); b
5678
>>> type(a)
<class 'sage.rings.integer.Integer'>
>>> a + b
6912
>>> b + a
6912
>>> a * b
7006652
>>> b * a
7006652
>>> a - b
-4444
>>> b - a
4444

a = Z(1234); a
b = Z(5678); b
type(a)
a + b
b + a
a * b
b * a
a - b
b - a

When we divide two 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)
<class 'sage.rings.rational.Rational'>
sage: a/a
1
sage: type(a/a)
<class 'sage.rings.rational.Rational'>

>>> from sage.all import *
>>> a / b
617/2839
>>> type(a/b)
<class 'sage.rings.rational.Rational'>
>>> a/a
1
>>> type(a/a)
<class 'sage.rings.rational.Rational'>

a / b
type(a/b)
a/a
type(a/a)

For floor division, use the // operator instead:

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

>>> from sage.all import *
>>> a // b
0
>>> type(a//b)
<class 'sage.rings.integer.Integer'>

a // b
type(a//b)

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

>>> from sage.all import *
>>> a + Integer(17)
1251
>>> a * Integer(374)
461516
>>> Integer(374) * a
461516
>>> a/Integer(19)
1234/19
>>> Integer(0) + Z(-Integer(64))
-64

a + 17
a * 374
374 * a
a/19
0 + Z(-64)

Integers can be coerced:

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

>>> from sage.all import *
>>> a = Z(-Integer(64))
>>> int(a)
-64

a = Z(-64)
int(a)

We can create integers from several types of objects:

sage: Z(17/1)
17
sage: Z(Mod(19,23))
19
sage: Z(2 + 3*5 + O(5^3))                                                       # needs sage.rings.padics
17

>>> from sage.all import *
>>> Z(Integer(17)/Integer(1))
17
>>> Z(Mod(Integer(19),Integer(23)))
19
>>> Z(Integer(2) + Integer(3)*Integer(5) + O(Integer(5)**Integer(3)))                                                       # needs sage.rings.padics
17

Z(17/1)
Z(Mod(19,23))
Z(2 + 3*5 + O(5^3))                                                       # needs sage.rings.padics

Arbitrary numeric bases are supported; strings or list of integers are used to provide the digits (more details in IntegerRing_class):

sage: Z("sage", base=32)
928270
sage: Z([14, 16, 10, 28], base=32)
928270

>>> from sage.all import *
>>> Z("sage", base=Integer(32))
928270
>>> Z([Integer(14), Integer(16), Integer(10), Integer(28)], base=Integer(32))
928270

Z("sage", base=32)
Z([14, 16, 10, 28], base=32)

The digits method allows you to get the list of digits of an integer in a different basis (note that the digits are returned in little-endian order):

sage: b = Z([4,1,7], base=100)
sage: b
70104
sage: b.digits(base=71)
[27, 64, 13]

sage: Z(15).digits(2)
[1, 1, 1, 1]
sage: Z(15).digits(3)
[0, 2, 1]

>>> from sage.all import *
>>> b = Z([Integer(4),Integer(1),Integer(7)], base=Integer(100))
>>> b
70104
>>> b.digits(base=Integer(71))
[27, 64, 13]

>>> Z(Integer(15)).digits(Integer(2))
[1, 1, 1, 1]
>>> Z(Integer(15)).digits(Integer(3))
[0, 2, 1]

b = Z([4,1,7], base=100)
b
b.digits(base=71)
Z(15).digits(2)
Z(15).digits(3)

The str method returns a string of the digits, using letters a to z to represent digits 10..36:

sage: Z(928270).str(base=32)
'sage'

>>> from sage.all import *
>>> Z(Integer(928270)).str(base=Integer(32))
'sage'

Z(928270).str(base=32)

Note that str only works with bases 2 through 36.

absolute_degree()[source]

Return the absolute degree of the integers, which is 1.

Here, absolute degree refers to the rank of the ring as a module over the integers.

EXAMPLES:

sage: ZZ.absolute_degree()
1

>>> from sage.all import *
>>> ZZ.absolute_degree()
1

ZZ.absolute_degree()
characteristic()[source]

Return the characteristic of the integers, which is 0.

EXAMPLES:

sage: ZZ.characteristic()
0

>>> from sage.all import *
>>> ZZ.characteristic()
0

ZZ.characteristic()
completion(p, prec, extras={})[source]

Return the metric completion of the integers at the prime \(p\).

INPUT:

  • p – a prime (or infinity)

  • prec – the desired precision

  • extras – any further parameters to pass to the method used to create the completion

OUTPUT: the completion of \(\ZZ\) at \(p\)

EXAMPLES:

sage: ZZ.completion(infinity, 53)
Integer Ring
sage: ZZ.completion(5, 15, {'print_mode': 'bars'})                          # needs sage.rings.padics
5-adic Ring with capped relative precision 15

>>> from sage.all import *
>>> ZZ.completion(infinity, Integer(53))
Integer Ring
>>> ZZ.completion(Integer(5), Integer(15), {'print_mode': 'bars'})                          # needs sage.rings.padics
5-adic Ring with capped relative precision 15

ZZ.completion(infinity, 53)
ZZ.completion(5, 15, {'print_mode': 'bars'})                          # needs sage.rings.padics
degree()[source]

Return the degree of the integers, which is 1.

Here, degree refers to the rank of the ring as a module over the integers.

EXAMPLES:

sage: ZZ.degree()
1

>>> from sage.all import *
>>> ZZ.degree()
1

ZZ.degree()
extension(poly, names, **kwds)[source]

Return the order generated by the specified list of polynomials.

INPUT:

  • poly – list of one or more polynomials

  • names – a parameter which will be passed to EquationOrder()

  • embedding – a parameter which will be passed to EquationOrder()

OUTPUT:

  • Given a single polynomial as input, return the order generated by a root of the polynomial in the field generated by a root of the polynomial.

    Given a list of polynomials as input, return the relative order generated by a root of the first polynomial in the list, over the order generated by the roots of the subsequent polynomials.

EXAMPLES:

sage: x = polygen(ZZ, 'x')
sage: ZZ.extension(x^2 - 5, 'a')                                            # needs sage.rings.number_field
Order of conductor 2 generated by a in Number Field in a with defining polynomial x^2 - 5
sage: ZZ.extension([x^2 + 1, x^2 + 2], 'a,b')                               # needs sage.rings.number_field
Relative Order generated by [-b*a - 1, -3*a + 2*b] in Number Field in a
 with defining polynomial x^2 + 1 over its base field

>>> from sage.all import *
>>> x = polygen(ZZ, 'x')
>>> ZZ.extension(x**Integer(2) - Integer(5), 'a')                                            # needs sage.rings.number_field
Order of conductor 2 generated by a in Number Field in a with defining polynomial x^2 - 5
>>> ZZ.extension([x**Integer(2) + Integer(1), x**Integer(2) + Integer(2)], 'a,b')                               # needs sage.rings.number_field
Relative Order generated by [-b*a - 1, -3*a + 2*b] in Number Field in a
 with defining polynomial x^2 + 1 over its base field

x = polygen(ZZ, 'x')
ZZ.extension(x^2 - 5, 'a')                                            # needs sage.rings.number_field
ZZ.extension([x^2 + 1, x^2 + 2], 'a,b')                               # needs sage.rings.number_field
fraction_field()[source]

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

EXAMPLES:

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

>>> from sage.all import *
>>> ZZ.fraction_field()
Rational Field
>>> ZZ.fraction_field() == QQ
True

ZZ.fraction_field()
ZZ.fraction_field() == QQ
from_bytes(input_bytes, byteorder='big', is_signed=False)[source]

Return the integer represented by the given array of bytes.

Internally relies on the python int.from_bytes() method.

INPUT:

  • input_bytes – a bytes-like object or iterable producing bytes

  • byteorder – string (default: 'big'); determines the byte order of input_bytes (can only be 'big' or 'little')

  • is_signed – boolean (default: False); determines whether to use two’s compliment to represent the integer

EXAMPLES:

sage: ZZ.from_bytes(b'\x00\x10', byteorder='big')
16
sage: ZZ.from_bytes(b'\x00\x10', byteorder='little')
4096
sage: ZZ.from_bytes(b'\xfc\x00', byteorder='big', is_signed=True)
-1024
sage: ZZ.from_bytes(b'\xfc\x00', byteorder='big', is_signed=False)
64512
sage: ZZ.from_bytes([255, 0, 0], byteorder='big')
16711680
sage: type(_)
<class 'sage.rings.integer.Integer'>

>>> from sage.all import *
>>> ZZ.from_bytes(b'\x00\x10', byteorder='big')
16
>>> ZZ.from_bytes(b'\x00\x10', byteorder='little')
4096
>>> ZZ.from_bytes(b'\xfc\x00', byteorder='big', is_signed=True)
-1024
>>> ZZ.from_bytes(b'\xfc\x00', byteorder='big', is_signed=False)
64512
>>> ZZ.from_bytes([Integer(255), Integer(0), Integer(0)], byteorder='big')
16711680
>>> type(_)
<class 'sage.rings.integer.Integer'>

ZZ.from_bytes(b'\x00\x10', byteorder='big')
ZZ.from_bytes(b'\x00\x10', byteorder='little')
ZZ.from_bytes(b'\xfc\x00', byteorder='big', is_signed=True)
ZZ.from_bytes(b'\xfc\x00', byteorder='big', is_signed=False)
ZZ.from_bytes([255, 0, 0], byteorder='big')
type(_)
gen(n=0)[source]

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

INPUT:

  • n – (default: 0) in a ring with more than one generator, the optional parameter \(n\) indicates which generator to return; since there is only one generator in this case, the only valid value for \(n\) is 0

EXAMPLES:

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

>>> from sage.all import *
>>> ZZ.gen()
1
>>> type(ZZ.gen())
<class 'sage.rings.integer.Integer'>

ZZ.gen()
type(ZZ.gen())
gens()[source]

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

EXAMPLES:

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

>>> from sage.all import *
>>> ZZ.gens(); ZZ.gens()[Integer(0)]
(1,)
1
>>> type(ZZ.gens()[Integer(0)])
<class 'sage.rings.integer.Integer'>

ZZ.gens(); ZZ.gens()[0]
type(ZZ.gens()[0])
is_field(proof=True)[source]

Return False since the integers are not a field.

EXAMPLES:

sage: ZZ.is_field()
False

>>> from sage.all import *
>>> ZZ.is_field()
False

ZZ.is_field()
is_integrally_closed()[source]

Return that the integer ring is, in fact, integrally closed.

Note

This should rather be inherited from the category of DedekindDomains.

EXAMPLES:

sage: ZZ.is_integrally_closed()
True

>>> from sage.all import *
>>> ZZ.is_integrally_closed()
True

ZZ.is_integrally_closed()
krull_dimension()[source]

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

Note

This should rather be inherited from the category of DedekindDomains.

EXAMPLES:

sage: ZZ.krull_dimension()
1

>>> from sage.all import *
>>> ZZ.krull_dimension()
1

ZZ.krull_dimension()
ngens()[source]

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

EXAMPLES:

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

>>> from sage.all import *
>>> ZZ.ngens()
1
>>> len(ZZ.gens())
1

ZZ.ngens()
len(ZZ.gens())
order()[source]

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

EXAMPLES:

sage: ZZ.order()
+Infinity

>>> from sage.all import *
>>> ZZ.order()
+Infinity

ZZ.order()
parameter()[source]

Return an integer of degree 1 for the Euclidean property of \(\ZZ\), namely 1.

EXAMPLES:

sage: ZZ.parameter()
1

>>> from sage.all import *
>>> ZZ.parameter()
1

ZZ.parameter()
quotient(I, names=None, **kwds)[source]

Return the quotient of \(\ZZ\) by the ideal or integer I.

EXAMPLES:

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

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

ZZ.quo(6*ZZ)
ZZ.quo(0*ZZ)
ZZ.quo(3)
ZZ.quo(3*QQ)
random_element(x=None, y=None, distribution=None)[source]

Return a random integer.

INPUT:

  • x, y integers – bounds for the result

  • distribution – string:

    • 'uniform'

    • 'mpz_rrandomb'

    • '1/n'

    • 'gaussian'

OUTPUT: with no input, return a random integer

If only one integer \(x\) is given, return an integer between 0 and \(x-1\).

If two integers are given, return an integer between \(x\) and \(y-1\) inclusive.

If at least one bound is given, the default distribution is the uniform distribution; otherwise, it is the distribution described below.

If the distribution '1/n' is specified, the bounds are ignored.

If the distribution 'mpz_rrandomb' is specified, the output is in the range from 0 to \(2^x - 1\).

If the distribution 'gaussian' is specified, the output is sampled from a discrete Gaussian distribution with parameter \(\sigma=x\) and centered at zero. That is, the integer \(v\) is returned with probability proportional to \(\mathrm{exp}(-v^2/(2\sigma^2))\). See sage.stats.distributions.discrete_gaussian_integer for details. Note that if many samples from the same discrete Gaussian distribution are needed, it is faster to construct a sage.stats.distributions.discrete_gaussian_integer.DiscreteGaussianDistributionIntegerSampler object which is then repeatedly queried.

The default distribution for ZZ.random_element() is based on \(X = \mbox{trunc}(4/(5R))\), where \(R\) is a random variable uniformly distributed between \(-1\) and \(1\). This gives \(\mbox{Pr}(X = 0) = 1/5\), and \(\mbox{Pr}(X = n) = 2/(5|n|(|n|+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”; \(\mbox{Pr}(|X| \geq n) = 4/(5n)\), so for instance, we expect that \(|X| \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 \(|n| = 10000\), but around \(|n| = 30000\) some values will never be returned at all, and we will never return anything greater than \(2^{30}\).

EXAMPLES:

sage: ZZ.random_element().parent() is ZZ
True

>>> from sage.all import *
>>> ZZ.random_element().parent() is ZZ
True

ZZ.random_element().parent() is ZZ

The default uniform distribution is integers in \([-2, 2]\):

sage: from collections import defaultdict
sage: def add_samples(*args, **kwds):
....:     global dic, counter
....:     for _ in range(100):
....:         counter += 1
....:         dic[ZZ.random_element(*args, **kwds)] += 1

sage: def prob(x):
....:     return 1/5
sage: dic = defaultdict(Integer)
sage: counter = 0.0
sage: add_samples(distribution='uniform')
sage: while any(abs(dic[i]/counter - prob(i)) > 0.01 for i in dic):
....:     add_samples(distribution='uniform')

>>> from sage.all import *
>>> from collections import defaultdict
>>> def add_samples(*args, **kwds):
...     global dic, counter
...     for _ in range(Integer(100)):
...         counter += Integer(1)
...         dic[ZZ.random_element(*args, **kwds)] += Integer(1)

>>> def prob(x):
...     return Integer(1)/Integer(5)
>>> dic = defaultdict(Integer)
>>> counter = RealNumber('0.0')
>>> add_samples(distribution='uniform')
>>> while any(abs(dic[i]/counter - prob(i)) > RealNumber('0.01') for i in dic):
...     add_samples(distribution='uniform')

from collections import defaultdict
def add_samples(*args, **kwds):
    global dic, counter
    for _ in range(100):
        counter += 1
        dic[ZZ.random_element(*args, **kwds)] += 1
def prob(x):
    return 1/5
dic = defaultdict(Integer)
counter = 0.0
add_samples(distribution='uniform')
while any(abs(dic[i]/counter - prob(i)) > 0.01 for i in dic):
    add_samples(distribution='uniform')

Here we use the distribution '1/n':

sage: def prob(n):
....:     if n == 0:
....:         return 1/5
....:     return 2/(5*abs(n)*(abs(n) + 1))
sage: dic = defaultdict(Integer)
sage: counter = 0.0
sage: add_samples(distribution='1/n')
sage: while any(abs(dic[i]/counter - prob(i)) > 0.01 for i in dic):
....:     add_samples(distribution='1/n')

>>> from sage.all import *
>>> def prob(n):
...     if n == Integer(0):
...         return Integer(1)/Integer(5)
...     return Integer(2)/(Integer(5)*abs(n)*(abs(n) + Integer(1)))
>>> dic = defaultdict(Integer)
>>> counter = RealNumber('0.0')
>>> add_samples(distribution='1/n')
>>> while any(abs(dic[i]/counter - prob(i)) > RealNumber('0.01') for i in dic):
...     add_samples(distribution='1/n')

def prob(n):
    if n == 0:
        return 1/5
    return 2/(5*abs(n)*(abs(n) + 1))
dic = defaultdict(Integer)
counter = 0.0
add_samples(distribution='1/n')
while any(abs(dic[i]/counter - prob(i)) > 0.01 for i in dic):
    add_samples(distribution='1/n')

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

sage: -10 <= ZZ.random_element(-10, 10) < 10
True
sage: def prob(x):
....:     return 1/20
sage: dic = defaultdict(Integer)
sage: counter = 0.0
sage: add_samples(-10, 10)
sage: while any(abs(dic[i]/counter - prob(i)) > 0.01 for i in dic):
....:     add_samples(-10, 10)

sage: 0 <= ZZ.random_element(5) < 5
True
sage: def prob(x):
....:     return 1/5
sage: dic = defaultdict(Integer)
sage: counter = 0.0
sage: add_samples(5)
sage: while any(abs(dic[i]/counter - prob(i)) > 0.01 for i in dic):
....:     add_samples(5)

sage: while ZZ.random_element(10^50) < 10^49:
....:     pass

>>> from sage.all import *
>>> -Integer(10) <= ZZ.random_element(-Integer(10), Integer(10)) < Integer(10)
True
>>> def prob(x):
...     return Integer(1)/Integer(20)
>>> dic = defaultdict(Integer)
>>> counter = RealNumber('0.0')
>>> add_samples(-Integer(10), Integer(10))
>>> while any(abs(dic[i]/counter - prob(i)) > RealNumber('0.01') for i in dic):
...     add_samples(-Integer(10), Integer(10))

>>> Integer(0) <= ZZ.random_element(Integer(5)) < Integer(5)
True
>>> def prob(x):
...     return Integer(1)/Integer(5)
>>> dic = defaultdict(Integer)
>>> counter = RealNumber('0.0')
>>> add_samples(Integer(5))
>>> while any(abs(dic[i]/counter - prob(i)) > RealNumber('0.01') for i in dic):
...     add_samples(Integer(5))

>>> while ZZ.random_element(Integer(10)**Integer(50)) < Integer(10)**Integer(49):
...     pass

-10 <= ZZ.random_element(-10, 10) < 10
def prob(x):
    return 1/20
dic = defaultdict(Integer)
counter = 0.0
add_samples(-10, 10)
while any(abs(dic[i]/counter - prob(i)) > 0.01 for i in dic):
    add_samples(-10, 10)
0 <= ZZ.random_element(5) < 5
def prob(x):
    return 1/5
dic = defaultdict(Integer)
counter = 0.0
add_samples(5)
while any(abs(dic[i]/counter - prob(i)) > 0.01 for i in dic):
    add_samples(5)
while ZZ.random_element(10^50) < 10^49:
    pass

Notice that the right endpoint is not included:

sage: all(ZZ.random_element(-2, 2) < 2 for _ in range(100))
True

>>> from sage.all import *
>>> all(ZZ.random_element(-Integer(2), Integer(2)) < Integer(2) for _ in range(Integer(100)))
True

all(ZZ.random_element(-2, 2) < 2 for _ in range(100))

We return a sample from a discrete Gaussian distribution:

sage: ZZ.random_element(11.0, distribution='gaussian').parent() is ZZ      # needs sage.modules
True

>>> from sage.all import *
>>> ZZ.random_element(RealNumber('11.0'), distribution='gaussian').parent() is ZZ      # needs sage.modules
True

ZZ.random_element(11.0, distribution='gaussian').parent() is ZZ      # needs sage.modules
range(start, end=None, step=None)[source]

Optimized range function for Sage integers.

AUTHORS:

  • Robert Bradshaw (2007-09-20)

EXAMPLES:

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]

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

ZZ.range(10)
ZZ.range(-5, 5)
ZZ.range(0, 50, 5)
ZZ.range(0, 50, -5)
ZZ.range(50, 0, -5)
ZZ.range(50, 0, 5)
ZZ.range(50, -1, -5)

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]

>>> from sage.all import *
>>> ZZ.range(Integer(0), Integer(2)**Integer(83), Integer(2)**Integer(80))
[0, 1208925819614629174706176, 2417851639229258349412352,
 3626777458843887524118528, 4835703278458516698824704, 6044629098073145873530880,
 7253554917687775048237056, 8462480737302404222943232]

ZZ.range(0, 2^83, 2^80)

Make sure Issue #8818 is fixed:

sage: ZZ.range(1r, 10r)
[1, 2, 3, 4, 5, 6, 7, 8, 9]

>>> from sage.all import *
>>> ZZ.range(1, 10)
[1, 2, 3, 4, 5, 6, 7, 8, 9]

ZZ.range(1r, 10r)
residue_field(prime, check=True, names=None)[source]

Return the residue field of the integers modulo the given prime, i.e. \(\ZZ/p\ZZ\).

INPUT:

  • prime – a prime number

  • check – boolean (default: True); whether or not to check the primality of prime

  • names – ignored (for compatibility with number fields)

OUTPUT: the residue field at this prime

EXAMPLES:

sage: # needs sage.libs.pari
sage: F = ZZ.residue_field(61); F
Residue field of Integers modulo 61
sage: pi = F.reduction_map(); pi
Partially defined reduction map:
  From: Rational Field
  To:   Residue field of Integers modulo 61
sage: pi(123/234)
6
sage: pi(1/61)
Traceback (most recent call last):
...
ZeroDivisionError: Cannot reduce rational 1/61 modulo 61:
it has negative valuation
sage: lift = F.lift_map(); lift
Lifting map:
  From: Residue field of Integers modulo 61
  To:   Integer Ring
sage: lift(F(12345/67890))
33
sage: (12345/67890) % 61
33

>>> from sage.all import *
>>> # needs sage.libs.pari
>>> F = ZZ.residue_field(Integer(61)); F
Residue field of Integers modulo 61
>>> pi = F.reduction_map(); pi
Partially defined reduction map:
  From: Rational Field
  To:   Residue field of Integers modulo 61
>>> pi(Integer(123)/Integer(234))
6
>>> pi(Integer(1)/Integer(61))
Traceback (most recent call last):
...
ZeroDivisionError: Cannot reduce rational 1/61 modulo 61:
it has negative valuation
>>> lift = F.lift_map(); lift
Lifting map:
  From: Residue field of Integers modulo 61
  To:   Integer Ring
>>> lift(F(Integer(12345)/Integer(67890)))
33
>>> (Integer(12345)/Integer(67890)) % Integer(61)
33

# needs sage.libs.pari
F = ZZ.residue_field(61); F
pi = F.reduction_map(); pi
pi(123/234)
pi(1/61)
lift = F.lift_map(); lift
lift(F(12345/67890))
(12345/67890) % 61

Construction can be from a prime ideal instead of a prime:

sage: ZZ.residue_field(ZZ.ideal(97))
Residue field of Integers modulo 97

>>> from sage.all import *
>>> ZZ.residue_field(ZZ.ideal(Integer(97)))
Residue field of Integers modulo 97

ZZ.residue_field(ZZ.ideal(97))
valuation(p)[source]

Return the discrete valuation with uniformizer p.

EXAMPLES:

sage: v = ZZ.valuation(3); v                                                # needs sage.rings.padics
3-adic valuation
sage: v(3)                                                                  # needs sage.rings.padics
1

>>> from sage.all import *
>>> v = ZZ.valuation(Integer(3)); v                                                # needs sage.rings.padics
3-adic valuation
>>> v(Integer(3))                                                                  # needs sage.rings.padics
1

v = ZZ.valuation(3); v                                                # needs sage.rings.padics
v(3)                                                                  # needs sage.rings.padics

See also

Order.valuation(), RationalField.valuation()

zeta(n=2)[source]

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

INPUT:

  • n – (default: 2) a positive integer

OUTPUT:

an n-th root of unity in \(\ZZ\)

EXAMPLES:

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

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

ZZ.zeta()
ZZ.zeta(1)
ZZ.zeta(3)
ZZ.zeta(0)
sage.rings.integer_ring.crt_basis(X, xgcd=None)[source]

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

INPUT:

  • X – list of Integers that are coprime in pairs

  • xgcd – an optional parameter which is ignored

OUTPUT:

  • E – list of Integers such that E[i] = 1 (mod X[i]) and E[i] = 0 (mod X[j]) for all \(j \neq i\)

For this explanation, let E[i] be denoted by \(E_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 understood modulo \(X_i\), then a CRT lift of \(A\) is simply

\[\sum_i E_i A_i.\]

ALGORITHM: To compute \(E_i\), compute integers \(s\) and \(t\) such that

\[s X_i + t \prod_{i \neq j} X_j = 1. (\*)\]

Then

\[E_i = t \prod_{i \neq j} 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 \neq i\).

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

EXAMPLES:

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)

>>> from sage.all import *
>>> X = [Integer(11),Integer(20),Integer(31),Integer(51)]
>>> E = crt_basis([Integer(11),Integer(20),Integer(31),Integer(51)])
>>> E[Integer(0)]%X[Integer(0)], E[Integer(1)]%X[Integer(0)], E[Integer(2)]%X[Integer(0)], E[Integer(3)]%X[Integer(0)]
(1, 0, 0, 0)
>>> E[Integer(0)]%X[Integer(1)], E[Integer(1)]%X[Integer(1)], E[Integer(2)]%X[Integer(1)], E[Integer(3)]%X[Integer(1)]
(0, 1, 0, 0)
>>> E[Integer(0)]%X[Integer(2)], E[Integer(1)]%X[Integer(2)], E[Integer(2)]%X[Integer(2)], E[Integer(3)]%X[Integer(2)]
(0, 0, 1, 0)
>>> E[Integer(0)]%X[Integer(3)], E[Integer(1)]%X[Integer(3)], E[Integer(2)]%X[Integer(3)], E[Integer(3)]%X[Integer(3)]
(0, 0, 0, 1)

X = [11,20,31,51]
E = crt_basis([11,20,31,51])
E[0]%X[0], E[1]%X[0], E[2]%X[0], E[3]%X[0]
E[0]%X[1], E[1]%X[1], E[2]%X[1], E[3]%X[1]
E[0]%X[2], E[1]%X[2], E[2]%X[2], E[3]%X[2]
E[0]%X[3], E[1]%X[3], E[2]%X[3], E[3]%X[3]
sage.rings.integer_ring.is_IntegerRing(x)[source]

Internal function: return True iff x is the ring \(\ZZ\) of integers.