Disquisitiones Arithmaticae art. 49 Article 49. If $p$ is a prime number tat does not divide $a$, and if $a^t$ is the lowest power of $a$ that is congruent to unity relative to the modulus $p$, the exponent $t$ will either be $p-1$ or a factor of $p-1$.
I am looking for a proof of this that does not use the fact that $a^{p-1}\equiv 1\pmod p$ (with a,p defined as above). This fact makes the proof very easy.
Gauss's proof is as follows:
Since $\{1,a,a^2,...,a^{p-1}\}\equiv \{1,2,...,p-1\}\pmod p$, then the maximum possible value of $t$ is $p-1$, and the theorem will hold. Therefore, we only need to consider values of $t$ that are $<p-1$.
Consider $1,a,a^2,...,a^{t-1}$. Just as before, we have $\{1,a,a^2,...,a^{t-1}\}\in \{1,2,...,p-1\}\pmod p$, i.e. the set $\{1,a,a^2,...,a^{t-1}\}\pmod p$ is contained in $\{1,2,...,p-1\}$, and further more it is STRICTLY contained in it (i.e. not equal to it), because $t<p-1$. Therefore, consider a number $\alpha$ in $\{1,2,...,p-1\}$ that is not contained in $\{1,a,a^2,...,a^{t-1}\}\pmod p$. Multiply this number by $1,a,a^2,...,a^{t-1}$ to get the new set $\{\alpha,\alpha a,\alpha a^2,...,\alpha a^{t-1}\}$. We will show that all of the numbers in this set (when reduced mod p) are (I) distinct from each other (I), and (II) distinct from every number in $\{1,a,a^2,...,a^{t-1}\}\pmod p$.
I. To prove they are distinct from each other, suppose for contradiction that there are $m,n$ such that $\alpha a^m\equiv \alpha a^n\pmod p$, and WLOG $m>n$. Then $a^m\equiv a^n\pmod p$ or $a^{m-n}\equiv 1\pmod p$. But $m,n<t\implies m-n<t$, contradicting the fact that $t$ is the lowest possible positive integer such that $a^t\equiv 1\pmod p$.
II. To prove they are distinct from every number in $\{1,a,a^2,...,a^{t-1}\}$, suppose for the sake of contradiction that $\alpha a^m\equiv a^n$ with $m<n$. Then $\alpha\equiv a^{n-m}\pmod p$ with $n-m<t$, contradicting the fact that $\alpha$ is a number not contained in $\{1,a,a^2,...,a^{t-1}\}$. If however $m>n$, then we can multiply $\alpha a^m\equiv a^n\pmod p$ by $a^{t-m}$ to get $\alpha a^t\equiv a^{t-(m-n)}\pmod p$, and since $a^t\equiv 1\pmod p$ this becomes $\alpha\equiv a^{t-(m-n)}\pmod p$ with $t>t-(m-n)>t-t>0$, again contradicting the fact that $\alpha$ is a number not contained in $\{1,a,a^2,...,a^{t-1}\}$.
Therefore, the sets $A=\{1,a,a^2,...,a^{t-1}\}$ and $B=\{\alpha,\alpha a,...,\alpha a^{t-1}\}$ are mutually disjoint and are both contained in $C=\{1,2,...,p-1\}$.
Now, if $A,B$ fully make up the set $\{1,2,...,p-1\}$, then considering the cardinalities we have $|A|+|B|=|C|$, or $t+t=p-1\implies 2=(p-1)/t$, and the result follows.
Otherwise, we can do as before and consider a number in $\{1,2,...,p-1\}$, say $\beta$, that is not contained in either $A$ or $B$, and then consider $D=\{\beta,\beta a,...\beta a^{t-1}\}$ and continue as before (albeit with a few more cases to consider). The end result will again be $|A|+|B|+|D|=|C|$, or $3=(p-1)/t$, proving the result.
Otherwise, we will get $4=(p-1)/t$, $5=(p-1)/t$, and in general (since there are only finitely many possibilities), t will divide p-1, as required. QED
My problem with this argument is how on earth did Gauss think of it? I mean I can understand at the start when he considered $1,a,a^2,...,a^{t-1}$. This consideration is easy to arrive to, because just by considering the problem statement we have $a^t\equiv 1\pmod p\implies (a-1)(a^{t-1}+a^{t-2}+...+a+1)\equiv 0\pmod p$, and since $a\not\equiv 1\pmod p$ we get $1+a+a^2+...+a^{t-1}\equiv 0\pmod p$. And finally this might lead us to consider $1,a,a^2,...,a^{t-1}$. But the following steps of the proof, WHERE HE CONSIDERS SOME $\alpha$ NOT IN $\{1,a,...,a^{t-1}\}$, AND THEN PROCEEDS TO MULTIPLY IT BY EVERY MEMBER OF THIS SET (etc), is beyond me.
NOTE: I fully understand the argument, just not the motivation behind it.
I would extremely appreciate if someone can shed some light on the motivations behind Gauss's proof, or provide another one that is more enlightening. Remember,using the fact that $a^{p-1}\equiv 1\pmod p$ is NOT allowed.
Thanks.
 A: In order to show that $t$ divides $p -1$, we want to take $p-1$ objects and decompose them into a whole number of distinct groups of size $t$.
We already have one group $\{1,a,a^2,\dots,a^{t-1}\}$ and we'd like to use that to find more groups of size $t$. A natural way to try and find another group is to modify the one we have, and since we are looking at multiplication $\mod p$, it is natural to try and multiply our group by some $\alpha$. 
So we want to multiply $\{1,a,a^2,\dots,a^{t-1}\}$ by $\alpha$ to get $\{\alpha,\alpha a,\alpha a^2,\dots, \alpha a^{t-1}\}$, and we want the restriction that the $\alpha a^i$ are distinct, and that none of the $\alpha a^i$ can be equal to any of the $a^j$ we've seen already. In particular, since $1 \in \{1,a,a^2,\dots,a^{t-1}\}$ it is necessary that $\alpha \notin \{1,a,a^2,\dots,a^{t-1}\}$. However, we still need to verify that:


*

*The set $\{\alpha,\alpha a,\alpha a^2,\dots, \alpha a^{t-1}\}$ really has $t$ elements (i.e. $\alpha a^i \neq \alpha a^j$).

*The condition that $\alpha \notin \{1,a,a^2,\dots,a^{t-1}\}$ is also sufficient, not just necessary.


Gauss proceeds to do just that...
