Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

1 Answer

up vote 8 down vote accepted

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

share|improve this answer
    
Lagrange's Theorem- The order of a subgroup should divide the order of a group? And can you please elaborate a little more on the intuition. –  vidit May 6 '12 at 20:21
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. –  Arturo Magidin May 6 '12 at 20:24
    
Thank you Sir :) –  vidit May 6 '12 at 20:26
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.