■記事リスト / ▼下のスレッド
/ ▲上のスレッド
□投稿者/ 雷 一般人(2回)-(2025/08/22(Fri) 13:32:21)
 | 自然数nに対してφ(n)をnと互いに素なn以下の自然数の個数とします a,b,cはどの2つも互いに素な自然数とします a^φ(bc)+b^φ(ca)+c^φ(ab)をabcで割った余りの求め方を教えて下さい
|
|
|
▽[全レス1件(ResNo.1-1 表示)]
| ■53023 / ResNo.1) |
Re[1]: オイラー関数と余り
|
□投稿者/ WIZ 一般人(2回)-(2026/01/20(Tue) 16:19:39)
 | べき乗演算子^は四則演算子より優先度が高いものとします。
φ(bc)は自然数ですから、 a^φ(bc) ≡ 0 (mod a)
cとaは互いに素であり、オイラーのトーシェント関数の性質より b^φ(ca) = (b^φ(a))^φ(c) ≡ 1^φ(c) ≡ 1 (mod a)
同様にaとbも互いに素なので c^φ(ab) = (c^φ(a))^φ(b) ≡ 1^φ(b) ≡ 1 (mod a)
以上から a^φ(bc)+b^φ(ca)+c^φ(ab) ≡ 0+1+1 ≡ 2 (mod a)
bとcを法とした場合も同様に a^φ(bc)+b^φ(ca)+c^φ(ab) ≡ 1+0+1 ≡ 2 (mod b) a^φ(bc)+b^φ(ca)+c^φ(ab) ≡ 1+1+0 ≡ 2 (mod c)
・・・なので、中国剰余定理を持ち出すまでもなく、 a^φ(bc)+b^φ(ca)+c^φ(ab) ≡ 2 (mod abc) と言えます。
しかしながら a ≦ 2 の場合は a^φ(bc)+b^φ(ca)+c^φ(ab) ≡ 2 ≡ 0 (mod a) とも言えますので、厳密には以下の通りです。
整数xを a ≦ 2 なら x = 0、a > 2 なら x = 2、 整数yを b ≦ 2 なら y = 0、b > 2 なら y = 2、 整数zを c ≦ 2 なら z = 0、c > 2 なら z = 2 とします。
aとbcは互いに素なので、ある整数(自然数とは限らない)pとuが存在して pa+ubc = 1 とできます。 bとcaは互いに素、cとabも互いに素なので、ある整数q, v, r, wが存在して、 qb+vca = rc+wab = 1 とできます。
すると、 a^φ(bc)+b^φ(ca)+c^φ(ab) ≡ xubc+yvca+zwab (mod abc) となる訳ですが、何だか上記の式の右辺は分かりづらいですね。
|
|
|
■記事リスト /
レス記事表示 →
[親記事-1]
|