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 gi=gj+k(p−1)=gj(gp−1)k. Pero, por definición de raíz primitiva, gp−1 pertenece a la clase residual del 1, es decir, se puede expresar como mp+1.
Sustituyendo en gi=gj(gp−1)k se obtiene gi=gj(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 gi=gj(Mp+1)=gj+Mpgj. Es decir, gi y gj son equiresiduales en la división entre p.
Ahora bien, partiendo de que gi,gj son equiresiduales en la división entre p, se tendría Mp=gi−gj=gj(gi−j−1). Así que gj(gi−j−1) es múltiplo de p. Pero gj es primo con p (por ser g raíz primitiva). Se sigue que gi−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 ge 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 gi,gj equiresiduales en la división entre p" se traduce a "i≡j(modp−1) si y sólo si gi≡gj(modp)" 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.