在已知朴素的欧拉定理时,证明模m情况下的扩展欧拉定理只需要对m进行素因子分解。根据中国剩余定理,只要我们能够说明对于任意的 均有:
即可完成证明。现在我们进行分情况讨论,设 其中b、p互素则根据朴素的欧拉定理,我们知道:
至此我们只需要说明 即可完成任务。r=0时命题是显然的,所以我们接下来只需要r>0的情况。由于 所以这种情况下:
综上所述,我们就能发现:
对于一切整数a和正整数m、n和v均成立。这便是广义欧拉定理。