Maths WorkshopMaths problems with full solutions
Exercise 2110Number theory › CongruencesOlympiadAdded 3 Nov 2026

The discrete logarithm

#discrete logarithm#cyclic group#Pohlig-Hellman

Statement

In F11∗\mathbb{F}_{11}^*, find the discrete logarithm of 44 to base 22, i.e. find kk with 2k≡4(mod11)2^k\equiv4\pmod{11}.

Hint

Enumerate powers of 22 mod 1111.

Show solutionHide solution

Solution

Powers.
- 21=22^1=2
- 22=42^2=4 ✓
- 23=82^3=8
- 24=16≡52^4=16\equiv5
- 25=10≡−12^5=10\equiv-1
- 26≡−2≡92^6\equiv-2\equiv9
- 27≡−4≡72^7\equiv-4\equiv7
- 28≡−8≡32^8\equiv-8\equiv3
- 29≡62^9\equiv6
- 210≡12^{10}\equiv1

Solution. k=2k=2.

Conclusion. log⁡24=2\log_2 4=2 in F11∗\mathbb{F}_{11}^*. Note that 22 is a primitive root: it generates the whole group of order 1010.