Consider the equation $x^4 = 7,$ which we wish to solve in $\mathbf{Z}/29\mathbf{Z}.$ I was taught a technique for solving this problem, but I can't understand it. I'll try my best to describe it, though.
First, notice that $2$ is a generator in $U(\mathbf{Z}/29\mathbf{Z}).$ Then define the "index base $2$" function, $$\mathrm{Ind}_2 x : U(\mathbf{Z}/29\mathbf{Z}) \to \mathbf{Z}/28\mathbf{Z},$$ which functions similarly to a logarithm. For, example, since $2^5 = 3$ in $\mathbf{Z}/29\mathbf{Z},$ we say that $\mathrm{Ind}_2 3 = 5.$ Now, we may generate a "table of indices" for $\mathbf{Z}/29\mathbf{Z},$ which contains $\mathrm{Ind}_2x$ for all $x$ in $\mathbf{Z}/29\mathbf{Z}$ (I won't write out the table, because only a few values of it should be needed).
All of this I understand. When it comes to solving equations, however, I am completely confused as to what is going on.
Returning to $x^4 = 7,$ we take the index base $2$ of both sides, yielding $\mathrm{Ind}_2x^4 = \mathrm{Ind}_27,$ and now using index properties (that I have not seen proven, and I am not convinced work), and our table to evaluate $\mathrm{Ind}_2 7,$ we get the equation $$4\cdot\mathrm{Ind}_2x = 12.$$
Now, we divide by $4$, but because we are for some reason now working in $\mathbf{Z}/28\mathbf{Z},$ we have to also divide the $28$ by $4$ (this trick in particular really makes no logical sense to me), to get that $$\mathrm{Ind}_2x=3,$$ which we now solve over $\mathbf{Z}/7\mathbf{Z}.$ This tells us that $\mathrm{Ind}_2 x = 3, 10, 17,$ or $24,$ which by the table tells us that $x = 8, 9, 20,$ and $21$ are the solutions to the equation.
I might have explained this process poorly, but that is only because I am repeating the way it was explained to me, even though I really don't understand what's going on. Can someone salvage the method being applied here, and justify it/add some rigor to the steps?
Thank you.
The map $h(x)=2^x$ is an isomorphism from $Z_{28}$ under addition onto the multiplicative group of nonzero elements of $Z_{29},$ and $ind_2(x)$ is its inverse. This is like the usual relation between log and exp, as you mention.
Then you have the identity (similar to a log identity) that $2^{ind_2 x}=x$ mod $29$. There is now a relation with Fermats little theorem, here that $\gcd(u,29)=1$ implies $u^{28}=1$ mod $29.$ This means for $u=2$ whose order is $28$ that the powers on the $2$ are each unique mod $28.$ This is why when considering the ind_2 values one is working mod 28, rather than mod 29.
Your example of $x^4=7$ now works as you outline, giving $4 \cdot ind_2 x=ind_2 7=12.$ With $t$ for $ind_2 x$ this is $4t=12$ mod $28$. In such a congruence, where each coefficient and the modulus have a common factor, one may divide all three by that factor, so that here you do get $t=3$ mod $7$, and the rest is as you have it.