乘积差公式

本文给出一种新颖的乘积差公式，而我们早已熟知的平方差公式，只是其中的一个特例。

 一、平方差公式                              

打开数学手册的第一页，就能够看到平方差公式，a² - b² =(a-b)(a+b)。这个公式的特点，是可以把两个乘积之间的差值，直接转化成为一个因数分解式。因为每一个乘积的乘数都是相等的，所以称其为平方差公式。

 二、乘积差公式

当乘积的乘数都不相等时，在两个乘积之间进行一次减法，仍然可以获得类似的因数分解式吗？老师没教过，数学手册上也没有，如果有需求怎么办？那就发明一个呗！

假设乘积A = a₁*a₂，允许其中的乘数a₂≥a₁，令C_a = a₂–a₁；设B = b₁*b₂，其中b₂≥b₁，令C_b = b₂–b₁。当这两个乘积相减时，可有乘积差公式，

A – B = a₁*a₂ - b₁*b₂ =（a₁- b₁）（a₂+ b₁）+(C_a- C_b)*b₁

如果C_a = C_b，那么简化为，

a₁*a₂ - b₁*b₂ =（a₁- b₁）（a₂+ b₁）

这就是说，即使a₁ ≠ a₂，b₁ ≠ b₂，只要a₂–a₁ = b₂–b₁，两个乘积之差仍可被直接写成一个因数分解式。这是一个要更加广义的公式，当a₁ = a₂，b₁ = b₂时，就进一步简化成为平方差公式。

当b₁ ≠ b₂时，貌似在这个公式中，并没有体现出有乘数b₂什么事；不过，从公式的证明过程看，没有问题。

显然，这种新型的乘积差公式要比平方差公式高级些，用途也要广泛得多。从它的基础性而言，如果今后哪本书中没有这个公式出现，那就只是本数学书而已，不能被称为数学手册了吧？

【证明】

（a₁- b₁）（a₂+ b₁）= a₁*a₂ + a₁*b₁ - b₁*a₂ - b₁*b₁

= a₁*a₂ - (a₂-a₁)*b₁ - b₁*b₁

= a₁*a₂ - C_a*b₁ - b₁*b₁

= a₁*a₂ – b₁*（C_b+b₁）

= a₁*a₂ - b₁*b₂

证明完毕。

还可以验证一下。已知1048575-264195 = 784380，若能获知它们的乘积形式，1048575 = 1023*1025，其中C_a = 1025-1023 = 2，264195 = 513*515，C_b = 515-513 = 2，这时C_a = C_b；就可以直接利用乘积差公式，同样得到 ，

1048575-264195 = 1023*1025–513*515 =（1023-513）（1025+513）= 510*1538 = 784380

784380已被分解成为两个510和1538两个因数，验证无误。

当C_a ≠ C_b时，公式的证明方法类似（略去），但可验证一下。

已知1048575–729 = 1047846，若知1048575 = 1023*1025，C_a = 1025-1023 = 2，729 = 27*27，C_b = 27-27 = 0，这时C_a - C_b = 2；直接利用乘积差公式，同样可有，

1048575–729 = 1023*1025-27*27 =（1023-27）（1025+27）+（2-0）*27 = 996*1052 + 54 = 1047846

当乘积的表达形式并不唯一时，例如，729 = 27*27 = 9*81，这时C = 81-9 = 72,乘积差公式仍然可以成立，

1048575–729 = 1023*1025-9*81 =（1023-9）（1025+9）+（2-72）*9 = 1014*1034 - 630 = 1047846

验证无误。

这就是说，即使同一个整数写成不同乘积的形式，乘积差公式均可适用。

上述讨论内容属于初等代数的范围，既是基础也非常简单实用。下节的讨论要略微复杂一些，但中学水平仍可大致理解；不过，不是从事数学工作的朋友不看也罢。

 三、乘积差公式在计算最大公约数时的应用

1）最大公约数背景简介

目前常用的最大公约数算法，有质因数分解法、短除法、碾转相除法和更相减损法，但它们的计算复杂度都是指数时间等级。通俗点说，当两个数值变大时，求出它们最大公约数所需要的计算量，将以指数的形式急剧增长。

简单地介绍一下其中两种。质因数分解法，是先把A和B两个合数分别进行因数分解，然后找出所有相同的因数来；这种算法的计算量，显然与A和B的数值大小有关。更相减损法，是利用把A和B两个数相减以后，它们的差值仍将保留着与A和B之间相同公约数的原理，不断地进行减法计算，直到获取最大的公约数。例如，假设A = g*a，B = g*b，其中g是它们的最大公约数；而它们的差值，A – B = g*(a-b)，仍然含有相同的公约数。

别看最大公约数的概念非常简单，在小学五年级时就应该可以学到，但相应的算法却有上千年历史了。而且，它被认为是一个NP完全问题，因此属于当今最顶尖的数学难题。简单地说就是，这类问题存在着计算量比较小，复杂度为0(n^k)的多项式时间等级算法吗？其中n代表A或B数值的位长；无论 k的数值有多么大，是个常数即可，但是越小计算量就越少。这个问题看似简单其实极难，所以目前尚无定论。有些难题，现在没有好的解法，并不代表将来就一定没有；但不幸的是，对于所有的NP完全问题，绝大多数数学家都猜测：将来也不会有。

在博主创立的一种数字体系中，认为任意一个整数，除了可以用有理数与无理数、实数与虚数、奇数与偶数等常规的分类方法，对它们进行简单分类以外，还可以被进一步细化描述；依照整除关系式，把它们分为不同类型的整除关系数。在这种新的数字分类体系下，取得了一些有意义的成果（例如因数分解、秘钥破译等等），部分内容已经发表在“中国科技论文在线”上，详见“合数、费马数较大因数的快速筛选”、“余数的等差级数表达”、“快速模除求余算法”、“一种新型的因数分解算法”等论文。

随着研究的深入，因为后续的更多成果属于原创性质，已无法给出洋跟班似的参考文献，不适应、或者说是无法在现有的科学刊物上，以八股文的形式顺利地发表。而隐藏已经取得的成果，是对人类知识的不尊重。因此，博主有选择性地将部分成果在博客中发布，是非功过由世人去评说。

2）整除关系数的定义

在大多数情况下，我们无法把一个合数，立即用乘积的形式来表达，但很容易得到一个整除关系式。

设整数A的整除关系式为，A = a₁*a₂ + r_a，其中a₁为除数，a₂为系数，a₂≥a₁，r_a为余数。令C = a₂–a₁，假如a₂ = a₁，那么C = 0，可称整数A为C0r_a类型的整除关系数。如果a₂ - a₁ = 1，那么C = 1，称其为C1r_a型。其余以此类推。

例如，2603 = 51*51+2，因为C = 51-51 = 0，余数R = 2，则称其为C0R2型的整除关系数。

设整数B的整除关系式为，B = b₁*b₂ + r_b，其中b₁为除数，b₂为系数，r_b为余数，同样定义C = b₂–b₁。

当r_a = r_b时，如果A和B的C值也相同，那么A和B就属于同一个类型的整除关系数。这就是说，整除关系数是按照整除关系式中，系数与除数的差值C，以及余数的大小来进行分类的。属于同一个类型的整除关系数可有无数多个，例如3*3+2,5*5+2，……，均属同类。

本节只是为了统一，定义a₁为小于A^1/2且最接近A^1/2的某个奇数，a₂≥a₁，但是这种定义可以放宽。也就是说，如有需要，同一个整数，当改变除数a₁时，可以被写成多种不同的整除关系数，也不一定要求余数r_a＜a₁。

既然这种崭新的数字分类体系可以适用于所有的整数（本主认为在虚数领域里也可以展开），那么一个有意思的问题随之而来，以整除关系数的形式进行减法运算，相比原有的数学体系，有什么特别的好处吗？乘积差公式就是在这个研究过程中被发现的。博主的结论是：同类整除关系数之间的一次减法计算，如果应用乘积差公式，可以使得因数分解的效率倍增。

3）计算最大公约数举例

假如要求两个整数43046723（=19*2265617）和2603（=19*137）之间的最大公约数，按照更相减损法，首先需要把它们相减。那么，43046723–2603 = 43044120 = 5*8*1076103，显然仅靠一次减法是无法得到它们的最大公约数17，还需要对1076103继续进行分解。但是，如果先把它们转换成为整除关系数的形式，43046723 = 6561*6561+2，2603 = 51*51+2，再进行减法计算；因为它们是同类型的整除关系数，可以根据乘积差公式直接有，

43046723–2603 =（6561-51）（6561+51）+2–2 = 6510*6612 = 5*8*651*1653

同样是在两个整数之间进行了一次减法计算，但是由于对整数的表达方法不同，利用乘积差公式，就可以把1076103直接分解为651和1653两个因数。即使它们并不一定是质数，但是需要继续进行质因数分解的数值却大约降低了平方倍，相当于只需要对A^1/2数值级别的整数继续进行因数分解，因而计算量被大大降低了。从计算复杂度的角度上看，相当于以O(n)或者是O(n²)的计算量（这是一种极好的多项式时间等级），完成了对于两个整数之间差值初步的因数分解。这种效率的提升，要归功于在减法计算时，首先引进了可以详细描述整数特征的“DNA技术”——整除关系数，再与乘积差公式完美地结合。

无论C的数值是否等于零，只要两个整除关系数属于同一个类型，当它们相减时，这种神奇的因数分解效率始终存在。数值越大时，这种效果会越加明显。

在计算两个不同类型的整除关系数之差时，即使利用乘积差公式，也不一定能够得到因数分解式；此时计算最大公约数，需要一数一议。

五、结束语

说句题外的话，整数转化成为整除关系数的好处远非仅此而已，另有甚多。例如，同一类的整除关系数，它们因数的数值结构，都有某种共同的规律可循。这样一来，仅需很少的计算量，凭借着几个很小合数的因数分解式，就可以揣摩、总结出属于同一个类型，但却任意大的合数都可以适用的因数数值分布规律，从而减少筛选因数时的计算量。

研究告一段落，心有感慨：一分忐忑，二分狐疑，三分寂寞。乘积差公式既简单又实用，况且只是属于数学中最基础的初等代数内容，怎么会历经了千百年，那么多的前辈大师都没有发现呢？一般来说，越是在最基础的科学领域里，就越没有创新的可能性；那么在现有的数字分类体系、四则运算等最基础的领域里，还有创新的可能性吗？吾本“下里巴人”，奈何和者盖寡？

每个人都希望能够在历史的长河中，留下一抹色彩。如有可能，希望朋友们把这篇文章传播出去，尽可能地让更多的人获知，使得科学收益。我在书写历史的同时，卿等也在加彩，这要比在历史古迹上，刻下“张三李四到此一游”，有意义得多。

“我是01” 二0一八年六月二十八日写于北京