- #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}##.