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
class sage.rings.integer_mod_ring.IntegerModFactory

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
__weakref__
list of weak references to the object (if defined)
create_key(order=0)
create_object(version, order)

EXAMPLES:

sage: R = Integers(10)
sage: loads(dumps(R)) is R
True
class sage.rings.integer_mod_ring.IntegerModRing_generic(order, cache=None)

The ring of integers modulo N, with N composite.

EXAMPLES:

sage: R = IntegerModRing(97)
sage: a = R(5)
sage: a**(10^62)
61
_IntegerModRing_generic__unit_gens_primecase(p)
_IntegerModRing_generic__unit_gens_primepowercase(p, r)
Find smallest generator for (\ZZ/p^r\ZZ)^*.
__call__(x)

TESTS:

sage: K2 = GF(2)
sage: K3 = GF(3)
sage: K8 = GF(8,'a')
sage: K8(5)
1
sage: K8('a+1')
a + 1
sage: K8(K2(1))
1

The following test refers to Trac Ticket number 6468:

sage: class foo_parent(Parent):
...       pass
sage: class foo(RingElement):
...       def lift(self):
...           raise PariError
sage: P = foo_parent()
sage: F = foo(P)
sage: GF(2)(F)
...
TypeError: error coercing to finite field
__cmp__(other)

EXAMPLES:

sage: F = GF(11)
sage: F
Finite Field of size 11
sage: R = IntegerModRing(11)
sage: R == F
False
__init__(order, cache=None)

Create with the command IntegerModRing(order)

INPUT:

  • order - an integer 1

OUTPUT:

  • IntegerModRing - the ring of integers modulo N.

EXAMPLES:

First we compute with integers modulo 17.

sage: FF = IntegerModRing(17)
sage: FF
Ring of integers modulo 17
sage: FF.is_field()
True
sage: FF.characteristic()
17
sage: FF.order()
17
sage: gens = FF.unit_gens()
sage: a = gens[0]
sage: a
3
sage: a.is_square()
False
sage: def pow(i): return a**i
sage: [pow(i) for i in range(16)]
[1, 3, 9, 10, 13, 5, 15, 11, 16, 14, 8, 7, 4, 12, 2, 6]

Next we compute with the integers modulo 16.

sage: Z16 = IntegerModRing(16)
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
16
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

Saving and loading:

sage: R = Integers(100000)
sage: loads(R.dumps()) == R
True
__iter__()

EXAMPLES:

sage: R = IntegerModRing(3)
sage: for i in R:
...    print i
0
1
2
sage: L = [i for i in R]
sage: L[0].parent()
Ring of integers modulo 3
_axiom_init_()

Returns a string representation of self in (Pan)Axiom.

EXAMPLES:

sage: Z7 = Integers(7)
sage: Z7._axiom_init_()
'IntegerMod(7)'

sage: axiom(Z7)  #optional - axiom
IntegerMod 7

sage: fricas(Z7) #optional - fricas
IntegerMod(7)
_coerce_impl(x)

Canonical coercion.

EXAMPLES:

sage: R = IntegerModRing(17)
sage: a = R(3)
sage: b = R._coerce_(3)
sage: b
3
sage: a==b
True

This is allowed:

sage: R(2/3)
12

But this is not, since there is no (canonical or not!) ring homomorphism from \QQ to \GF{17}.

sage: R._coerce_(2/3)
...
TypeError: no canonical coercion of x

We do not allow the coercion GF(p) - Z/pZ, because in case of a canonical isomorphism, there is a coercion map in only one direction, i.e., to the object in the smaller category.

_fricas_init_()

Returns a string representation of self in (Pan)Axiom.

EXAMPLES:

sage: Z7 = Integers(7)
sage: Z7._axiom_init_()
'IntegerMod(7)'

sage: axiom(Z7)  #optional - axiom
IntegerMod 7

sage: fricas(Z7) #optional - fricas
IntegerMod(7)
_gap_init_()

EXAMPLES:

sage: R = Integers(12345678900)
sage: R
Ring of integers modulo 12345678900
sage: gap(R)
(Integers mod 12345678900)
_latex_()
_macaulay2_init_()

EXAMPLES:

sage: macaulay2(Integers(7))  # optional - macaulay2
ZZ
--
 7
sage: macaulay2(Integers(10)) # optional - macaulay2
...
TypeError: Error evaluating Macaulay2 code.
IN:sage1=ZZ/10;
OUT:stdio:3:9:(1):[0]: ZZ/n not implemented yet for composite n
_magma_init_(magma)

EXAMPLES:

sage: R = Integers(12345678900)
sage: R
Ring of integers modulo 12345678900
sage: magma(R)                                          # optional - magma
Residue class ring of integers modulo 12345678900
_pari_order()
_precompute_table()
_pseudo_fraction_field()

If self is composite, we may still want to do division by elements of self.

EXAMPLES:

sage: Integers(15).fraction_field()
...
TypeError: self must be an integral domain.
sage: Integers(15)._pseudo_fraction_field()
Ring of integers modulo 15
sage: R.<x> = Integers(15)[]
sage: (x+5)/2
8*x + 10

This should be very fast:

sage: R.<x> = Integers(next_prime(10^101)*next_prime(10^100))[]
sage: x / R.base_ring()(2)
500000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000013365000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000401*x
_repr_()
cardinality()
characteristic()

EXAMPLES:

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

EXAMPLES:

sage: R = Integers(15)
sage: f = R.coerce_map_from(Integers(450)); f
Natural morphism:
  From: Ring of integers modulo 450
  To:   Ring of integers modulo 15
sage: f(-1)
14
sage: f = R.coerce_map_from(int); f
Native morphism:
  From: Set of Python objects of type 'int'
  To:   Ring of integers modulo 15
sage: f(-1r)
14
sage: f = R.coerce_map_from(ZZ); f
Natural morphism:
  From: Integer Ring
  To:   Ring of integers modulo 15
sage: f(-1)
14
sage: f = R.coerce_map_from(Integers(10)); print f
None
sage: f = R.coerce_map_from(QQ); print f
None
degree()

Return 1.

EXAMPLE:

sage: R = Integers(12345678900)
sage: R.degree()
1
factored_order()

EXAMPLES:

sage: R = IntegerModRing(18)
sage: FF = IntegerModRing(17)
sage: R.factored_order()
2 * 3^2
sage: FF.factored_order()
17
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()
...
ValueError: self must be a field
is_field()

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 Z/NZ is finite for all positive N.

EXAMPLES:

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

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

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

EXAMPLES:

sage: Integers(18).krull_dimension()
0
list_of_elements_of_multiplicative_group()
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()
...
ValueError: multiplicative group of this ring is not cyclic
sage: Integers(4).multiplicative_generator()
3
sage: Integers(25*3).multiplicative_generator()
...
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 #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
order()
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:

  • tuple - the square roots of 1 in self.

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 \ge 3.

INPUT: (none)

OUTPUT:

  • list - a list of elements 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]
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.integer_mod_ring.crt(v)
INPUT: v - (list) a lift of elements of rings.IntegerMod(n), for various coprime moduli n.
sage.rings.integer_mod_ring.is_IntegerModRing(x)

Return True if x is an integer modulo ring.

EXAMPLES:

sage: from sage.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