- #1

fishturtle1

- 394

- 82

## Homework Statement

Let g be a primitive root for ##\mathbb{Z}/p\mathbb{Z}## where p is a prime number.

b) Prove that ##\log_g(h_1h_2) = \log_g(h_1) + \log_g(h_2)## for all ##h_1, h_2 \epsilon \mathbb{Z}/p\mathbb{Z}##.

## Homework Equations

Let x, denoted ##\log_g(h)##, be the discrete logarithm of g to the base g. Then ##g^x \equiv h## (mod p).

In part a) I showed : Suppose that ##x = a## and ##x = b## are both integer solutions to the congruence ##g^x \equiv h## (mod p). Prove that ##a \equiv b## (mod p - 1).

## The Attempt at a Solution

Attempted proof:

We have ##g^{\log_g(h_1)}g^{\log_g(h_2)} \equiv h_1h_2## (mod p). So

##g^{\log_g(h_1) + \log_g(h_2)} \equiv h_1h_2## (mod p).

We know ##\log_g(h_1h_2) \le p - 1## must be true. But ##\log_g(h1) + \log_g(h_2)## could be greater than p - 1. So, even though they are congruent modulo p - 1, they might not be equal. Let ##\log_g(h_1) + \log_g(h_2) = (p - 1)q + r## where ##q, r \epsilon \mathbb{Z}## and ##0 \le r < p -1##. Using Fermat's Little Theorem, we have

##g^{\log_g(h_1) + \log_g(h_2)}g^{q(p - 1)} \equiv h_1h_2(1)^q## (mod p).

##g^{\log_g(h_1) + \log_g(h_2) + q(p - 1)} \equiv h_1h_2## (mod p).

Taking the log of both sides, we get

##r \equiv \log_g(h_1h_2)## (mod p).

and since ##r < p - 1## and ##\log_g(h_1h_2) < p - 1## we can conclude

##r \equiv \log_g(h_1h_2)## (mod p - 1).

But ##r## and ##\log_g(h_1) + \log_g(h_2)## are just elements of the equivalence class ##[r]## in ##\mathbb{Z}/p\mathbb{Z}##. So we can conclude by transitivity ##\log_g(h_1) + \log_g(h_2) \equiv \log_g(h_1h_2)## (mod p - 1). []

edit: sorry, I keep reading this question wrong, but this is the same stuck point I've gotten a few different ways... I'm not sure how to go from here, to the ##\log_g(h_1h_2) = \log_g(h1) + \log_g(h2)## for all ##h_1, h_2 \epsilon \mathbb{Z}/p\mathbb{Z}##.