证明这样的定理，最好还是执果索因。因为公式只是描述一个客观事实。充满好奇心的初学者看到这样简洁但毫无头绪的公式，很容易失去方向。要知道我们的目的是证明这个式子，而不是追究这个式子是怎么发明的。不要觉得一个式子看起来简单，就可以用一个很简单的逻辑推算出来。例如这样的式子，高中生就能看懂其中所有的符号，但是想要推导它，则非学复变函数不可。
1. 正向推演
先看看欧拉定理的公式：
要证明这个式子，首先要回归 的定义。 的含义是小于、且与互质的数字的个数。比如令 ，则1、3、5、7都与之互质。那么 。
现在，我们把这个数的集合记作，即
现在把中的每个元素乘以，得到新的集合，即
可以证明模意义下，，也就是对。更具体地说，如果，那么。
第二节会证明这个性质，现在先让我们继续。既然，那么A和B中的元素各自在模意义下相乘，得到的结果也是一样的。即
根据欧拉函数的定义，一定有，所以一定有模意义下的模逆元（第三节会做一个简单的证明）。用的模逆元消掉等号两边的，可以得到最终的式子：
2. 证明模意义下A=B
为了方便区分两个集合，我们记。其中的元素来自欧拉函数的定义，所以, ；中的元素经过模运算，因此。
证明的关键在于或者的性质。由于，而欧拉定理的前置条件约定，所以，自然（对于此有疑问的读者，可以思考一下辗转相除法成立的原理：）。又因为，所以恰好符合了的定义，也就是
但是这样只能证明，不能证明。要证明，就要证明两两不同，这样，A和B中就都拥有了个元素，那么成立。用数学语言表示，就是要证明。
可以用反证法证明这一点。假如满足。由于，所以一定存在的模逆元。使用模逆元消去，就得到了。而前面提到, ，所以不存在且的情况。因此假设不成立，原命题成立。
3. 证明只有时，才存在的模逆元，即
同样也是反证法，假如，也就是，使得，那么对同余式移项目得到
显然当且仅当是的倍数，也就是时，同余式成立。对其进行简单的移项，得到。由于，所以我们从和中分离公因数，剩下的部分记作和。得到：
由于，所以。这个不等式显然没有正整数解，因此得证假设不成立。