精华内容
下载资源
问答
  • 威尔逊定理

    2019-11-04 22:24:18
    威尔逊定理:当p为质数时,(p−1)!≡−1 mod p 或 (p-1)!≡p-1 mod p; 当p为合数时,(p-1)!≡0 mod n 。 例题 #include <bits/stdc++.h> using namespace std; const int maxn = 3e6 +10; const int ...

    威尔逊定理:当p为质数时,(p−1)!≡−1 mod p 或 (p-1)!≡p-1 mod p;
    当p为合数时,(p-1)!≡0 mod n 。

    例题

    
    #include <bits/stdc++.h>
    using namespace std;
    const int maxn = 3e6 +10;
    const int maxm = 1e6 + 10;
    int v[maxn];
    vector <int> pri;
    int cnt, n;
    int ans[maxn];
    void prime(){
        for (int i =2 ; i < maxn; i++){
            if (!v[i]) pri.push_back(i);
            for (int j = 0; j < pri.size() && pri[j] * i < maxn; j++){
                v[i * pri[j]] = 1;
                if (i % pri[j] == 0) break;
            }
        }
    }
    int main()
    {
        prime();
        cnt = pri.size();
        int T;cin >> T;
        for (int i = 1; i < maxm; i++){
            int k = 3 * i + 7;
            if (!v[k]) ans[i] = ans[i - 1] + 1;
            else ans[i] = ans[i -1];
        }
        while (T--){
            scanf("%d", &n);
            cout << ans[n] << endl;
        }
        return 0;
    }

     

     

    展开全文
  • 威尔逊定理 数论

    千次阅读 2020-07-12 15:15:04
    最近在整理原来的一些资料,偶然想起原来搞OI时讲过一次威尔逊定理的内容,这里分享给大家 目录 一个实验 证明 剩余类与剩余系 缩系 证明 题目推荐 数论四大定理之一 ※是以英格兰数学家爱德华·华林的...

    最近在整理原来的一些资料,偶然想起原来搞OI时讲过一次威尔逊定理的内容,这里分享给大家

     

    目录

    一个实验

    证明

    剩余类与剩余系

    缩系

    证明

    题目推荐


     

    数论四大定理之一

    ※是以英格兰数学家爱德华·华林的学生约翰·威尔逊命名的,尽管这对师生都未能给出证明。华林于1770年提出该定理,1773年由拉格朗日首次证明

    ※威尔逊定理是判定一个自然数是否为素数的充分必要条件

     

     

    一个实验

    十八世纪中叶,一位英国法官约翰·威尔逊爵士,发现了数论中一种极为罕见的关系:取从1到某个质数所有连续正整数的乘积,例如从1乘到11,即11的阶乘11!。显然,11!能被从111的所有整数整除,除去11这个数,得10!。无疑10!不能被11整除。

    然而,如果给10!加上1的话,1×2×3×4×5×6×7×8×9×1013628801,怎么也不会想到,3628801却能被11整除(3628801÷11329891)。类似地,从1到质数7的阶乘7!中略去7,再加上1,得1×2×3×4×5×61721721也能被7整除(721÷7103

     
    117都是质数,研究发现,此种整除性对一切质数都成立,但对合数却不成立。下面的表格展示了这一规律:

    n

    (n-1)!

    (n-1)!+1

    [(n-1)!+1] mod n

    数性

    2

    1

    2

    0

    质数

    3

    2

    3

    0

    质数

    4

    6

    7

    3

    合数

    5

    24

    25

    0

    质数

    6

    120

    121

    1

    合数

    7

    720

    721

    0

    质数

    8

    5040

    5041

    1

    合数

    9

    40320

    40321

    1

    合数

    10

    362880

    362881

    1

    合数

    11

    3628800

    3628801

    0

    质数

    12

    39916800

    39916801

    1

    合数

    13

    479001600

    479001601

    0

    质数

    14

    6227020800

    6227020801

    1

    合数

    15

    87178291200

    87178291201

    1

    合数

     

    把上面所说的加以推广,就得到威尔逊定理:

    p为质数时,(p-1)!+1能被p整除。

    威尔逊定理逆定理:
    若一个数(p-1)!+1能被p整除,那么p为质数

     

    证明

    剩余类与剩余系

    我们考虑对一类数的分类规则

         ①.以除以2的余数为标准,整数可以分为两类:余数为0和余数为1

         ②.以除以3的余数为标准,整数可以分为三类:余数为0、余数为1、余数为2

     

    依此推理,以除以m的余数为标准,整数可以分为m类:余数为0、余数为1、余数为2...余数为m-1

    性质:每类中的数模m同余,即任取同类中数a,b,均有ab(mod m)

     

     

    定义:记[i]={j | ji(mod m)},[i]Z,通俗来讲,就是所有mod m 等于i的数

    [i]=[i+m]=[i-m]=[i+km],[i]称为模m的一个剩余类

     

    性质:模m的剩余类恰好有m个: [0],[1],[2]...[m-1]

     

    定义:

    从模m的剩余类[0]中取一个元素a0[1]中取一个元素a1 . . . [m-1]中取一个元素am-1 ,得到m个数

                                a0 a1 . . . am-1

    这样的m个数称为模m的一个完全剩余系

     

    性质:

    m个数对m作带余除法得到的余数恰好是0,1...m-1

    m个数两两对m取模不同余

     

    给出模5的一个完全剩余系

    5的剩余类是[0],[1],[2],[3],[4],我们从每个集合中选取一个元素,可以是:

                                             0,1,2,3,4

    上面那个完全剩余系称为模5的最小非负剩余系

     

    当然也可以是:

                                             5,1,2,3,4

    这个被称为模5的最小正剩余系

     

    缩系

    通过大量的实践发现:

    在模m的一个剩余类中,若有一个数与m互素,则该剩余类中每个数都与m互素,称此剩余系与m互素。φ(m)m的欧拉函数,函数的值为对于正整数m,小于或等于m的数中与m互质的数的数目。

    在模m的完全剩余系中,有φ(m)个数是与m互素的,称这φ(m)个数构成模m的一个缩系

    模7的缩系为:{1,2,3,4,5,6} φ(7)=6

    8的缩系为:{1,3,5,7} φ(8)=4

     

    性质:若

    是模m的缩系,则

    也为模m的缩系(gcd(a,m)=1

     

    证明

    回顾威尔逊定理:当p为质数时,(p-1)!+1能被p整除

    p=2时,威尔逊定理显然成立

    p>=3时,若p为素数,取集合A={2,3,...,p-2},由定义得知,则该集合Ap的一个缩系,在此时有性质:对于任意iA,存在jA,使得i*j1(mod p)

    这里搬运一个当时找到的该性质证明供参考:

    http://imgsrc.baidu.com/forum/w%3D580/sign=2d183b94afc379317d688621dbc6b784/fec56959252dd42a7ddcf839033b5bb5cbeab8be.jpg

    补充说明一下:上述不定方程:ij+pk=1中的j不可能为p的整数倍mp。简证之:假设j=mp,则有i(mp)+pk=1,即(im+k)p=1,而素数p>=2,im+k为整数,所以方程不成立。所以,ij+pk=1中的j不可能为p的整数倍mp

     

    将元素1p-1单独考虑,发现1×(p-1)(p-1) mod p

    而p为素数,除了2为偶素数外,其余均为奇素数,那么p-3p>=3意义下一定为偶数,则集合A能满足两两配对使得

     i*j1(mod p)

    即:

    故定理得证

     

    题目推荐

    HDU 2973 YAPTCHA

    题解:

    https://blog.csdn.net/csyzcyj/article/details/107299894

     

    转载注明出处:https://blog.csdn.net/csyzcyj/

    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,203
精华内容 481
关键字:

威尔逊定理