《数论概论》读书笔记（第二章）勾股数组

￡神魔★判官ぃ 2022-06-16 00:42 368阅读 0赞

本章主要讨论的是本原勾股数组，也就是关于满足a2\+b2=c2的三元组(a,b,c)，且(a,b,c)互质的问题。  
这章中提到一个概念：本原勾股数组（PPT）是一个三元组(a,b,c),其中a,b,c没有公因子，且满足a2\+b2=c2，就是gcd(a,b,c)=1。  
对于本原勾股数组，显然a 和 b 奇偶性不同只需要将a=2x\+1,b=2y\+1,c=2z，代入a2\+b2=c2，即可推出有公约数2。**由于a和b奇偶性不同，即a或b是偶数**，**那么显然c为奇数。**（书中有证明的）。

那么我们最关心的是如何求出所有的本原勾股数组。

如果将公式转化一下，得到a2=c2−b2=(c\+b)∗(c−b)，那么显然有，c\+b和c−b没有公因子。

（反证法）证明：  
如果d|(c\+b)且d|(c−b)，那么显然有d|((c\+b)\+(c−b))和d|((c\+b)−(c−b))即d|2b且d|2c，因为在定义本原勾股数组的时候已经有了b和c的最大公约数是1的约定(虽然定义是a，b，c最大公约数是1，但是如果gcd(b,c)=d>1，显然有d|c不满足定义)。所以d要么为1，要么为2。但是如果d=2时，那么显然a，b，c均为偶数，不满足定义，那么d只能为1，证明了c\+b和c−b都没有公因子。（书中都有）。  
因此，如果将a2进行质因数分解，那么会有a=pa11∗pa22∗pa33...pann，其中指数a1,a2,a3...an为偶数（因为这样才能保证a2开根号后为整数），又因为c\+b和c−b没有公因数，c\+b和c−b各用a分解后的必然是pakk这些东西，因此，c\+b 和 c−b均为平方数。那么假设c\+b=s2,c−b=t2，则有c=(s2\+t2)2,b=(s2−t2)2，a=st，**因此形如(st,(s2−t2)2(s2\+t2)2)的三元组为本原勾股数组**。(其中s和t都是奇数，因为如果s和t中有且只有一个为奇数，那么显然(s2\+t2)2不会是整数，而如果两个数都是偶数，那么显然该三元组有公因子2，与本原勾股数组定义矛盾。)

#### **本原勾股数公式：**a=m²−n²，b=2mn，c=m²\+n² ####

#### **一些构造题和数论题会涉及：本原勾股数组。** ####

#### 例题： ####

#### [http://codeforces.com/contest/707/problem/C][http_codeforces.com_contest_707_problem_C] ####

#### [http://acm.hdu.edu.cn/showproblem.php?pid=3422][http_acm.hdu.edu.cn_showproblem.php_pid_3422] ####

#### [http://poj.org/problem?id=1305][http_poj.org_problem_id_1305] ####

--------------------

#### 习题解析： ####

1.  （a） 反证法。假设a和b都不是3的倍数，那么由于a和b的奇偶性不同，因此我想的方法是分成4种情况讨论:  
    由于a和b具有互换性，因此假定a为奇数，b为偶数。
    
     *  amod3=1,bmod3=1  
        那么a=6x\+1,b=6y\+4,那么根据勾股定理，可以得到c=6z\+5的形式，再代入a2\+b2=c2后可得：  
        36x2\+12x\+1\+36y2\+48y\+16=36z2\+60z\+25  
        整理后可得3∗(12x2\+4x\+12y2\+16y−12z2−20z)=8。  
        3不是8的因子，所以显然不存在整数x，y使得该式成立。
     *  amod3=1,bmod3=2  
        那么有a=6x\+1,b=6y\+2,那么可以得到c=6y\+5的形式，代入a2\+b2=c2后可得  
        36x2\+12x\+1\+26y2\+24y\+4=26y2\+60z\+25  
        整理后常数项20也不是3的因子，所以不存在整数x，y
     *  同理，可证明当amod3=2,bmod3=1和amod3=2,bmod3=2中同样找不到x，y成立，因此假设不成立，所以证明了a或者b必定是3的倍数。  
        （b）根据上面的反证法也可以证明a或b或c是5的倍数。
2.  证明：如果d|m和d|n，则d|(m−n)且d|(m\+n)的证明。  
    很显然有m=ad,n=bd，则m−n=d(a−b)，m\+n=d(a\+b)，显然能够被d整除。
3.  证明略。**奇数和4的倍数**可以出现在本原勾股数组中，而形如**4n+2的偶数**不可能出现在本原勾股数组中。  
    定理：如果x和y没有公约数，那么x2\+y2的**任何奇素因子** 都必定形如4n\+1.
4.  显然是存在相同c值的2个本原勾股数组的。自己打个表就知道了。也可以找到相同c值的4个本原勾股数组。但找不到3个(10,000,000内)，可以找到4个的，找不到5个的，也找不到6个的。。。  
    测试代码：

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    ll n;
    ll vis[10000000+7];
    ll gcd(ll a,ll b){
        return b==0?a:gcd(b,a%b);
    }
    ll cot[100000000+7];
    int main()
    {
        while(~scanf("%lld",&n))// <= 1,000,0000
        {
            memset(vis,0,sizeof(vis));
            int m=sqrt((double)n);
    
            ll ans=0; 
            ll x,y,z;
            ll a,b,d;
            for(ll i=1;i<=m;i+=2)
            {
                for(ll j=2;j<=m;j+=2)
                {
    
                    a=max(i,j);
                    b=min(i,j);
                    d=gcd(a,b);
    
                    if(d==1)
                    {
                        x=a*a-b*b;
                        y=2*a*b;
                        z=a*a+b*b;
                        cot[z]++;
                        for(int k=1;k*z<=n;k++)
                        {
                            vis[x*k]=1;
                            vis[y*k]=1;
                            vis[z*k]=1;
                        }
                        if(z<=n)
                            ans++;  
                    }
                }
            }
            printf("有%lld个本原勾股数组\n",ans);
            ans = 0;
            for(int i=1;i<=n;i++){
                 ans=max(ans,cot[i]);
                 if(ans==2)cout<<"存在2个."<<endl;
                // if(ans==4)cout<<"存在4个"<<endl;
                // if(ans==5)cout<<"存在5个"<<endl;
                 //if(ans==6)cout<<"存在6个"<<endl;
            }
            cout<<"(最大值)相同的有"<<ans<<"个."<<endl;
        }
        return 0;
    }

(5)  
对于问题（a）:  
首先，  
b=4T1:(3,4,5)  
b=4T2:(5,12,13)  
b=4T3:(7,24,25)  
b=4T4:(9,40,41)  
观察可以找到规律：一个数是奇数，第二个数是Tn，第三个数是(Tn)\+1。即：a=2k\+1,b=2k(k\+1),c=2k(k\+1)\+1，即a=2k\+1，b=2k2\+2k，c=2k2\+2k\+1.

对于问题（b）,由（a）可以得到，b显然是是三角数的4倍。所以，每个三角数Tn都存在b=Tn的本原勾股数组（a，b，c）。

(6)对于（a）（b）（c），由上面的题目我们可以得到：a=4k，b=4k2−1,c=4k2\+1，即：c=a\+2。那么：a=4k，b=4k2−1,c=4k2\+1就是通用公式。

(7)你打个表或者套上面的公式，可以发现，打表发现2c−2a为完全平方数。特殊形式：2c−2a=2∗((s2\+t2)2−st)=(s−t)2。

(8)自行阅读与了解。

[http_codeforces.com_contest_707_problem_C]: http://codeforces.com/contest/707/problem/C
[http_acm.hdu.edu.cn_showproblem.php_pid_3422]: http://acm.hdu.edu.cn/showproblem.php?pid=3422
[http_poj.org_problem_id_1305]: http://poj.org/problem?id=1305