Solving a congruence in mod 59

Question

Given that 10 is a primitive root in mod 59, I want to solve $x^{29} \equiv -1 (mod 59)$. My approach is, since 10 is a primitive root, we can set $x \equiv 10^{\bar{x}}, \Rightarrow x^{29} \equiv 10^{29\bar{x}}$. In mod 59, $-1 \equiv 58$. I want to find an equivalency of 58 to some power of 10, but I'm stuck there. I tried using MATLAB, but I think finite precision is preventing me from getting an answer. Once I have that power of 10, say $b$, such that $58 \equiv 10^b (mod 59)$, I can make this problem into a linear equation in (mod 58).

Answer 1

I may be confused but isn't it just $x\equiv 10^{29}$?

The point is, since $10$ is a primitive root, all of $1,\ldots,58$ will get hit by a power of $10$, so the power that hits $1$ for the first time must be $58$ -- not $59$ since $0$ in the field is off limits. This is elementary group theory. Now, since $(10^{29})^2\equiv10^{58}\equiv1$, $10^{29}\equiv\pm1$ -- this is a field after all -- there are at most 2 roots and $\pm1$ work. Finally, $10^{29}\not\equiv1$ since $10$ is primitive.

For example, in $\mathbb{Z}/5=\{\bar0,\bar1,\bar2,\bar3,\bar4\}$, $2$ is a primitive root -- its power $1,2,3,4$ are $\bar2,\bar4,\bar3,\bar1$.

EDIT: BTW, I don't want to sound like a dick but you should NEVER use MATLAB for modular arithmetic. The following C++ two-liner solves the problem:

int a=1;
for (int i=1;i<=29;++i)
    a = (a*10)%59;
cout << a;

Answer 2

The solution to the equation $x^{29}\equiv-1$ is not unique modulo the prime $59$. There are $29$ solutions, indeed.

Remember that the multiplicative group modulo a prime is cyclic. You have told us that $10$ is a generator. Let’s call it $g$, because the particular value of the primitive root is not important. But we can say that $-1=g^{29}$.

But $g^{58}=1$, and multiplication can be thought of as $g^ag^b=g^c$, where $c\equiv a+b\pmod{58}$. If you want to solve $x^{29}\equiv-1$, write your $x$ as $g^a$ for unknown $a$, and raise to the $29$-th power. You get: $(g^a)^{29}=g^{29a}$, and to solve your congruence, you get $g^{29a}\equiv g^{29}\pmod{59}$, so $29a\equiv29\pmod{58}$. This looks a little mysterious, allowing the obvious solution $a=1$, but what about the others? The last congruence translates to $29a-29=58m$ for some integer $m$. Divide through by $29$ and get $a-1=2m$, i.e. $a$ must be odd. And you see that all the odd numbers from $1$ through $57$ give you solutions to your congruence.

Thus the answer is: $x^{29}\equiv-1\pmod{59}$ if and only if $x$ is an odd power of $10$.

Answer 3

Using discrete logarithm and If $r$ is a primitive root of odd prime $p$, prove that $\text{ind}_r (-1) = \frac{p-1}{2}$,

$29$ind$_{10}x\equiv\dfrac{59-1}2\pmod{\phi(59)} \iff29$ind$_{10}x\equiv29\pmod{58}$

$\iff$ind$_{10}x\equiv1\pmod2\iff x\equiv10^{2k+1}\pmod{59}$ for $0\le2k+1\le58\iff0\le k\le28$