uniolympiads Ελληνικά

Groups, rings and fields

Lagrange, the order of an element and of a product of commuting elements, cyclic groups, homomorphisms, actions and the orbit–stabiliser theorem, rings and ideals, Fp\F_p and Fp[x]\F_p[x].

What to know by heart

Groups and subgroups. A nonempty H⊆GH \subseteq G is a subgroup if ab−1∈Ha b^{-1} \in H for all a,b∈Ha, b \in H. If HH is finite, closure under the product is enough.

Lagrange. If GG is finite and H≤GH \le G, then ∣H∣|H| divides ∣G∣|G|, and the index is [G:H]=∣G∣/∣H∣[G : H] = |G| / |H|.

Order of an element. ord⁡(g)\operatorname{ord}(g) is the least d≥1d \ge 1 with gd=eg^d = e, and it equals ∣⟨g⟩∣|\langle g \rangle|. Hence:

gk=e  ⟺  ord⁡(g)∣k,ord⁡(g)∣∣G∣,g∣G∣=e,ord⁡(gk)=ord⁡(g)gcd⁡(k,ord⁡(g)).g^k = e \iff \operatorname{ord}(g) \mid k, \qquad \operatorname{ord}(g) \mid |G|, \qquad g^{|G|} = e, \qquad \operatorname{ord}(g^k) = \frac{\operatorname{ord}(g)}{\gcd(k, \operatorname{ord}(g))} .

Order of a product. If ab=baab = ba, ord⁡(a)=m\operatorname{ord}(a) = m and ord⁡(b)=n\operatorname{ord}(b) = n, then ord⁡(ab)∣lcm⁡(m,n)\operatorname{ord}(ab) \mid \operatorname{lcm}(m, n). If moreover gcd⁡(m,n)=1\gcd(m, n) = 1, then ord⁡(ab)=mn\operatorname{ord}(ab) = mn. Without commutativity neither statement holds.

Cyclic groups. In the cyclic group of order nn, for every d∣nd \mid n there is exactly one subgroup of order dd, and exactly φ(d)\varphi(d) elements of order dd. Hence ∑d∣nφ(d)=n\sum_{d \mid n} \varphi(d) = n. Every group of prime order is cyclic.

Homomorphisms. For a homomorphism ϕ:G→H\phi : G \to H, the kernel ker⁡ϕ\ker \phi is a normal subgroup, ϕ\phi is injective exactly when ker⁡ϕ={e}\ker \phi = \{e\}, and ∣G∣=∣ker⁡ϕ∣⋅∣im⁡ϕ∣|G| = |\ker \phi| \cdot |\operatorname{im} \phi| (first isomorphism theorem). Also ord⁡(ϕ(g))∣ord⁡(g)\operatorname{ord}(\phi(g)) \mid \operatorname{ord}(g), with equality if ϕ\phi is injective.

Actions. If GG acts on XX, the orbit of xx is GxGx and the stabiliser Gx={g:gx=x}G_x = \{g : gx = x\} is a subgroup. The orbit–stabiliser theorem:

∣Gx∣=[G:Gx],so∣Gx∣⋅∣Gx∣=∣G∣.|Gx| = [G : G_x], \qquad \text{so} \quad |Gx| \cdot |G_x| = |G| .

The orbits partition XX. The action of GG on the left cosets of a subgroup HH with [G:H]=n[G : H] = n gives a homomorphism G→SnG \to S_n whose kernel lies inside HH.

Cauchy (statement only). If the prime pp divides ∣G∣|G|, then GG has an element of order pp.

Rings, ideals, fields. An ideal II of a ring RR is an additive subgroup with rI⊆IrI \subseteq I and Ir⊆IIr \subseteq I for every r∈Rr \in R. The ideals of Z\Z are the nZn\Z. A field has only the ideals {0}\{0\} and itself. Z/nZ\Z/n\Z is a field exactly when nn is prime. The characteristic of a field is 00 or a prime pp, and in characteristic pp we have (a+b)p=ap+bp(a + b)^p = a^p + b^p (Frobenius).

Fp\F_p and Fp[x]\F_p[x]. In Fp[x]\F_p[x] there is division with remainder, so:

  • aa is a root of ff exactly when (x−a)∣f(x - a) \mid f, and a nonzero ff of degree dd has at most dd roots;
  • xp−x=∏a∈Fp(x−a)x^p - x = \prod_{a \in \F_p} (x - a) and xp−1−1=∏a≠0(x−a)x^{p-1} - 1 = \prod_{a \ne 0} (x - a) (the constant term gives Wilson again);
  • every ideal has the form (f)(f), and Fp[x]/(f)\F_p[x]/(f) is a field with pdeg⁡fp^{\deg f} elements exactly when ff is irreducible;
  • Fp∗\F_p^{*} is cyclic of order p−1p - 1.

Standard lemmas with short proofs

Lagrange. The cosets gHgH all have ∣H∣|H| elements (h↦ghh \mapsto gh is a bijection), and two of them either coincide or are disjoint. So they partition GG into [G:H][G : H] pieces of equal size.

Order of a product of commuting elements. Since ab=baab = ba, we have (ab)k=akbk(ab)^k = a^k b^k, so (ab)lcm⁡(m,n)=e(ab)^{\operatorname{lcm}(m, n)} = e. If gcd⁡(m,n)=1\gcd(m, n) = 1 and (ab)k=e(ab)^k = e, then ak=b−k∈⟨a⟩∩⟨b⟩a^k = b^{-k} \in \langle a \rangle \cap \langle b \rangle. The intersection is a subgroup of both, so its order divides mm and nn, that is, it is 11. Thus ak=bk=ea^k = b^k = e, so m∣km \mid k, n∣kn \mid k and mn∣kmn \mid k.

An element whose order is the least common multiple. In an abelian group, if there are elements of orders mm and nn, there is an element of order lcm⁡(m,n)\operatorname{lcm}(m, n). Write lcm⁡(m,n)=m′n′\operatorname{lcm}(m, n) = m' n' with m′∣mm' \mid m, n′∣nn' \mid n and gcd⁡(m′,n′)=1\gcd(m', n') = 1 (give each prime power to one of the two). Then am/m′a^{m/m'} and bn/n′b^{n/n'} have orders m′m' and n′n', and their product has order m′n′m' n'.

A finite subgroup of K∗K^{*} is cyclic. Let G≤K∗G \le K^{*} with ∣G∣=n|G| = n, and let mm be the largest order of an element. By the previous lemma every order divides mm (otherwise the least common multiple would exceed mm). So all nn elements are roots of xm−1x^m - 1, hence n≤mn \le m. By Lagrange m≤nm \le n, so m=nm = n and GG is cyclic.

Orbit–stabiliser. The map gGx↦gxg G_x \mapsto gx is well defined and bijective from the cosets of GxG_x onto the orbit GxGx, because gx=hx  ⟺  h−1g∈Gxgx = hx \iff h^{-1} g \in G_x.

An element of order 22 in a group of even order. Pair each gg with g−1g^{-1}. The elements with g≠g−1g \ne g^{-1} are even in number, so the gg with g2=eg^2 = e are even in number too. One of them is ee, so there is another one.

Frobenius. For 0<k<p0 < k < p, pp divides (pk)=p!k! (p−k)!\binom{p}{k} = \frac{p!}{k!\,(p-k)!}, because it divides the numerator and not the denominator.

A finite integral domain is a field. For a≠0a \ne 0 the map x↦axx \mapsto ax is injective (since ax=ay⇒a(x−y)=0⇒x=yax = ay \Rightarrow a(x - y) = 0 \Rightarrow x = y), hence surjective, so ax=1ax = 1 for some xx.

Typical tricks

  • Find the group and apply Lagrange. Fermat is Lagrange in (Z/pZ)∗(\Z/p\Z)^{*}, Euler is Lagrange in (Z/nZ)∗(\Z/n\Z)^{*}.
  • Compare orders of elements. An injective homomorphism preserves orders. In SnS_n the order of a permutation is the least common multiple of its cycle lengths, so a group with an element of "very large" order does not embed there.
  • Build an action. GG acts on itself by conjugation, on the cosets of a subgroup, or on a set given by the problem. For a group of order pkp^k acting on XX, ∣X∣≡∣{fixed points}∣(modp)|X| \equiv |\{\text{fixed points}\}| \pmod p, because every nontrivial orbit has size a power of pp greater than 11.
  • A subgroup of index 22 is normal: the left and the right cosets are HH and its complement.
  • Identities in rings. Expand (a+b)2(a + b)^2 without assuming ab=baab = ba: (a+b)2=a2+ab+ba+b2(a + b)^2 = a^2 + ab + ba + b^2. If all squares are 00, you get ab=−baab = -ba.
  • Bézout in the exponents. If gm=eg^m = e and gn=eg^n = e, then ggcd⁡(m,n)=eg^{\gcd(m, n)} = e.

How they appear in the IMC

  • Orders in an abelian group with pairwise coprime exponents (IMC 2001, day 1, problem 2), with the question whether commutativity is needed.
  • Subgroups generated by powers and the gcd⁡\gcd of the exponents (IMC 2005, day 1, problem 6).
  • Characteristic of a field and orders of elements (IMC 2018, day 1, problem 2): comparing the multiplicative and the additive group of a field.
  • Actions and fixed points (IMC 2010, day 2, problem 3; IMC 2020, day 2, problem 7): subgroups of SnS_n and indices of subgroups.
  • Homomorphisms into a symmetric group (IMC 2021, day 2, problem 6): GL2(Z/pZ)GL_2(\Z/p\Z) and SpS_p.
  • Rings (IMC 1999, day 2, problem 1; IMC 2016, day 2, problem 8): identities in a noncommutative ring and the ring Z/nZ\Z/n\Z.
  • Orders of permutations (IMC 2025, day 1, problem 5).

Pitfalls

  • The converse of Lagrange is false. A4A_4 has order 1212 but no subgroup of order 66.
  • Order of a product without commutativity. In S3S_3, (1 2)(1\,2) and (1 2 3)(1\,2\,3) have orders 22 and 33, but their product is a transposition, of order 22, not 66.
  • Commutativity without coprimality. aa and a−1a^{-1} commute and have the same order, but a⋅a−1=ea \cdot a^{-1} = e.
  • Z/nZ\Z/n\Z is not a field for composite nn, and there a polynomial can have more roots than its degree: x2−1x^2 - 1 has four roots modulo 88.

Contest problems using these tools

No problems with these tools yet.