Exercise (6.3).17

Solve $x^{14} \equiv 27  \pmod {37}$ by using the primitive root 2 of modulo 37.

We are given that 2 is a primitive root modulo 37.

We prepare the following table of indices

ind_2(a) = n	2^n	a = 2^n mod 37
1	2	2
2	4	4
3	8	8
4	16	16
5	32	32
6	64	27
7	128	17
8	256	34
9	512	31
10	1024	25
11	2048	13
12	4096	26
13	8192	15
14	16384	30
15	32768	23
16	65536	9
17	131072	18
18	262144	36
19	524288	35
20	1048576	33
21	2097152	29
22	4194304	21
23	8388608	5
24	16777216	10
25	33554432	20
26	67108864	3
27	134217728	6
28	268435456	12
29	536870912	24
30	1073741824	11
31	2147483648	22
32	4294967296	7
33	8589934592	14
34	17179869184	28
35	34359738368	19
36	68719476736	1

Applying Proposition (6.15) and (6.16) to $x^{14} \equiv 27 \pmod {37}$ gives us

$$ 14 \times \text{ind}_2(x) \equiv \text{ind}_2(27) \pmod{36} $$

Using the table of indices, we have

$$ 14 \times \text{ind}_2(x) \equiv 6 \pmod{36} $$

This has solutions if $g=\gcd(36,14)=2$ divides 6, which it does. In fact there are $g=2$ incongruent solutions modulo 36.

Dividing by 2

$$ 7 \times \text{ind}_2(x) \equiv 3 \pmod{18} $$

We can't obtain $\text{ind}_2(x)$ directly, but we do notice that $7 \times 3 \equiv 21 \equiv 3 \pmod{18}$, and so the two incongruent solutions are $ \text{ind}_2(x) = 3$ and $ \text{ind}_2(x) = 21$ modulo 36.

From these, the table of indices gives us

$$ x \equiv 8 \pmod {37} \quad \text{ and } \quad x \equiv 29 \pmod {37} $$