Can someone give me an intuition behind the working of Fermat-Euler's theorem? I am not looking for definition nor for proof (I know both of them). $$a^{\phi(p)} \equiv 1 \pmod p$$
This is what I understand.. when we multiply a positive number $a$ less than $p$, $\phi(p)$ times with itself (raising to the power of $\phi(n)$) and then divide it by $p$, the remainder is 1. In mathematical terms $$a^{\phi(p)} = qp + 1$$ where $q$ is a positive number and $\phi(n)$ is Euler's Totient Function.
The intuition is the same: since multiplying every invertible element modulo $p$ by $a$ just permutes the invertible elements, if we let $x$ be the product of all invertible elements we must have $a^{\#\text{ of invertible elements}}x \equiv x$, suggesting it "should" be equal to $1$.
Of course, this is basically a proof, but this particular theorem is so "close to the surface" that any good intuition as to why it should be true will be essentially the same as a proof.
(Form a group-theoretic point of view, it's just Lagrange's Theorem).
Note: For arbitrary $p$ (that is, not necessarily a prime), we must require that $a$ be relatively prime to $p$. For prime $p$ this can be achieved by simply requiring that $a$ be positive and smaller than $p$, but for arbitrary numbers this is not enough (e.g., $3$ will not work modulo $6$). And we don't really need $a$ to be smaller than $p$ even in the prime case; for instance, $11^6\equiv 1\pmod{7}$ works just as well. The real requirement is that $\gcd(a,p)=1$.