# What is the intuition behind the Fermat-Euler's Theorem?

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$.
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$.
@vidit: Yes: so the order of the cyclic subgroup generated by $a$ in the multiplicative group of invertible elements should divide the order of the group of invertible elements. The order of the group of invertible elements is exactly $\varphi(n)$, so we can write $\varphi(n) = kq$ where $q$ is the multiplicative order of $a$. So $a^{\varphi(n)} = a^{kq} = (a^q)^k = 1^k = 1$. I don't see what else to "elaborate". I gave you all the intuition I can squeeze out of that particular line of reasoning. – Arturo Magidin May 6 '12 at 20:24