《数论概论》读书笔记第5章整除性与最大公因子数

骑猪看日落 2022-06-13 22:36 270阅读 0赞

这章就是讲最大公因子的一些概念和求gcd的方法。  
高中必修三，就已经知道可以有“辗转相除法”和“更相减损术”等方法能够更快的求出两个数的最大公因数  
讲述一些概念。  
m整除n指n是m的倍数。  
如果m整除n，我们记为m|n。  
如果m不整除n，则记为m∤n。  
两个数a和b（不全为零）的最大公因数的最大公因数是整除它们两个的最大公因数，记为gcd(a,b)。如果gcd（a,b）=1，我们称a与b互素。

然后这章后面的就是怎么用“辗转相除法”求gcd了，并且给了“辗转相除法”的证明。

定理5.1. 欧几里得算法。（略）

题目解析：  
1. gcd(12345,67890)=15，gcd(54321,9876)=3.  
2.

#include <bits/stdc++.h>
    using namespace std;
    int gcd(int a,int b)
    {
        return b==0?a:gcd(b,a%b);
    }
    int main()
    {
        int a,b;
        while(cin>>a>>b)
        {
            cout<<gcd(a,b)<<endl;
        }
        return 0;
    }

3.  
推导：  
ri=qi\+2∗ri\+1\+ri\+2  
ri\+1=qi\+3∗ri\+2\+ri\+3  
代入得：  
ri=(qi\+2∗qi\+3\+1)∗ri\+2\+qi\+2∗ri\+3  
riri\+2=qi\+2∗qi\+3\+1\+qi\+2∗ri\+3ri\+2>qi\+2∗qi\+3\+1.  
因为，qi\+2∗qi\+3>=1  
所以，riri\+2>2  
即，ri\+2<12ri.  
因此，最坏情况为每两次计算缩小一半，也就是2p=t，其中t为max(x,y)，p为步数k2。所以有log2t=p，将p=k2代入，得步数k=2log2t。假设t有s位，也就是k<2log2(10s),得到k<2slog210<7s，因此可以认为最坏情况大约为位数的7倍。

4.  
代码：

#include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    ll gcd(ll a,ll b)
    {
        return b==0?a:gcd(b,a%b);
    }
    int main()
    {
        ll a,b;
        while(cin>>a>>b)
        {
            cout<<a/gcd(a,b)*b<<endl;
        }
        return 0;
    }

(1).  
证明：lcm(a,b)=abgcd(a,b).  
证明: d∣lcm(a,b)⟺d∣a,b⟺a,b∣ab/d⟺gcd(a,b)∣ab/d⟺d∣ab/gcd(a,b).  
所以，lcm(8,12)=24,lcm(20,30)=60,lcm(51,68)=204,lcm(23,18)=414.

(2).  
lcm(a,b)=abgcd(a,b).

(3).  
证明看(1).

(4).  
lcm(301337,307829)=171460753.

(5).  
肯定有多解啊。  
对于gcd(m,n)=18, 假设m<=n,那么有一下解：

18 36
    18 54
    18 72
    18 90
    18 108
    18 126
    18 144
    18 162
    18 180
    18 198
    18 216
    18 234
    18 252
    18 270
    18 288
    18 306
    18 324
    18 342
    18 360
    18 378
    18 396
    18 414
    18 432
    18 450
    18 468
    18 486
    18 504
    18 522
    18 540
    18 558
    18 576
    18 594
    18 612
    18 630
    18 648
    18 666
    18 684
    18 702
    18 720
    18 738
    18 756
    18 774
    18 792
    18 810
    18 828
    18 846
    18 864
    18 882
    18 900
    18 918
    18 936
    18 954
    18 972
    18 990
    18 1008
    18 1026
    18 1044
    18 1062
    18 1080
    18 1098
    18 1116
    18 1134
    18 1152
    18 1170
    18 1188
    18 1206
    18 1224
    18 1242
    18 1260
    18 1278
    18 1296
    18 1314
    18 1332
    18 1350
    18 1368
    18 1386
    18 1404
    .....
    .....
    .....

对于lcm(m,n)=720，假设m<=n,那么有一下解：

1 720
    2 720
    3 720
    4 720
    5 144
    5 720
    6 720
    8 720
    9 80
    9 240
    9 720
    10 144
    10 720
    12 720
    15 144
    15 720
    16 45
    16 90
    16 180
    16 360
    16 720
    18 80
    18 240
    18 720
    20 144
    20 720
    24 720
    30 144
    30 720
    36 80
    36 240
    36 720
    40 144
    40 720
    45 48
    45 80
    45 144
    45 240
    45 720
    48 90
    48 180
    48 360
    48 720
    60 144
    60 720
    72 80
    72 240
    72 720
    80 90
    80 144
    80 180
    80 360
    80 720
    90 144
    90 240
    90 720
    120 144
    120 720
    144 180
    144 240
    144 360
    144 720
    180 240
    180 720
    240 360
    240 720
    360 720
    720 720

(1).(2).跑一下代码就知道了。有关循环长度的问题，得到L(21)=8，L(13)=10,，L(31)=107。另外，我们可以发现，对于前100个数进行试验，最后都是在4,2,1上停下来。

(3).  
8k\+4⟺4k\+2⟺2k\+1⟺6k\+4  
8k\+5⟺24k\+16⟺12k\+8⟺6k\+4  
所以，当n=8k\+4时n和n\+1经过3步后会变成同一个数，所以，n=8k\+4时L(n)=L(n\+1).。

(4).  
同理，对n=128k\+28时，L(n)=L(n\+1)=L(n\+2)的证明也可以用(3)中方法。

6.  
自己写代码吧….3n\+1 问题（卡拉兹(Callatz)猜想）.

代码：

#include <bits/stdc++.h>
    using namespace std;
    int main()
    {
        int n = 0;  
        while(cin>>n)
        {
            int ans = n; 
            cout<<n<<" ";
            int len=1;  
            while (1)
            {
                if(n == 1)
                {
                    break;
                }
                else
                {
                    if (n & 1)
                    {
                        n = n* 3 + 1;
                        len++;
                        cout << n << " ";
                    }
                    else
                    {
                        n = n / 2;
                        len++;
                        cout << n << " ";
                    }
                }
            }
            printf("\nL(%d)=%d\n",ans,len);
        }
        return 0;
    }