First, we have
***********
If $a$ is primitive root of $n$, the congruence a^x=b (mod p) is always
possible, except if b = 0 (mod p), and has only one solution less than
p-1. We call $x$ the index of $b$ (mod n) in the system of base $a$.
***********
This terminology is found in Gauss's _Disquisitiones_ and I
believe both the idea and the term were introduced there. The term
remained standard for this idea until quite recently, when people
began using the more descriptive phrase "discrete logarithm". The
index in this sense is of course dependent on the choice of generator
a, not just on b and n.
Second, we have
**********
the minimum $r$ such that b^r=1 (mod n).
**********
Gauss has no special name for this. The word now used for it
is always "order". This use arose in group theory, originally
just for permutations; if I understand right, Wussing's _Genesis
of the Abstract Group Concept_ (II,2) says that it was introduced
by Abel but popularized by Cauchy in 1844-45 (for permutations
only). The use of "order" in the related sense of the size of a
subgroup is also due to Cauchy at that time. Presumably the word
was brought over to the number-theoretic setting once people began
to develop the abstract idea and could speak of the multiplicative
group mod n.
Note that this second idea is never (to my knowledge) called
an index. What "index" means in group theory is of course the
number of cosets of a subgroup. This is then (n-1)/order in the
second situation, so it is related but not the same. The
use of the word "index" in this sense seems to be due to Cauchy
in 1815 (Wussing, loc. cit.). Again, of course, he was looking
only at subgroups of the symmetric groups. He was interested
in large ones (in connection with a study of functions that took
on few different values when the variables were permuted), and
he knew Lagrange's theorem that the order of the subgroup would
divide n!, so the "index" in this sense (= the number of values the
function assumed) was more natural for him to consider than the
order.
William C. Waterhouse
Penn State