精华内容
下载资源
问答
  • 欧拉定理

    2020-09-15 21:30:20
    欧拉定理的证明

    什么是欧拉定理

    数论上的欧拉定理,指的是

    ax1(mod n)a^x \equiv 1 (mod\ n)

    这个式子实在a和n互质的前提下成立的。

    欧拉定理的证明

    首先,我们知道在1到n的数中,与n互质的一共有φ(n)φ(n)个,所以我们把这φ(n)φ(n)个数拿出来,放到设出的集合X中,即为x1,x2xφ(n)x_1,x_2……x_{φ(n)}

    那么接下来,我们可以再设出一个集合为MM,设MM中的数为:

    m1=ax1m2=ax2mφ(n)=axφ(n)m1=a*x1 \\m2=a*x2 \\…… \\mφ(n)=a*xφ(n)

    下面我们证明两个推理:

    一、M中任意两个数都不模n同余。

    反证法。

    证明:假设MM中存在两个数设为ma,mbm_a,m_bnn同余。

    ​ 即mambm_a \equiv m_b

    ​ 移项得到:mamb=nkm_a-m_b=n*k
    ​ 再将mmxx来表示得到:axaaxb=nka∗x_a−a∗x_b=n∗k

    ​ 提取公因式得到a(xaxb)=nka∗(x_a−x_b)=n∗k

    ​ 我们现在已知a与n互质,那么式子就可以转化为:xaxbmod n)x_a−x_b\equiv(mod\ n)

    ,因为aa中没有与nn的公因子(11除外)所以aa对模nn同余00并没有什么贡献。

    ​ 又因为xa,xbx_a,x_b都是小于nn的并且不会相同,所以xaxbx_a−x_b一定是小于nn的,那么上述的式子自然全都不成立。

    ​ 假设不成立。

    证得:M中任意两个数都不模n同余。

    二、M中的数除以n的余数全部与n互质。

    证明:我们已知mi=axim_i=a∗x_i.

    ​ 又因为aann互质,xix_inn互质,所以可得mim_inn互质。

    ​ 带入到欧几里得算法中推一步就好了。

    ​ 即:

    gcd(axi,n)=gcd(mi,n)=gcd(n,mimod n)=1gcd(a∗x_i,n)=gcd(m_i,n)=gcd(n,m_imod\ n)=1

    证毕。

    推式子

    根据我们证得的两个性质,就可以开始推式子了。

    首先,根据第二个性质可以知道,M中的数分别对应X中的每个数模n同余。

    所以可以得到:

    m1m2mφ(n)x1x2xφ(n)(mod n)m_1*m_2*……*m_{φ(n)}\equiv x_1*x_2*……*x_{φ(n)}(mod\ n)

    现在我们把mim_i替换成xx的形式,就可以得到:

    ax1ax2axφ(n)x1x2xφ(n)(mod n)a*x_1*a*x_2*……*a*x_{φ(n)}\equiv x_1*x_2*……*x_{φ(n)}(mod\ n)

    很显然,我们应该移项了,但是在移项之前,我们认为这么多的aa很烦,那么就先乘起来:

    aφ(n)(x1x2xφ(n))x1x2xφ(n)(modn)a^{φ(n)}*(x_1*x_2……*x_{φ(n)})\equiv x_1*x_2……*x_{φ(n)}(mod n)

    我们凑出了aφ(n)a^{φ(n)},那么就开始移项:
    (aφ(n)1)(x1x2xφ(n))0(modn)(a^{φ(n)}-1)*(x_1*x_2……*x_{φ(n)})\equiv 0(mod n)

    然后,就可证明:

    aφ(n)1(modn)a^{φ(n)}\equiv 1(mod n)

    展开全文
  • 欧拉定理:若gcd(a,p)=1,则a^φ§≡1(mod p) 欧拉定理特例:费马小定理:若p是质数,则对于任意整数a,有a^p≡a(mod p)。 扩展欧拉定理: 欧拉函数: 对于一个正整数n,小于等于n且和n互质的正整数(包括1)的个数...

    欧拉定理:若gcd(a,p)=1,则a^φ( p )≡1(mod p)
    欧拉定理特例费马小定理:若p是质数,则对于任意整数a,有a^p≡a(mod p)。
    扩展欧拉定理(欧拉降幂)
    扩展欧拉定理
    欧拉函数
    对于一个正整数n,小于等于n且和n互质的正整数(包括1)的个数,记作φ(n) 。
    通式:φ(n)=n*(1-1/p1) * (1-1/p2) * (1-1/p3) * (1-1/p4) * …… * (1-1/pn), 其中p1, p2……pn为n的所有质因数,n是不为0的整数。记 φ(1)=1(唯一和1互质的数就是1本身)。

    欧拉函数性质

    1. 当m,n互质时,有phi(m*n)= phi(m)*phi(n);(积性函数通有性质)

    2. 若i%p==0,有phi(i*p) = phi(i)*p;

    3. 当n为奇数时,phi(2n)=phi(n) (奇数与2互质,且phi(2) = 1);

    4. n>1,不大于n且和n互质的所有正整数的和是 phi(n)*n/2。

    5. 若x与p互质且x<p,则p-x也与p互质;

    6. 若(n%a == 0 && (n/a)%a == 0) 则有:phi(n) = phi(n/a) * a;

    7. 若(n%a == 0 && (n/a)%a != 0) 则有:phi(n) = phi(n/a) * (a-1);

    8. 若i%p != 0,有phi(i*p) = phi(i) * (p-1);

    展开全文
  • 欧拉定理、拓展欧拉定理及其应用(欧拉降幂法) 摘要  本文主要介绍了数论中的欧拉定理,进而介绍欧拉定理的拓展及应用,结合例题展示如何使用拓展欧拉定理实现降幂取模。  在数论中,欧拉定理,(也称费马-...

    欧拉定理、拓展欧拉定理及其应用(欧拉降幂法)

    摘要

      本文主要介绍了数论中的欧拉定理,进而介绍欧拉定理的拓展及应用,结合例题展示如何使用拓展欧拉定理实现降幂取模。


      在数论中,欧拉定理,(也称费马-欧拉定理)是一个关于同余的性质定理。了解欧拉定理之前先来看一下费马小定理:

        a是不能被质数p整除的正整数,则有a^(p-1) ≡ 1 (mod p)

      欧拉给出了推广形式

        若n,a为正整数且互质,则,其中φ(n)表示小于等于m的数中与n互质的数的数目。可以看出费马小定理是欧拉定理的一种特殊情况。

      首先看一个基本的例子。令a = 3,n = 5,这两个数是互素的。比5小的正整数中与5互素的数有1、2、3和4,所以φ(5)=4。计算:a^{φ(n)} = 3^4 =81,而81= 80 + 1 Ξ 1 (mod 5)。与定理结果相符。

      然后使用欧拉定理实现简化幂的模运算。比如计算7^{222}的个位数,实际是求7^{222}被10除的余数。7和10[互素],且φ(10)=4。由欧拉定理知7^4Ξ1(mod 10)。所以7^{222}=(7^4)^55*(7^2)Ξ1^{55}*7^2Ξ49Ξ9 (mod 10)。于是该7^{222}的个位数就是9。

      最后将欧拉定理拓展到a和m不互质的情况

      下面给出求解一个φ(n)值的求法:

    ll euler_phi( ll n )
    {
        ll i,ans = n;
        for ( i=2; i*i<=n; i++ ) {
            if ( n%i==0 ) {
                ans = ans - ans/i;
                while ( n%i==0 ) n/=i;
            }
        }
        if ( n>1 ) {
            ans = ans - ans/n;
        }
        return ans;
    }

    使用类似筛法的方法计算phi(1),phi(2),phi(3),...phi(n)

    const int maxn = 100001;
    ll phi[maxn];
    void phi_table(ll n) {//计算1到n的欧拉函数值
        for(ll i = 2; i <= n; i++)
            phi[i] = 0;
        phi[1] = 1;
        for(ll i = 2; i <= n; i++) {
                if(!phi[i]) {
                    for(ll j = i; j <= n; j+=i) {
                        if(!phi[j]) phi[j] = j;
                        phi[j] = phi[j] / i * (i - 1);
                }
            }
        }
    }

    看一道例题:FZU 1759 Super A^B mod C

    题意

    计算A^B mod C,其中1<=A,C<=1000000000,1<=B<=10^1000000。

    解题思路

    使用数组读入,循环取余。

    #include <iostream>
    #include <cmath>
    #include <cstring>
    
    using namespace std;
    
    typedef long long ll;
    char b[1000005];
    
    ll qpow( ll a, ll n, ll mod )
    {
        ll re = 1;
        while ( n ) {
            if ( n&1 ) {
                re = (re*a)%mod;
            }
            n >>= 1;
            a = (a*a)%mod;
        }
        return re;
    }
    
    ll euler_phi( ll n )
    {
        ll i,ans = n;
        for ( i=2; i*i<=n; i++ ) {
            if ( n%i==0 ) {
                ans = ans - ans/i;
                while ( n%i==0 ) n/=i;
            }
        }
        if ( n>1 ) {
            ans = ans - ans/n;
        }
        return ans;
    }
    
    ll solve(ll a, ll b, ll c)
    {
        ll t = euler_phi(c);
        if ( b<t ) {
            return qpow(a,b%t,c)%c ;
        }
        else {
            return qpow(a,b%t+t,c)%c ;
        }
    }
    
    int main()
    {
        ll a,c;
        while ( cin>>a>>b>>c ) {
            ll len = strlen(b);
            ll n = euler_phi(c);
            ll ans = 0;
            for ( ll i=0; i<len; i++ ) {
                ans = (ans*10 + b[i]-'0')%n;
            }
            cout << solve(a,ans,c) << endl;
    
        }
    
        return 0;
    }
    

     

    展开全文
  • 数论专题-学习笔记:欧拉定理与扩展欧拉定理1. 前言2. 前置知识3. 欧拉定理3.1 描述3.2 证明4. 扩展欧拉定理4.1 描述4.2 证明4.3 例题5. 总结 1. 前言 欧拉定理与扩展欧拉定理,是数论中的一个很重要的定理。 该定理...

    1. 前言

    欧拉定理与扩展欧拉定理,是数论中的一个很重要的定理。

    该定理可以将形如 aba^b 的式子的指数降得很低,通常可以降到 logb\log b 可接受范围内,这样就可以用快速幂计算了。

    若无特殊说明,本文所有数都是正整数。

    一些符号说明:

    • φ(n)\varphi(n)欧拉函数
    • abmodca \equiv b \bmod c 表示 a,ba,bcc 的值相等,这个式子叫做同余式

    2. 前置知识

    费马小定理:若 mm 为质数并且 mam \nmid a,则 am11modma^{m-1} \equiv 1 \bmod m

    3. 欧拉定理

    3.1 描述

    欧拉定理描述如下:

    gcd(a,m)=1\gcd(a,m)=1,则 aφ(m)1modma^{\varphi(m)} \equiv 1 \bmod m

    结合上面的费马小定理可以发现,费马小定理实际上就是欧拉定理的一种特殊情况。

    3.2 证明

    x1,x2,...,xφ(m)x_1,x_2,...,x_{\varphi(m)}φ(m)\varphi(m) 个与 mm 互质的数。

    pi=axip_i=ax_i

    下面若无特殊说明,同余式均对 mm 取模。


    引理 1:i,j[1,φ(m)],pi≢pj,xi≢xj\forall i,j \in[1,\varphi(m)],p_i \not \equiv p_j,x_i \not \equiv x_j

    证明如下:首先因为所有 xi<mx_i<m,那么必然有 xi≢xjx_i \not \equiv x_j

    接下来反证法,假设 pipjp_i \equiv p_j

    那么有 pipj0p_i - p_j \equiv 0

    a(xixj)0a(x_i-x_j) \equiv 0

    但是 gcd(a,m)=1\gcd(a,m)=1,因此 mxixjm \mid x_i-x_j。但是 xixj0x_i-x_j \not = 0 且小于 mm,矛盾。

    综上引理 1 成立。


    引理 2:所有 ppmm 的结果都与 mm 互质。

    证明如下:

    还是反证法。

    pi=axi=km+rp_i=ax_i=km+r,即除以 mm,那么有 gcd(r,m)>1\gcd(r,m)>1

    整理得 xi=km+rax_i=\dfrac{km+r}{a}

    因为 xix_i 是个正整数,所以 gcd(a,km,r)=a\gcd(a,km,r)=a

    所以 gcd(a,r)=a\gcd(a,r)=a

    然而 gcd(a,m)=1\gcd(a,m)=1,因此只有 gcd(a,km)=a\gcd(a,km)=a 才能够做到 gcd(a,km,r)=a\gcd(a,km,r)=a

    所以 k=ak=a

    但是因为 pi=axip_i=ax_i,因此就要有 xi=mx_i=mr=0r=0,显然与假设矛盾,因此原假设错误。

    综上,引理 2 成立。


    有了这两个引理之后,我们就可以证明欧拉定理了。

    由引理 2,所有 ppmm 的结果都与 mm 互质。

    由引理 1,任意两个 pp 之间模 mm 不同余,任意两个 xx 之间模 mm 不同余。

    因此我们可以得到所有 ppmm 的结果组成的集合与 xxmm 的结果组成的集合是相同的。

    因此我们就有 i=1φ(m)pii=1φ(m)xi\prod\limits_{i=1}^{\varphi(m)}p_i \equiv \prod\limits_{i=1}^{\varphi(m)}x_i

    同余式的基本性质,约去 xi\prod x_i,我们可以得到 aφ(m)1a^{\varphi(m)}\equiv 1

    综上,欧拉定理成立。

    4. 扩展欧拉定理

    4.1 描述

    扩展欧拉定理是欧拉定理的扩展,该定理将欧拉定理扩展到了 gcd(a,m)\gcd(a,m) 为任意数的情况。

    其描述如下(均对 mm 取模):

    ab{abmodφ(m)gcd(a,m)=1abgcd(a,m)1,bφ(m)a(bmodφ(m))+φ(m)gcd(a,m)1,b>φ(m)a^b \equiv \begin{cases}a^{b \bmod \varphi(m)}&\gcd(a,m)=1\\a^b&\gcd(a,m)\ne1,b \leq\varphi(m)\\a^{(b \bmod \varphi(m))+\varphi(m)}&\gcd(a,m)\ne1,b>\varphi(m)\end{cases}

    4.2 证明

    下面同余式无说明均对 mm 取模。


    ababmodφ(m),gcd(a,m)=1a^b \equiv a^{b \bmod \varphi(m)},\gcd(a,m)=1

    这个还是比较简单的。

    由欧拉定理,aφ(m)1a^{\varphi(m)} \equiv 1,因此实际上我们两遍同时除以 aφ(m)a^{\varphi(m)} 是可行的。

    因此原式得证。


    abab,gcd(a,m)1,bφ(m)a^b \equiv a^b,\gcd(a,m) \ne1,b \leq \varphi(m)

    啊不是这还需要证明吗qwq


    aba(bmodφ(m))+φ(m),gcd(a,m)1,b>φ(m)a^b \equiv a^{(b \bmod \varphi(m)) + \varphi(m)},\gcd(a,m) \ne 1,b > \varphi(m)

    首先对 aa 做一个质因数分解 a=i=1kpiria=\prod_{i=1}^{k}p_i^{r_i}

    因此根据同余式可以同乘的性质,我们的目标变成了证明 a=piria=p_i^{r_i} 时上式成立。

    显然 pirip_i^{r_i} 也是可以由 rir_ipip_i 同乘的,因此我们的最终目的变成了证明当 aa 是个质数的时候上式成立。

    接下来的证明都只考虑 aa 为质数。

    考虑引入一个数 ssaa 互质,令 m=s×ac,cφ(m)m=s \times a^c,c \leq \varphi(m)

    • 实际上 cφ(m)c \leq \varphi(m) 是必定成立的,因为总共与 mm 互质的数有 φ(m)\varphi(m) 个,而且φ(m)=φ(s)×φ(ac)=φ(s)×c,φ(s)1\varphi(m)=\varphi(s) \times \varphi(a^c)=\varphi(s) \times c,\varphi(s) \geq 1,因此有 cφ(m)c \leq \varphi(m)

    根据欧拉定理,有 aφ(s)1modsa^{\varphi(s)} \equiv 1 \bmod s

    因为 gcd(s,a)=1\gcd(s,a)=1,根据欧拉函数的下面这条性质:

    • nN+,pn \in N_+,p 为质数,那么:φ(n×p)={φ(n)×φ(p)pnφ(n)×ppn\varphi(n \times p)=\begin{cases}\varphi(n) \times \varphi(p)&p \nmid n\\\varphi(n) \times p&p \mid n\end{cases}

    我们可以得到 φ(s)φ(m)\varphi(s) \mid \varphi(m)

    因此有 aφ(m)=aφ(s)×φ(m)φ(s)1modsa^{\varphi(m)} =a^{\varphi(s) \times \frac{\varphi(m)}{\varphi(s)}}\equiv 1 \bmod s

    两遍同乘以 aca^c(注意模数变成了 mm),有 aφ(m)+caca^{\varphi(m)+c} \equiv a^{c}

    于是 ab=abc+c=ac×abcaφ(m)+b,bca^b=a^{b-c+c} =a^c \times a^{b-c}\equiv a^{\varphi(m)+b},b \geq c

    因为任意 cφ(m)c \leq \varphi(m) 上式都成立,因此有 abaφ(m)+ba^b \equiv a^{\varphi(m)+b}

    上式等价于 aba(bmodφ(m))+φ(m)a^b \equiv a^{(b \bmod \varphi(m))+\varphi(m)}

    因此我们成功的证明了 aa 是个质数的时候原式成立。

    那么根据我们一开始的理论,可以证出原式对于任意 aa 都成立。


    综上,扩展欧拉定理成立。

    4.3 辅助说明

    扩展欧拉定理:

    ab{abmodφ(m)gcd(a,m)=1abgcd(a,m)1,bφ(m)a(bmodφ(m))+φ(m)gcd(a,m)1,b>φ(m)a^b \equiv \begin{cases}a^{b \bmod \varphi(m)}&\gcd(a,m)=1\\a^b&\gcd(a,m)\ne1,b \leq\varphi(m)\\a^{(b \bmod \varphi(m))+\varphi(m)}&\gcd(a,m)\ne1,b>\varphi(m)\end{cases}


    首先观察一下第一个式子和第三个式子。

    我们发现实际上这两个式子对于 b>φ(m)b>\varphi(m) 的时候是等价的。

    因此一般做题的时候我们不需要记第一个式子,只记第二个和第三个式子就好。

    对于 b>φ(m)b>\varphi(m) 的情况刚刚已经说过第一个式子与第二个式子等价。

    对于 bφ(m)b \leq \varphi(m) 的情况因为 ab=aba^b=a^b 恒成立(难道不是吗),所以第一个式子和第二个式子等价。

    当然如果出现了 gcd(a,m)=1\gcd(a,m)=1 的情况实际上我们可以直接用欧拉定理即可。


    或许有的人问了:对于第二个式子 abab,gcd(a,m)1,bφ(m)a^b \equiv a^b,\gcd(a,m) \ne 1,b \leq \varphi(m),为什么其不等价于第三个式子?

    解释如下:

    首先因为 gcd(a,m)1\gcd(a,m) \ne 1,我们知道欧拉定理不成立,也就是 aφ(m)≢1a^{\varphi(m)} \not \equiv 1

    因此对第三个式子做一个拆分:ababmodφ(m)×aφ(m)a^b \equiv a^{b \bmod \varphi(m)} \times a^{\varphi(m)}

    我们发现因为 bφ(m)b \leq \varphi(m) 的时候 aφ(m)≢1a^{\varphi(m)} \not \equiv 1,因此我们不能在第二个式子两边同时乘以 aφ(m)a^{\varphi(m)}

    4.4 例题

    例题:P5091 【模板】扩展欧拉定理

    扩展欧拉定理板子题。

    特别需要注意 bφ(m)b \leq \varphi(m) 的情况,此种情况 bb 不能加上 φ(m)\varphi(m)

    代码:

    /*
    ========= Plozia =========
        Author:Plozia
        Problem:P5091 【模板】扩展欧拉定理
        Date:2021/5/19
    ========= Plozia =========
    */
    
    #include <bits/stdc++.h>
    
    typedef long long LL;
    // const int MAXN = ;
    LL a, b, m, phi = 1;
    bool flag = 0;
    
    LL read()
    {
        LL sum = 0, fh = 1; char ch = getchar();
        for (; ch < '0' || ch > '9'; ch = getchar()) fh -= (ch == '-') << 1;
        for (; ch >= '0' && ch <= '9'; ch = getchar()) sum = (sum << 3) + (sum << 1) + (ch ^ 48);
        return sum * fh;
    }
    
    LL Specail_read()
    {
        LL sum = 0, fh = 1; char ch = getchar();
        for (; ch < '0' || ch > '9'; ch = getchar()) fh -= (ch == '-') << 1;
        for (; ch >= '0' && ch <= '9'; ch = getchar())
        {
            sum = sum * 10ll + ch - '0';
            if (sum > phi) { sum %= phi; flag = 1; }
        }
        return sum * fh;
    }
    
    LL ksm(LL fir, LL sec, LL p)
    {
        LL ans = 1 % p;
        for (; sec; sec >>= 1, fir = fir * fir % p)
            if (sec & 1) ans = ans * fir % p;
        return ans;
    }
    
    void Get_phi()
    {
        int i, c = m;
        for (i = 2; i * i <= c; ++i)
        {
            int sum = 0;
            while (c % i == 0) { ++sum; c /= i; }
            if (sum != 0) phi *= (LL)(i - 1) * ksm(i, sum - 1, m);
        }
        if (c != 1) phi *= (c - 1);
    }
    
    int main()
    {
        a = read(), m = read(); Get_phi();
        b = Specail_read();
        if (flag) b += phi;
        printf("%lld\n", ksm(a, b, m));
        return 0;
    }
    

    5. 总结

    扩展欧拉定理:

    ab{abmodφ(m)gcd(a,m)=1abgcd(a,m)1,bφ(m)a(bmodφ(m))+φ(m)gcd(a,m)1,b>φ(m)a^b \equiv \begin{cases}a^{b \bmod \varphi(m)}&\gcd(a,m)=1\\a^b&\gcd(a,m)\ne1,b \leq\varphi(m)\\a^{(b \bmod \varphi(m))+\varphi(m)}&\gcd(a,m)\ne1,b>\varphi(m)\end{cases}

    展开全文
  • 欧拉定理 内容 欧拉定理:当gcd(a,m)=1gcd(a,m)=1gcd(a,m)=1时,有aϕ(m)≡1(modm)a^{\phi(m)}\equiv1{\pmod{m}}aϕ(m)≡1(modm) 费马小定理:当mmm为质数且aaa不为mmm的倍数时有am−1≡1(modm)a^{m-1}\equiv1\pmod{...

空空如也

空空如也

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

欧拉定理