『オイラーの関数』

　今回のテーマは、あのオイラーの関数です。
今、１以下の、分母が６の分数を考えます。（正の数）
これは

１
――
６，２
――
６，３
――
６，４
――
６，５
――
６，６
――
６

の６個ありますね。

そのうちで約分できないのは分子が１と５の２個です。
（これは分子と分母が互いに素になる場合、つまり最大公約数が１である場合です。）
この時、φ(６）＝２と表すことにします。

同様に考えると
φ(２）＝１，φ(３）＝２（分子が１と２），φ(４）＝２（分子が１と３）

【問題】

φ(９），φ(１０）とφ(１１）を計算してください。
今、ｐは素数であるとします。
ｎ＝ｐ^mとするとき、φ(ｎ）＝ｐ^m－ｐ^m-1となる理由を考えてください。
特に、ｐが素数のとき、φ(ｐ）＝ｐ－１となります。
ａ，ｂは自然数で、ａとｂは互いに素であるとするとき、
φ(ａ×ｂ）＝φ(ａ）×φ(ｂ）となる理由を考えてください。
２，３を用いてφ(１４００）を計算してください。

◆おまけ（高校生以上向き、難問）

　ａとｂは互いに素であるとすると、
　ａ^φ(ｂ）をｂで割った余りは１になります。
　この理由を説明してください。

　特に、ｐが素数でａとｐが互いに素なら、
　ａ^p-1をｐで割った余りは１です。