問題

問題概要

1より大きい整数 $N$ が与えられる。次のような関数を考える：

$f(a) = a^N \ mod \ N$
$F_1 (a) = f(a)$
$F_{k+1} (a) = F_{k} (f(a)) \ (k = 1,2,3, \ldots)$

この時、 $1 \le a \le N-1$ の $a$ について $F_{k} (a) = a$ が成り立つような最小の $k$ を求めよ。このような $k$ が存在しない時は、-1を出力せよ。

$2 \le N \le 10^9$

アイデア

まず、考察したこととしては、 $N$ が素数の時は、フェルマーの小定理から $f(a) = a$ であることがわかるので素数の時は1が答えになると思った。ただ、素数で無いときにも答えが1になることはあるようでこのような条件を満たす数にはカーマイケル数という名前がついているらしい。

$F_k$ は漸化式の形になっているが、これは帰納的に $F_k (a) = a^{N^k}$ であることが示せる。

$m$ を素数として、 $N = p^2 N'$ のとき、 $p^{N^k} \equiv p (mod \ N)$ となることはない。こうなるということは、 $p^{N^k} = Nx + p$ と書けるということだが、 $Nx + p = p(pxN' +1)$ とくくると、この数は $p$ しか素因数を持たないはずなのに、括弧内の数はどのように $x$ を選んだとしても $p$ の倍数になることはないからである。

つまり、これ以降で考えるべき $N$ としては $N = p_1 p_2 \ldots p_m$ のように、各素因数が1つのみである素数の積の形をしている。

さて、 $a^{N^k} \equiv a (mod \ N)$ が成り立つためには、各素数 $p_i$ でも $a^{N^k} \equiv a (mod \ p_i)$ が成り立っているはずである。さらに、これは $1 \le a \le N-1$ の $a$ について成り立っているので( $a$ と $p_i$ が互いに素なときでも成立しなければならない)、指数の肩に注目すると $N^k - 1 \equiv 0 (mod \ p_i - 1)$ と言い換える事ができる。

これが $1 \le i \le m$ の $i$ について成り立っていて欲しい、ということはLCMを考えて $L = lcm(p_1 -1 , p_2 -1 , \ldots , p_m -1)$ で割り切れて欲しいということになる。よって、この問題は $N^k \equiv 1 (mod \ L)$ を満たす最小の $k$ を見つける、と言う問題になった。

まず、 $N$ と $L$ が互いに素でないならこのような $k$ は存在しない。そして互いに素である場合には、この $k$ はオイラー関数 $\phi (L)$ の約数である(!?)ので、約数を列挙して順番に試せば良い。

とあるが、なんで約数しかみなくていいんだ...ってなったが、もう一度求めたいものをみてみると、この求めたい $k$ というのはまさにカーマイケルのλ関数によって与えられるものであり、それがオイラー関数の約数であることは定義より明らかである(オイラー関数は単純に掛け算しているところで、カーマイケルのλ関数はLCMを取っているので)(参考)。

ただ、今回はNについてのみ成り立ってくれればいいので、やはり約数を小さい方から順にチェックする必要がある。

実装(C++)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second
#define dbg(x) cout<<#x" = "<<((x))<<endl
template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

int lcm(int x, int y){
    return x/__gcd(x,y)*y;
}

int euler_phi(int n){
    if(n==0) return 0;
    int ret = n;
    for(int i=2; i*i<=n; ++i){
        if(n%i==0){
            ret -= ret/i;
            while(n%i==0) n/=i;
        }
    }
    if(n!=1) ret -= ret/n;
    return ret;
}

map<int,int> factorize(int n){
    map<int,int> ret;
    for(int i=2; i*i<=n; ++i){
        while(n%i==0){
            n/=i;
            ++ret[i];
        }
    }
    if(n>1) ++ret[n];
    return ret;
}

ll mod_pow(ll x, ll n, ll mod){
    ll ret = 1;
    while(n){
        if(n&1) (ret*=x)%=mod;
        (x*=x)%=mod;
        n>>=1;
    }
    return ret;
}

int main(){
    int n;
    cin >>n;

    map<int,int> f = factorize(n);
    int L = 1;
    for(const auto &p:f){
        if(p.se>1){
            cout << -1 << endl;
            return 0;
        }
        L = lcm(L, p.fi-1);
    }

    if(__gcd(n,L)!=1){
        cout << -1 << endl;
        return 0;
    }

    int ans = L;
    int P = euler_phi(L);
    for(int i=1; i*i<=P; ++i){
        if(P%i==0){
            for(int d:{i,P/i}){
                if(mod_pow(n,d,L) == 1) ans = min(ans,d);
            }
        }
    }

    cout << ans << endl;
    return 0;
}

裏紙

ほぼ競プロ、たまに日記

AOJ 2720 - Identity Function

問題

問題概要

アイデア

実装(C++)