使用c语言实现欧拉定理

欧拉定理是指若a和n是正整数且a与n互质，则a^φ(n) ≡ 1(mod n)，其中φ(n)表示小于等于n的正整数中与n互质的数的个数。

以下是使用C语言实现欧拉定理的代码:

#include <stdio.h>

int gcd(int a, int b)
{
    if(b==0)
        return a;
    return gcd(b,a%b);
}

int phi(int n)
{
    int result=1;
    for(int i=2;i<n;i++)
    {
        if(gcd(i,n)==1)
            result++;
    }
    return result;
}

int power(int x, int y, int m)
{
    int res=1;
    x=x%m;
    while(y>0)
    {
        if(y&1)
            res=(res*x)%m;
        y=y>>1;
        x=(x*x)%m;
    }
    return res;
}

int main()
{
    int a=7,n=13;
    printf("a^n mod m is: %d\n",power(a,phi(n),n));
    return 0;
}

在这个例子中，我们使用了三个函数gcd, phi和power。

gcd函数用于计算两个数的最大公约数。

phi函数用于计算小于等于n的正整数中与n互质的数的个数。

power函数用于计算a^n mod m的值。

在main函数中，我们使用了以上三个函数来计算7^phi(13) mod 13的结果，结果为1。

注意：此代码仅用于演示目的，没有对足够的边界情况进行测试，不建议直接用于实际应用。