Primitive roots/discrete logs

[five]

I sort of get this stuff, but I can't seem to show that a few congruences hold.

From what I understand, a primitive root of a prime p is a number such that the order is p-1. (i.e. 2 is a primitive root of 13 because 2^12 is congruent to 1 mod 13).

From my understanding, discrete logs work the opposite way, so log(2,13) (1) is congruent to 0 mod 12. (Here, I included the 2 and 13 to indicate the base and modulus.)

How do you show that
log(b,p) (st) is congruent to log(b,p) (s) + log(b,p) (t) ?

[bigpooch]

You stated:

[ QUOTE ]
(i.e. 2 is a primitive root of 13 because 2^12 is congruent to 1 mod 13).


[/ QUOTE ]

It's not quite that: a is a primitive root of a prime number
p IFF the least positive integer n such that a^n is
congruent to 1 mod p is (p-1).

Actually, the logarithms aren't unique as you may know (for
prime p, adding any integer multiple of (p-1) will give a
different logarithm).

In any case, it's simply working with definitions:

Let x be a logarithm (base b, prime p) of s,
y be a logarithm (base b, prime p) of t.

Then, by definition, b^x is congruent to s (mod p)
and b^y is congruent to t (mod p). Multiplying,

(b^x)*(b^y) is congruent to s*t (mod p) or

b^(x+y) is congruent to st (mod p)

or (x+y) is a logarithm (base b, prime p) of st.

This is another way of saying that (x+y) is congruent
modulo (p-1) to ANY other logarithm (base b, prime p) of st.

Here, the congruence is modulo (p-1) so it's more accurate
to state that

log (st) is congruent to log (s) + log (t) mod (p-1)

where the logarithm is (base b, prime p).

Also, discrete logarithms can be generalized to groups in
abstract algebra.

[five]

Big Pooch,

Thanks a ton. Wow. That was very helpful.

I tried to show two other congruences, and was wondering if this is ok:

All logs are really log (base b, prime p)

Show log(s^n) is congruent to n log (s):

By the congruence in the post above,
log(s^n) is congruent to log(s) + log (s^(n-1))
which is congruent to log(s) + log(s) + log(s^n-2).

This can be written as j*log(s) + log(s^(n-j)).

When j = n-1, we have (n-1)*log(s) + log(s^1) which is congruent to n*log(s).

The second congruence is to show that if t is the inverse of s mod p, then log(t) is congruent to (-1)*log(s) mod (p-1).

By definition, st is congruent to 1 mod p, can we say that t is congruent to 1/s (or s^-1) mod p?
(I'm fuzzy on the dividing rule here. It has something to do with fields, etc. Since we are operating modulo a prime p, is this ok?)

If so, then log(t) is congruent to log(s^-1) mod p-1, and by the above congruence, log(t) is congruent to (-1)log(s).

Thanks again for your help Pooch.

[bigpooch]

To show log(s^n) is congruent to n log(s) for ANY integer
n, you would have to break it down to some cases. For n=0,
this is by definition: s^0 is defined to be e where e is
the identity element. Also, log(e) = 0 by definition; in
our example, e = 1. For n >=1 , you can just use
mathematical induction and for n<0, you need to show the
other congruence in your post.

Yes, every element of the GROUP (that's a specific kind of
algebraic object: a set with an associative operation that
admits inverses, has an identity element and the operation
is obviously closed: x, y are in the group G implies x*y is
also in the group where * is the operation) of nonzero
modulo classes for a prime p has an inverse.

Actually, what I am trying to say that the nonzero modulo
classes of a prime p form a group under the operation of
"multiplication". Because this is a group, all elements,
by definition must have an inverse, i.e., for any element
a in the group, it makes sense to talk about 1/a or a^(-1).