# Class to which an element belong in a quotient ring

This post is a wiki. Anyone with karma >750 is welcome to improve it.

Fellow Sages:

I wish to determine whether certain elements of the quotient ring $Q:=\mathbb{F}_{2}[x]/\langle (x^{5}-1)^2\rangle$ are units and, in the case they are indeed units, I would also like to compute their multiplicative orders. How can one go about doing this?

In case you consider that my previous questions is a wee bit too broad, I have a related question which is more specific: if $p(x) \in \mathbb{F}_{2}[x]$ and $k \in \mathbb{N}$, how does one even determine a representative of the class (in the quotient ring $Q$) to which $(p(x))^{k}$ belongs? The naïve approach does not seem to work here: in my viewpoint, the code

F = GF(2)

R.<x> = PolynomialRing(F)

S.= R.quo((x^5-1)^2)

b=x^5-1 b^2;
SHOULD output [0] because the image of $(x^{5}-1)^2$ under the natural projection $\mathbb{F}_{2}[x] \to Q$ is exactly equal to the zero element of the quotient ring $Q$, but it does not yield that (it outputs the polynomial $x^{10}+1$, duh!). Do you know how it is that I am supposed to modify it in order to get the class in $Q$ to which the power in question belongs? Thanks in advance for your insightful replies!
edit retag close merge delete

Sort by » oldest newest most voted

The given code could not be fully understood. (What is "output [0]"?)

However, the following way to view the things should be enough to proceed in the given case, and in a similar more general one.

sage: F = GF(2)
sage: R.<x> = F[]
sage: factor( x^5-1 )
(x + 1) * (x^4 + x^3 + x^2 + x + 1)


So the ring obtained by taking $R$ modulo $(x^5-1)^2$ is isomorphic to $$\mathbb F_2[x]/(x+1)^2\ \times \ \mathbb F_2[x]/(x^4 + x^3 + x^2 + x+1)^2\ .$$ (Chinese R.T.)

A an element in the cartesian product of rings is a unit iff each cartesian component of the element is a unit.

Let $P$ be irreducible in $R$. An element in $$\mathbb F_2[x]/P^2$$ is a unit, iff its image in the field $\mathbb F_2[x]/P$ is a unit, i.e. is not zero. (Since a polynomial $1+rP$ has the inverse $1-rP$ in the ring $R/(P^2)$.)

Some sample sage code:

sage: F = GF(2)
sage: R.<x> = F[]
sage: S.<u> = R.quotient( [ (x^5-1)^2 ] )
sage: u.is_unit()
True
sage: 1/u
u^9
sage: HF = Hom( S, F )
sage: f = HF( [F(1)] )
sage: f(u)
1
sage: F25.<v> = GF(2**4, modulus=x^4 + x^3 + x^2 + x + 1 )
sage: HF25 = Hom( S, F25 )
sage: g = HF25( [v] )
sage: g(u)
v
sage: # let us test if u^3+u+1 is a unit in S
sage: y = u^3 + u + 1
sage: f(y)
1
sage: f(y).is_unit()
True
sage: g(y)
v^3 + v + 1
sage: g(y).is_unit()
True
sage: y.is_unit()
True
sage: 1/y
u^9 + u^6 + u^4 + u^3 + u^2
sage: # let us compute the multiplicative order of y
sage: f(y).multiplicative_order()
1
sage: g(y).multiplicative_order()
15
sage: y^15
u^8 + u^7 + u^6 + u^5 + u^3 + u^2 + u
sage: y^30
1
sage: y^10
u^8 + u^2 + 1
sage: y^6
u^8


So the multiplicative order of $y=u^3+u+1$ was computed by mapping it to the two fields, compute there the multiplicative orders, take the lcm of them. (Well, the one field is simple, order is one for "each" unit.) Then compute the $y$--power of order this lcm. If it is one, this is the order. Else take the square. In our case, $y^{30}=1$ in $S$. But no divisor of $30$ "works instead", so the order is $30$.

more