0
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ Matlab: x=solve(sym('x')^29==mod(-1,59))? $\endgroup$ – horchler Feb 25 '15 at 18:27
1
$\begingroup$

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;
$\endgroup$
  • $\begingroup$ Any particular reason for avoiding MATLAB with modular arithmetic? $\endgroup$ – user2049004 Feb 25 '15 at 3:15
  • 1
    $\begingroup$ the dick answer: by conception MATLAB is geared towards numeric computations while modular arithmetic is symbolic. the short answer: because C++/Python is much faster than MATLAB and you can work mod N more easily. $\endgroup$ – r0fg1 Feb 25 '15 at 3:18
  • $\begingroup$ Thanks, that's helpful as I'm familiar with python but not so much C++. Also, you aren't a dick. $\endgroup$ – user2049004 Feb 25 '15 at 3:25
  • 1
    $\begingroup$ Maybe I’m a double-dick, but you really don’t want to use any computation package for this. $\endgroup$ – Lubin Feb 25 '15 at 3:41
  • $\begingroup$ no, you're right -- I was just being stupid $\endgroup$ – r0fg1 Feb 25 '15 at 17:44
1
$\begingroup$

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$.

$\endgroup$
0
$\begingroup$

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$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.