首先提几个概念：
质数又称素数。指在一个大于1的自然数中，除了1和此整数自身外，没法被其他自然数整除的数。
互素（relatively primeì）：若N个整数的最大公因数是1，则称这N个整数互素。
整除：就是若整数“a” 除以大于0的整数“b”，商为整数，且余数为零。 我们就说a能被b整除（或说b能整除a），记作b|a，读作“b整除a”或“a能被b整除”。
费马小定理：若p是素数，a是正整数且不能被p整除，则：a^(p-1) ≡１（mod p）。
欧拉定理：对任意互素的a和n，有：a^φ(n) ≡ 1 (mod n)。
因为欧拉定理是费马小定理的推广，所以欧拉定理的条件对任意互素的a和n与费马小定理的条件若p是素数，a是正整数且不能被p整除相比不可能是缩小范围。
通过证明也可以得出费马小定理的条件其实就是(a,p)=1等同于a和n互素。
1.p是素数
2.p|a<>0
得出a中不包含p的因子，那么(a, p)=1。证毕。