Ring \(\ZZ/n\ZZ\) of integers modulo \(n\)

EXAMPLES:

sage: R = Integers(97)
sage: a = R(5)
sage: a**100000000000000000000000000000000000000000000000000000000000000
61

This example illustrates the relation between \(\ZZ/p\ZZ\) and \(\GF{p}\). In particular, there is a canonical map to \(\GF{p}\), but not in the other direction.

sage: r = Integers(7)
sage: s = GF(7)
sage: r.has_coerce_map_from(s)
False
sage: s.has_coerce_map_from(r)
True
sage: s(1) + r(1)
2
sage: parent(s(1) + r(1))
Finite Field of size 7
sage: parent(r(1) + s(1))
Finite Field of size 7

We list the elements of \(\ZZ/3\ZZ\):

sage: R = Integers(3)
sage: list(R)
[0, 1, 2]

AUTHORS:

  • William Stein (initial code)
  • David Joyner (2005-12-22): most examples
  • Robert Bradshaw (2006-08-24): convert to SageX (Cython)
  • William Stein (2007-04-29): square_roots_of_one
  • Simon King (2011-04-21): allow to prescribe a category
class sage.rings.finite_rings.integer_mod_ring.IntegerModFactory

Bases: sage.structure.factory.UniqueFactory

Return the quotient ring \(\ZZ / n\ZZ\).

INPUT:

  • order – integer (default: 0), positive or negative

EXAMPLES:

sage: IntegerModRing(15)
Ring of integers modulo 15
sage: IntegerModRing(7)
Ring of integers modulo 7
sage: IntegerModRing(-100)
Ring of integers modulo 100

Note that you can also use Integers, which is a synonym for IntegerModRing.

sage: Integers(18)
Ring of integers modulo 18
sage: Integers() is Integers(0) is ZZ
True
create_key(order=0, category=None)

An integer mod ring is specified uniquely by its order.

EXAMPLES:

sage: Zmod.create_key(7)
7
sage: Zmod.create_key(7, Fields())
(7, Category of fields)
create_object(version, order)

EXAMPLES:

sage: R = Integers(10)
sage: TestSuite(R).run() # indirect doctest
class sage.rings.finite_rings.integer_mod_ring.IntegerModRing_generic(order, cache=None, category=None)

Bases: sage.rings.quotient_ring.QuotientRing_generic

The ring of integers modulo \(N\), with \(N\) composite.

INPUT:

  • order – an integer
  • category – a subcategory of CommutativeRings() (the default) (currently only available for subclasses)

OUTPUT:

The ring of integers modulo \(N\).

EXAMPLES:

First we compute with integers modulo \(29\).

sage: FF = IntegerModRing(29)
sage: FF
Ring of integers modulo 29
sage: FF.category()
Join of Category of commutative rings and Category of subquotients of monoids and Category of quotients of semigroups and Category of finite enumerated sets
sage: FF.is_field()
True
sage: FF.characteristic()
29
sage: FF.order()
29
sage: gens = FF.unit_gens()
sage: a = gens[0]
sage: a
2
sage: a.is_square()
False
sage: def pow(i): return a**i
sage: [pow(i) for i in range(16)]
[1, 2, 4, 8, 16, 3, 6, 12, 24, 19, 9, 18, 7, 14, 28, 27]

We have seen above that an integer mod ring is, by default, not initialised as an object in the category of fields. However, one can force it to be. Moreover, testing containment in the category of fields my re-initialise the category of the integer mod ring:

sage: F19 = IntegerModRing(19, category = Fields())
sage: F19.category().is_subcategory(Fields())
True
sage: F23 = IntegerModRing(23)
sage: F23.category().is_subcategory(Fields())
False
sage: F23 in Fields()
True
sage: F23.category().is_subcategory(Fields())
True

Next we compute with the integers modulo \(16\).

sage: Z16 = IntegerModRing(16)
sage: Z16.category()
Join of Category of commutative rings and Category of subquotients of monoids and Category of quotients of semigroups and Category of finite enumerated sets
sage: Z16.is_field()
False
sage: Z16.order()
16
sage: Z16.characteristic()
16
sage: gens = Z16.unit_gens()
sage: gens
(15, 5)
sage: a = gens[0]
sage: b = gens[1]
sage: def powa(i): return a**i
sage: def powb(i): return b**i
sage: gp_exp = FF.unit_group_exponent()
sage: gp_exp
28
sage: [powa(i) for i in range(15)]
[1, 15, 1, 15, 1, 15, 1, 15, 1, 15, 1, 15, 1, 15, 1]
sage: [powb(i) for i in range(15)]
[1, 5, 9, 13, 1, 5, 9, 13, 1, 5, 9, 13, 1, 5, 9]
sage: a.multiplicative_order()
2
sage: b.multiplicative_order()
4

Testing ideals and quotients:

sage: Z10 = Integers(10)
sage: I = Z10.principal_ideal(0)
sage: Z10.quotient(I) == Z10
True
sage: I = Z10.principal_ideal(2)
sage: Z10.quotient(I) == Z10
False
sage: I.is_prime()
True
sage: R = IntegerModRing(97)
sage: a = R(5)
sage: a**(10^62)
61
cardinality()

Return the cardinality of this ring.

EXAMPLES:

sage: Zmod(87).cardinality()
87
characteristic()

EXAMPLES:

sage: R = IntegerModRing(18)
sage: FF = IntegerModRing(17)
sage: FF.characteristic()
17
sage: R.characteristic()
18
degree()

Return 1.

EXAMPLE:

sage: R = Integers(12345678900)
sage: R.degree()
1
extension(poly, name=None, names=None, embedding=None)

Return an algebraic extension of self. See sage.rings.ring.CommutativeRing.extension() for more information.

EXAMPLES:

sage: R.<t> = QQ[]
sage: Integers(8).extension(t^2 - 3)
Univariate Quotient Polynomial Ring in t over Ring of integers modulo 8 with modulus t^2 + 5
factored_order()

EXAMPLES:

sage: R = IntegerModRing(18)
sage: FF = IntegerModRing(17)
sage: R.factored_order()
2 * 3^2
sage: FF.factored_order()
17
factored_unit_order()

Return a list of Factorization objects, each the factorization of the order of the units in a \(\ZZ / p^n \ZZ\) component of this group (using the Chinese Remainder Theorem).

EXAMPLES:

sage: R = Integers(8*9*25*17*29)
sage: R.factored_unit_order()
[2^2, 2 * 3, 2^2 * 5, 2^4, 2^2 * 7]
field()

If this ring is a field, return the corresponding field as a finite field, which may have extra functionality and structure. Otherwise, raise a ValueError.

EXAMPLES:

sage: R = Integers(7); R
Ring of integers modulo 7
sage: R.field()
Finite Field of size 7
sage: R = Integers(9)
sage: R.field()
Traceback (most recent call last):
...
ValueError: self must be a field
is_field(proof=True)

Return True precisely if the order is prime.

EXAMPLES:

sage: R = IntegerModRing(18)
sage: R.is_field()
False
sage: FF = IntegerModRing(17)
sage: FF.is_field()
True
is_finite()

Return True since \(\ZZ/N\ZZ\) is finite for all positive \(N\).

EXAMPLES:

sage: R = IntegerModRing(18)
sage: R.is_finite()
True
is_integral_domain(proof=True)

Return True if and only if the order of self is prime.

EXAMPLES:

sage: Integers(389).is_integral_domain()
True
sage: Integers(389^2).is_integral_domain()
False
is_noetherian()

Check if self is a Noetherian ring.

EXAMPLES:

sage: Integers(8).is_noetherian()
True
is_prime_field()

Return True if the order is prime.

EXAMPLES:

sage: Zmod(7).is_prime_field()
True
sage: Zmod(8).is_prime_field()
False
krull_dimension()

Return the Krull dimension of self.

EXAMPLES:

sage: Integers(18).krull_dimension()
0
list_of_elements_of_multiplicative_group()

Return a list of all invertible elements, as python ints.

EXAMPLES:

sage: R = Zmod(12)
sage: L = R.list_of_elements_of_multiplicative_group(); L
[1, 5, 7, 11]
sage: type(L[0])
<type 'int'>
modulus()

Return the polynomial \(x - 1\) over this ring.

Note

This function exists for consistency with the finite-field modulus function.

EXAMPLES:

sage: R = IntegerModRing(18)
sage: R.modulus()
x + 17
sage: R = IntegerModRing(17)
sage: R.modulus()
x + 16
multiplicative_generator()

Return a generator for the multiplicative group of this ring, assuming the multiplicative group is cyclic.

Use the unit_gens function to obtain generators even in the non-cyclic case.

EXAMPLES:

sage: R = Integers(7); R
Ring of integers modulo 7
sage: R.multiplicative_generator()
3
sage: R = Integers(9)
sage: R.multiplicative_generator()
2
sage: Integers(8).multiplicative_generator()
Traceback (most recent call last):
...
ValueError: multiplicative group of this ring is not cyclic
sage: Integers(4).multiplicative_generator()
3
sage: Integers(25*3).multiplicative_generator()
Traceback (most recent call last):
...
ValueError: multiplicative group of this ring is not cyclic
sage: Integers(25*3).unit_gens()
(26, 52)
sage: Integers(162).unit_gens()
(83,)
multiplicative_group_is_cyclic()

Return True if the multiplicative group of this field is cyclic. This is the case exactly when the order is less than 8, a power of an odd prime, or twice a power of an odd prime.

EXAMPLES:

sage: R = Integers(7); R
Ring of integers modulo 7
sage: R.multiplicative_group_is_cyclic()
True
sage: R = Integers(9)
sage: R.multiplicative_group_is_cyclic()
True
sage: Integers(8).multiplicative_group_is_cyclic()
False
sage: Integers(4).multiplicative_group_is_cyclic()
True
sage: Integers(25*3).multiplicative_group_is_cyclic()
False

We test that trac ticket #5250 is fixed:

sage: Integers(162).multiplicative_group_is_cyclic()
True
multiplicative_subgroups()

Return generators for each subgroup of \((\ZZ/N\ZZ)^*\).

EXAMPLES:

sage: Integers(5).multiplicative_subgroups()
((2,), (4,), ())
sage: Integers(15).multiplicative_subgroups()
((11, 7), (4, 11), (8,), (11,), (14,), (7,), (4,), ())
sage: Integers(2).multiplicative_subgroups()
((),)
sage: len(Integers(341).multiplicative_subgroups())
80

TESTS:

sage: IntegerModRing(1).multiplicative_subgroups()
((0,),)
sage: IntegerModRing(2).multiplicative_subgroups()
((),)
sage: IntegerModRing(3).multiplicative_subgroups()
((2,), ())
order()

Return the order of this ring.

EXAMPLES:

sage: Zmod(87).order()
87
quadratic_nonresidue()

Return a quadratic non-residue in self.

EXAMPLES:

sage: R = Integers(17)
sage: R.quadratic_nonresidue()
3
sage: R(3).is_square()
False
random_element(bound=None)

Return a random element of this ring.

If bound is not None, return the coercion of an integer in the interval [-bound, bound] into this ring.

EXAMPLES:

sage: R = IntegerModRing(18)
sage: R.random_element()
2
square_roots_of_one()

Return all square roots of 1 in self, i.e., all solutions to \(x^2 - 1 = 0\).

OUTPUT:

The square roots of 1 in self as a tuple.

EXAMPLES:

sage: R = Integers(2^10)
sage: [x for x in R if x^2 == 1]
[1, 511, 513, 1023]
sage: R.square_roots_of_one()
(1, 511, 513, 1023)
sage: v = Integers(9*5).square_roots_of_one(); v
(1, 19, 26, 44)
sage: [x^2 for x in v]
[1, 1, 1, 1]
sage: v = Integers(9*5*8).square_roots_of_one(); v
(1, 19, 71, 89, 91, 109, 161, 179, 181, 199, 251, 269, 271, 289, 341, 359)
sage: [x^2 for x in v]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
unit_gens()

Returns generators for the unit group \((\ZZ/N\ZZ)^*\).

We compute the list of generators using a deterministic algorithm, so the generators list will always be the same. For each odd prime divisor of \(N\) there will be exactly one corresponding generator; if \(N\) is even there will be 0, 1 or 2 generators according to whether 2 divides \(N\) to order 1, 2 or \(\geq 3\).

OUTPUT:

A tuple containing the units of self.

EXAMPLES:

sage: R = IntegerModRing(18)
sage: R.unit_gens()
(11,)
sage: R = IntegerModRing(17)
sage: R.unit_gens()
(3,)
sage: IntegerModRing(next_prime(10^30)).unit_gens()
(5,)

TESTS:

sage: IntegerModRing(2).unit_gens()
()
sage: IntegerModRing(4).unit_gens()
(3,)
sage: IntegerModRing(8).unit_gens()
(7, 5)
unit_group_exponent()

EXAMPLES:

sage: R = IntegerModRing(17)
sage: R.unit_group_exponent()
16
sage: R = IntegerModRing(18)
sage: R.unit_group_exponent()
6
unit_group_order()

Return the order of the unit group of this residue class ring.

EXAMPLES:

sage: R = Integers(500)
sage: R.unit_group_order()
200
sage.rings.finite_rings.integer_mod_ring.crt(v)

INPUT:

  • v – (list) a lift of elements of rings.IntegerMod(n), for various coprime moduli n

EXAMPLES:

sage: from sage.rings.finite_rings.integer_mod_ring import crt
sage: crt([mod(3, 8),mod(1,19),mod(7, 15)])
1027
sage.rings.finite_rings.integer_mod_ring.is_IntegerModRing(x)

Return True if x is an integer modulo ring.

EXAMPLES:

sage: from sage.rings.finite_rings.integer_mod_ring import is_IntegerModRing
sage: R = IntegerModRing(17)
sage: is_IntegerModRing(R)
True
sage: is_IntegerModRing(GF(13))
True
sage: is_IntegerModRing(GF(4, 'a'))
False
sage: is_IntegerModRing(10)
False
sage: is_IntegerModRing(ZZ)
False

Previous topic

Elements of the ring \(\ZZ\) of integers

Next topic

Elements of \(\ZZ/n\ZZ\)

This Page