Por definición, $i,j$ son equiresiduales en la división entre $p-1$ si y sólo si $i=j+k(p-1)$. De aquí que $g^i=g^{j+k(p-1)}=g^j(g^{p-1})^k$. Pero, por definición de raíz primitiva, $g^{p-1}$ pertenece a la clase residual del 1, es decir, se puede expresar como $mp+1$.
Sustituyendo en $g^i=g^j(g^{p-1})^k$ se obtiene $g^i=g^j(mp+1)^k$. Y en la expansión del binomio se obtienen puros múltiplos de p, excepto el término final que es 1. De aquí que $(mp+1)^k$ sea equiresidual con el 1 y se pueda expresar como $Mp+1$. Finalmente, en la sustitución, se obtiene $g^i=g^j(Mp+1)=g^j+Mpg^j$. Es decir, $g^i$ y $g^j$ son equiresiduales en la división entre $p$.
Ahora bien, partiendo de que $g^i,g^j$ son equiresiduales en la división entre p, se tendría $Mp=g^i-g^j=g^j(g^{i-j}-1)$. Así que $g^j(g^{i-j}-1)$ es múltiplo de $p$. Pero $g^j$ es primo con $p$ (por ser $g$ raíz primitiva). Se sigue que $g^{i-j}$ es equiresidual con el 1.
De aquí se debería concluir que $i,j$ son equiresiduales en la división entre $p-1$. Pero ¿cómo? La respuesta está en la definición de raíz primitiva: como $g$ es raíz primitiva de $p$ y éste es primo, entonces $p-1$ es el menor exponente positivo (es el orden de $g$) con el que se logra que $g^e$ sea equiresidual con el 1 en la división entre $p$. Entonces $p-1$ es el orden de $p$ y cualquier otro exponente $e$ que logre esa equiresidualidad es múltiplo de $p-1$.
De aquí que $i-j$ sea múltiplo de $p-1$. Como se quería.
Nota 1: La demostración está deliberadamente escrita en lenguaje pre-congruencias; el lector familiarizado con la aritmética modular no tendrá ningún problema en traducirla a ese lenguaje.
Nota 2: En lenguaje de la aritmética modular "$i,j$ equiresiduales en la división entre $p-1$ si y sólo si $g^i,g^j$ equiresiduales en la división entre $p$" se traduce a "$i\equiv j (\mod p-1)$ si y sólo si $g^i\equiv g^j (\mod p)$" y aquí es fácil ver que la propiedad es logarítmica: potencias "iguales", exponentes "iguales" (con los módulos "ligeramente" diferentes). Claramente, la base es la raíz primitiva $g$.
