Proof Explanation: If $n$ is a positive integer and $a$ is relatively prime to $n$, then $a^{\phi(n)}\equiv 1 \pmod n$. I was reading a book about group theory and there was a proof given about Euler's Theorem.  Euler's theorem:If $n$ is a positive integer and $a$ is relatively prime
to $n$, then $a^{\phi(n)}\equiv 1 \pmod{n}$.
The proof given in the book is as follows:

We know that,  if $G$ is a finite group and $a\in G$, then $a^{o(G)} = e$($e$ is the identity element in $G$). Also, the numbers less than $n$ and relatively prime to $n$ formed a group under multiplication $\bmod n$. This group has order $\phi(n)$. Now , the group is finite hence, $a^{\phi(n)}\bmod n =1$ and thus, $a^{\phi(n)}\equiv 1 \pmod n$.

However, I am not quite getting this proof . The theorem says any $a$ relatively prime to $n$ is valid and $a>n$, $a=n$, $a<n$ . But in this proof, we only considered $a$ to be the group elements i.e the numbers less than $n$ and relatively prime to $n$. How is the proof valid? Also , can $a$ be negative ? The theorem only states $n$ to be a positive integer and $a$ is relatively prime to $n$. I am not quite getting it.
 A: The statement is about $a^{\phi(n)}\equiv 1\pmod n$.  This is an equivalence $\mod n$ and all statements about equivalence $\mod n$ are equally true for any representative from the equivalence class that $a$ belongs to.  That is why they are called equivalence classes.
Review:  Given $n$ we can partition the integers into sets $[0],[1],[2], .....,[n-1]$ where $[k]=\{k+ mn|m\in \mathbb Z\} = \{w\in \mathbb Z| w\equiv k\pmod n\}=\{w\in \mathbb Z$ where $n$ divides $w-k\}$. [Partition means every integer is in exactly one of the sets]
We use the notation to mean $a \equiv b \pmod n$ to mean any and all of the following equivalent statements 1) $n$ divides $a-b$, 2) $b= a + mn$ for some $m \in \mathbb Z$ 3) $a$ and $b$ have the same remainder when divided by $n$ 4) $a,b \in [r]$ for the same equivalence class $[r]$ (Note: we can notate equivalence classes so that $[r]=[a]=[b]$)
Now the key issue is that addition, subtraction, multiplication, exponentiation (but not division except as involves relatively prime numbers and requires a second introduction) are preserved by modulo equivalences.
That is to say:   If $a \equiv a' \pmod n$ and $b \equiv b'\pmod n$ the $a+b\equiv a'+b'\pmod n; a-b\equiv a'-b'\pmod n; ab \equiv a'b' \pmod n$ and for all $k \in \mathbb N$ $a^k \equiv a'^k \pmod n$.
Thus anything that you prove for any $a$ about $\mod n$, you actually prove for all $a'\equiv a\pmod n$.
And this includes relative primeness.   If $a\equiv b\pmod n$ then $\gcd(a,n) = \gcd(b,n)$.  So $a$ is relatively prime to $n$ if and only if $b$ is relatively prime to $n$.  Pf:  If $d|n$ then $d|mn$ for all $m\in \mathbb Z$.  If $d|a$ and $b\equiv a \pmod n$ then $b = a + mn$ for some integer $m$.  So as $d|a$ and $d|n$ then $d|b$.  So common divisors of $a$ and $n$ are exactly the same as the common divisors of $b$ and $n$.
......
To prove the statement:  For all $a$ relatively prime to $n$ we have $a^{\phi n}\equiv 1\pmod n$.  It is sufficient to not prove it for all $a\in \mathbb Z$ but to just prove it for one representative from each of the equivalence classes $[0],[1],[2],.....,[n-1]$.
That is because if it is true for one $r \in [r]$ it will be true for all $a \in [r]$ and and so if it is true for all $1,2,3,....,n-1$ where $r$ is relatively prime to $n$.  (We don't have to worry about $0$ as $0$ is not relatively prime to $n$) then it will be true for all integers $a$ in $[1],[2],.....,[n-1]$ were $[r]$ are all relatively prime to $n$.  That is to say, for all integers that are relatively prime to $n$.
......
Now the integers $\{k| 1\le k < n; \gcd(k,n)=1\}$ form a group under multiplication $\mod n$.  This is actually a simplification.  This would be true for $G= \{c_i| \}$ where each $c_i$ is any integer $c_i \equiv i \pmod n$ and $\gcd(i,n)=1$ and all $i$ relatively prime to $n$ are represented. In that case $G$ would also be a group.
Thus if $\gcd(a,n) = 1$ then $a\not \equiv 0 \pmod n$ and we can make such a set of $G=\{c_i\}$ where $a$ is one of the members.
And as it is a group under modulo multiplication:  $a^{|G|} = a^{\phi n} \equiv 1 \pmod n$.
A: Since this is modular arithmetic, we can map any number to a number between $0$ and $n$, so every element of the group is defined to be in $[0,n)$. Therefore, $a≥n$ isn't part of the group. However, since $a \equiv b$ implies $ac \equiv bc$, $a^{\phi(n)} \equiv 1$ (mod $n$).
