1. 首先验证当a=1时，费马小定理是否成立。由于任何数的1次方与其自身对模任何数都同余，因此费马小定理在这种情况下显然成立。
2. 接下来，假设对于某个正整数a，费马小定理成立，即a的p次方与a对模p同余。
3. 然后考虑(a+1)的p次方与a+1对模p的关系。根据二项式定理，(a+1)的p次方可以展开为：
(a+1)^p = a^p + p*a^(p-1) + ... + p*a + 1。
4. 在这个展开式中，除了第一项和最后一项是p的倍数外，中间的各项都是p的倍数。因此，(a+1)^p与a^p+1对模p同余。
5. 由假设知a^p与a对模p同余，所以(a+1)^p与a+1对模p同余。
通过数学归纳法，我们证明了费马小定理对于所有正整数都成立。
