# Solve congruence with primitive root

I am seeking the solution to the congruence

$$29x^{33} \equiv 27\ \text{(mod 11)}$$

Primitive root is 2 and $ord_{11} (2) =10$. Then I got so the equation can be field:

$$lnd_2(29) + 33 lnd_2(x) \equiv lnd2(27)\ \text{(mod 10)}$$

Since $$lnd_a(rs) \equiv lnd_ar + lnd_as \ \text{(mod p-1)}$$

However, how to get a prime number 29 to be the product of two numbers??

• $29\equiv 7 \bmod 11$.
– lhf
May 20, 2014 at 11:11
• Oh I see, thank you very much! May 20, 2014 at 11:15
• @YangXia: Have you been able to solve it? May 20, 2014 at 11:18
• @user88595, one more question is, can I make that 33 in the equation into least residue? May 20, 2014 at 11:19
• @YangXia, no! But you can simplify $33 \bmod 10$.
– lhf
May 20, 2014 at 11:26

Index tables are unneeded since it is $\rm\color{#c00}{easy}$ to take $\,n$'th roots when $\,n\,$ is coprime to $\,p\!-\!1,\,$ e.g.
${\rm mod}\ 11\!:\ 29x^{33}\!\equiv 27\overset{\large\, x^{10}\,\equiv\, 1}\iff\!-4x^3\!\equiv 16\!\!\iff\! x^3\!\equiv -4\!\!\!\overset{\rm\color{#c00}{cube}}\iff\!\! \dfrac{1}x\equiv 2\!\iff\! x \equiv \dfrac{1}2 \equiv \dfrac{12}2 = 6$
First reduce $\bmod 11$: $$29x^{33} \equiv 27 \bmod 11 \quad\text{iff}\quad 7x^{33} \equiv 5\bmod 11$$
Using index calculus gives us $$ind(7)+33ind(x)\equiv ind(5) \bmod 10$$ $$7+3ind(x)\equiv 4 \bmod 10$$ $$3ind(x)\equiv -3 \bmod 10$$ $$ind(x)\equiv -1 \bmod 10$$ so $ind(x)=9$ and $x\equiv 6 \bmod 11$.