Example 3 Find a primitive root modulo 43.
Solve $43-1=42=2 \cdot 3 \cdot 7$. The divisors $d=1,2,3,7,6,14,21,42$. First, find the index of 2.
$$\begin{array}{c}
2^{2} \equiv 4(\bmod 43), 2^{3} \equiv 8(\bmod 43), 2^{6} \equiv 8^{2} \equiv 21(\bmod 43) \\
2^{7} \equiv-1(\bmod 43), \quad 2^{14} \equiv 1(\bmod 43)
\end{array}$$

So $\delta_{43}(2)=14$. Next, find the index of 3.
$$\begin{array}{ll}
3^{2} \equiv 9(\bmod 43), & 3^{3} \equiv-16(\bmod 43) \\
3^{4} \equiv-5(\bmod 43), & 3^{6} \equiv 9 \cdot(-5) \equiv-2(\bmod 43), \\
3^{7} \equiv-6(\bmod 43), & 3^{14} \equiv 36 \equiv-7(\bmod 43) \\
3^{21} \equiv-1(\bmod 43) &
\end{array}$$

So 3 is a primitive root modulo 43.
Now, find $3^{42}$ modulo $43^{2}=1849$,
$$\begin{aligned}
3^{4} & \equiv 81 \equiv 2 \cdot 43-5\left(\bmod 43^{2}\right) \\
3^{8} & \equiv(2 \cdot 43-5)^{2} \equiv-5(4 \cdot 43-5)\left(\bmod 43^{2}\right) \\
3^{16} & \equiv 5^{2}(3 \cdot 43+25)\left(\bmod 43^{2}\right) \\
3^{20} & \equiv 5^{2}(3 \cdot 43+25)(2 \cdot 43-5) \\
& \equiv 5^{2}(35 \cdot 43-125) \\
& \equiv-5^{2}(11 \cdot 43-4)\left(\bmod 43^{2}\right) \\
3^{21} & \equiv-(2 \cdot 43-11)(11 \cdot 43-4) \\
& \equiv-44\left(\bmod 43^{2}\right) \\
3^{42} & \equiv(43+1)^{2} \equiv 1+2 \cdot 43\left(\bmod 43^{2}\right)
\end{aligned}$$

Since $43 \nmid 2$ and 3 is odd, 3 is a primitive root modulo $43^{a}, 2 \cdot 43^{a}$.