オイラーの定理

無数に定理を残したオイラーですが、数学で単に「オイラーの定理」というと、

a^φ(n) ≡ 1 (mod n)
aとnは互いに素

のことを言います。φ(n)はオイラーのφ関数です。
nが素数の場合、フェルマーの小定理になります。

a^n-1 ≡ 1 (mod n)

証明は適当なものを参照してもらうことにして、ここではいくつかの例でこの定理を確認しましょう。

a = 7
n = 2 : 7¹ = 3 * 2 + 1
n = 3 : 7² = 16 * 3 + 1
n = 4 : 7² = 12 * 4 + 1
n = 5 : 7⁴ = 480 * 5 + 1
n = 6 : 7² = 8 * 6 + 1
n = 8 : 7⁴ = 300 * 8 + 1

最後に、決められた範囲で定理の正しさを確認するコードを示します。

from itertools import takewhile

from fractions import gcd
def gen_prime_candidates():

    yield 2

    yield 3

    n = 0

    while True:

        yield n + 5

        yield n + 7

        n += 6
def calc_exp(n, p):

    e = 0

    while n % p == 0:

        e += 1

        n /= p

    return e, n
# 60 = 2^2*3*5 -> (2, 3, 5)

def factorize(n):

    f = ()

    for p in takewhile(lambda p: p * p <= n, gen_prime_candidates()):

        e, n = calc_exp(n, p)

        if e:

            f = f + (p, )

    if n > 1:

        f = f + (n, )

    return f
def phi(n):

    return reduce(lambda x, p: x * (p - 1) / p, factorize(n), n)
# n^e % d

def pow_mod(n, e, d):

    if e == 0:

        return 1

    m = pow(n, e >> 1, d)

    p = m * m % d

    if e & 1:

        p = p * n % d

    return p
def gen_an():

    for a in xrange(2, N):

        for n in xrange(2, M):

            if gcd(a, n) == 1:

                yield a, n
N = 1000

M = 10000

for a, n in gen_an():

    if pow_mod(a, phi(n), n) != 1:

        print a, n