First things first: I have posted my proof here because I don't know where to post questions about number theory. What I needed to proof definitely wasn't an advanced math theorem; just a simple task from an old book of mine.
Prove that the smallest number natural number [imath] e [/imath], satisfying the equation [imath]a^e \equiv 1\pmod p[/imath], must divide (p-1).
My proof:
Suppose the opposite: we assume that [imath] e[/imath] is the smallest natural number satisfying [imath]a^e \equiv 1\pmod p[/imath] (later I will not write mod p) but it does not divide [imath] (p-1) [/imath]. Then, we can say [imath]p-1=ke+r[/imath], where [imath]0 < r < e[/imath]. By Fermat's Little Theorem, it must be true that [imath]a^{ke+r} \equiv 1[/imath] or 1) [imath](a^e)^k*a^r \equiv 1[/imath]. By our assumption, [imath]a^e \equiv 1[/imath], which also means that [imath](a^e)^k \equiv 1[/imath]. Knowing this, we can rewrite 1) as [imath]a^r \equiv 1[/imath]. We definitely know [imath]r \not = 0[/imath] and [imath]r < e[/imath]. We've just arrived at contradiction: [imath]e[/imath] was assumed to be the smallest natural number satisfying our equation but we just have found a smaller one. So, [imath]e[/imath] must divide [imath] (p-1) [/imath].
Prove that the smallest number natural number [imath] e [/imath], satisfying the equation [imath]a^e \equiv 1\pmod p[/imath], must divide (p-1).
My proof:
Suppose the opposite: we assume that [imath] e[/imath] is the smallest natural number satisfying [imath]a^e \equiv 1\pmod p[/imath] (later I will not write mod p) but it does not divide [imath] (p-1) [/imath]. Then, we can say [imath]p-1=ke+r[/imath], where [imath]0 < r < e[/imath]. By Fermat's Little Theorem, it must be true that [imath]a^{ke+r} \equiv 1[/imath] or 1) [imath](a^e)^k*a^r \equiv 1[/imath]. By our assumption, [imath]a^e \equiv 1[/imath], which also means that [imath](a^e)^k \equiv 1[/imath]. Knowing this, we can rewrite 1) as [imath]a^r \equiv 1[/imath]. We definitely know [imath]r \not = 0[/imath] and [imath]r < e[/imath]. We've just arrived at contradiction: [imath]e[/imath] was assumed to be the smallest natural number satisfying our equation but we just have found a smaller one. So, [imath]e[/imath] must divide [imath] (p-1) [/imath].
