2
$\begingroup$

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.

1 Answers 1

9

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$.

  • 2
    @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.2012-05-06