如何用MATLAB证明费马大定理

matlab只能处理有限情况，显然不可以昌汪裂通过matlab证明费马大定理。对于费马大定理Andrew Wiles的证明我作为数学专业学生觉得这辈子是没机会看懂了，如果你不是数耐闭学专业，劝你也放弃陵指吧。如果有兴趣可以看一下n=4和n=3时的证明。n=4是最简单的情况，费马本人就给出了正确的证明。

解决方案1：

直接用缉鼎光刮叱钙癸水含惊ifft()例如信号x

y=fft(x)%对信高友号傅里叶变换到频域

z=ifft(y)%对信号y傅里滚念搜叶反变换到时域，

解决大历方案2：

工具箱啊。IFFT()函数

从一个例题：【HDU 3037】 Saving Beans 来开始Lucas定理的应用。

题目大意为：松鼠要从n棵树上摘一共m个豆子，结果的方案数对素数p（不大于1e5）取模，求解。

思路：

可以理解为m个豆子分为n份，求分的方法个数。

由插板法来对m个数进行划分，由于可能某棵树没有摘豆子，可以理解为：x1+x2+x3+……+xn=m的解的个数，即为C(m+n-1,n-1)。（将m颗豆子加上n-1个板子的位置，得到的序列再从中取n-1个板子的位置）=C(m+n-1,m)。

由于m的值取0~m，那么就得sum=C(n-1,0)+C(n,1)+C(n+1,2)+C(n+2,3)+……+C(m+n-1,m)。

利用公式C（n，r）=C（n-1，r）+C（n-1，r-1）=C（n-1，r）+C（n-2，r-1）+C（n-3，r-2）晌竖……

sum=C（n+m，m）。

也就是说，接下来的算法变成了C（n+m，m）%p。

然后就是Lucas定理的运用：

Lucas（m，n，p）=C（m%p，n%p，p）✲Lucas（m/p，宴或大n/p，p）。

Lucas（x，0，p）=1。

这里可以采用的方法是递归求解。

简单的理解就是：

以求解n! % p 为例，把n分段，每p个一段，每一段求得结果是一样的。但是需要单独处理每一段的末尾p,2p,...,把p提取出来，会发现剩下的数正好又是(n/p)! ，相当于划归了一个子问题，这团销样递归求解即可。

这个是单独处理n！的情况，当然C(n,m)就是n！/(m! *（n－m）！），每一个阶乘都用上面的方法处理的话，就是Lucas定理了.

Lucas最大的数据处理能力是p在10^5左右。

而C(a,b) =a! / ( b! ✲ (a-b)! ) mod p

其实就是求 ( a! / (a-b)!) ✲ ( b! )^(p-2) mod p

上面这一步变换是根据费马小定理：假如p是质数，且a,p互质，那么a的（p-1）次方除以p的余数恒为1,

那么a和a^(p-2)互为乘法逆元，则（b / a) = (b * a^(p-2) ) mod p)

b!与b! (p-2)互为乘法逆元，即b!✲b! (p-2)=1，那么，

//快速幂a^b % k

//求C(n, m)%p p最大为10^5n, m可以很大！

用下面的Lucas定理程序实现就能得出结果，实现过程中要注意乘法时的强制转换

---