Here is another way to prove Euler's generalization. You do not need to know the formula of $\varphi(n)$ for this method which I think makes this method elegant.
Consider the set of all numbers less than $n$ and relatively prime to it. Let $\{a_1,a_2,...,a_{\varphi(n)}\}$ be this set.
Consider a number $c < n$ and relatively prime to it i.e. $c \in \{a_1,a_2,\ldots,a_{\varphi(n)}\}$.
First observe that for any $a_i$, $c a_{i} \equiv a_{j} \pmod{n}$ for some $j$.
(True since $c$ and $a_i$ are themselves relatively prime to $n$, their product has to be relatively prime to $n$).
And if $c a_{i} \equiv c a_{j} \pmod{n}$ then $a_i = a_j$.
(True as cancellation can be done since $c$ is relatively prime to $n$).
Hence, if we now consider the set $\{ca_1,ca_2,...,ca_{\varphi(n)}\}$ this is just a permutation of the set $\{a_1,a_2,...,a_{\varphi(n)}\}$.
Thereby, we have $\displaystyle \prod_{k=1}^{\varphi(n)} ca_k \equiv \prod_{k=1}^{\varphi(n)} a_k \pmod{n}$.
Hence, we get $\displaystyle c^{\varphi(n)} \prod_{k=1}^{\varphi(n)} a_k \equiv \prod_{k=1}^{\varphi(n)} a_k \pmod{n}$.
Now, note that $\displaystyle \prod_{k=1}^{\varphi(n)} a_k$ is relatively prime to $n$ and hence you can cancel them on both sides to get
$$c^{\varphi(n)} \equiv 1 \pmod{n}$$ whenever $(c,n) = 1$.
Best Answer
$\require{begingroup}\begingroup\newcommand\Z{\mathbb Z}$Fermat's little theorem tells us something modulo a prime $p$: $a^{p-1}\equiv1\pmod p$: the 'modulus' of the congruence is $p$, not $a$. Now if you're asked to find some residue modulo $13$, then you would use congruences to reduce the given value modulo $13$, i.e., the congruences will have modulus $13$.
If for example you want to find the remainder of $50^{50}$ when divided by (='modulo') $13$, probably the calculations would look like $$50^{50}\equiv\ldots\equiv\ldots\equiv\ldots\equiv\ldots\pmod{13}$$ and the rightmost dots should contain a number between $0$ and $12$ (inclusive).
I'm not sure why you want to use congruence classes for finding $50^{50}\bmod13$, but, as you're asking: a congruence class modulo $m$ is defined as a (non-empty) subset of $\Z$ in which all elements are (pairwise) congruent modulo $m$. Moreover, the congruence class should contain all integers congruent to its elements.
For example, the congruence classes modulo $2$ are precisely the set of even integers and the set of odd integers. The congruence classes modulo $3$ are the integers of the form $3k$, those of the form $3k+1$, and those of the form $3k+2$. In general, there are $|m|$ congruence classes modulo $m$, and a shorthand to write them is $m\Z,\,m\Z+1,\,m\Z+2,\,\ldots,\,m\Z+|m|-1$.
Now if you're asked to find $50^{50}\bmod13$, since $50^{50}$ is a big number probably you want to reduce the exponent and base, without affecting the value modulo $13$. Fermat's Little Theorem (FLT) is a handy tool to reduce exponents: as $13\nmid50$, FLT gives $50^{12}\equiv1\pmod{13}$. We can use this as follows: $$50^{50}=50^{4\cdot12}\cdot50^2=(50^{12})^4\cdot50^2\overset{\rm\small FLT}\equiv1^4\cdot50^2=50^2\pmod{13}$$ and look, we've reduced the exponent from $50$ to $2$ by subtracting a multiple of $12=13-1$.
Because $50^2$ is still not so small, let us try to reduce the base modulo $13$. We could replace $50$ by its remainder modulo $13$, which is $11$. This would leave use with calculating $11^2\bmod13$. A little easier is to subtract $13$ one more time: $$50^2\equiv(50-4\cdot13)^2=(-2)^2=4\pmod{13}.$$