Number Theory - Discrete Log (Index) - Equation

[mattmns]

Here is a silly question from our book, that seems to be a pain to solve:
------------
Solve the following equation:

$$59^x \equiv 63 \ \text{mod 71}$$
------------

The idea is to use the discrete log (or index).

Note that 7 is a primitive root mod 71.

The two books I have looked at, solve a problem like this by creating a table with the powers of a primitive root (on the top they have 0, 1, ..., 70 and on the bottom they would have 7^top mod 71). Personally, I don't want to write all that out, so I am curious if there is a way to solve the problem without writing such a table. Any ideas? Thanks!

 

[lippyka]

Yes, there is a way to solve this problem without writing a table. Since 7 is a primitive root modulo 71, we can use the discrete logarithm (or index) to solve this equation. We want to solve for x in the equation 59^x = 63 (mod 71). We can use the following formula to find the solution:x = log_7(63) (mod 71)To calculate this, we need to find the smallest positive integer k such that 7^k = 63 (mod 71). Using the Euclidean algorithm, we can find that k = 18. Therefore, the solution to our equation is x = 18 (mod 71).