自然数ｎの素因数の積をｆ（ｎ）で表す。
ただし、ｆ（１）＝１とする。
たとえば、
ｆ（８）＝２、ｆ（12）＝６
８の素因数は２、12の素因数は２と３だからね。
このｆを確か“オイラー関数”といったはず。。
問題
ｍ、ｎを自然数、ｄをｍ、ｎの最大公約数とする。
このとき、以下の等式が成り立つことを示せ。
ｆ（ｄ）ｆ（ｍｎ）＝ｆ（ｍ）ｆ（ｎ）
誤答例
ｐ_i、ｑ_j、ｒ_kを素数、
a_i、b_j、c_kを自然数、
i=1,...,s、j=1,...,t、k=1,...,uを番号として、
ｍ＝ｐ_1＾a_1・・・ｐ_s＾a_s・ｑ_1＾b_1・・・ｑ_t＾b_t
ｎ＝ｐ_1＾a_1・・・ｐ_s＾a_s・ｒ_1＾c_1・・・ｒ_u＾c_u
と表せる。
（ｄ＝ｐ_1＾a_1・・・ｐ_s＾a_sってことです）
すると、
ｆ（ｄ）ｆ（ｍｎ）＝ｐ_1・・・ｐ_s・ｐ_1・・・ｐ_s・ｑ_1・・・ｑ_t・ｒ_1・・・ｒ_u
（＝Πｐ_i・Πｐ_i・Πｑ_j・Πｒ_k）
ｆ（ｍ）ｆ（ｎ）＝ｐ_1・・・ｐ_s・ｑ_1・・・ｑ_t・ｐ_1・・・ｐ_s・ｒ_1・・・ｒ_u
（＝Πｐ_i・Πｑ_j・Πｐ_i・Πｒ_k）
よって、成り立つ。□
これは、おかしい。
たとえば、
ｍ＝８、ｎ＝12とすると、
ｍ＝２＾3、ｎ＝２＾2・３、ｄ＝２＾2
ｐ、ｑ、ｒは、
ｐ_1＝２、ｑ_1＝２、ｒ＝３
上の証明に従うなら、
ｆ（ｄ）ｆ（ｍｎ）＝２・２・２・３
ｆ（ｍ）ｆ（ｎ）＝２・２・２・３
となるが、
よく考えると、
ｆ（ｍ）＝ｆ（８）＝２、ｆ（ｎ）＝ｆ（１２）＝６
だから、
ｆ（ｍ）ｆ（ｎ）＝２・２・３
のはずである。
上の証明で、
ｆ（ｍ）ｆ（ｎ）＝・・・
の式は誤りである。
ｐ_iとｑ_jの中に同じ素数がありうること
（ｍ＝８、ｎ＝12とすれば、ｐ_1=ｑ_1=２）
を失念している。
同様の理由で、上の証明で
ｆ（ｄ）ｆ（ｍｎ）＝・・・
の式も誤りである。
解答例
まず次のことに注意する。
（１）ｍがｎで割り切れるときｆ（ｍｎ）＝ｆ（ｍ）
（２）ｍとｎが互いに素であるときｆ（ｍｎ）＝ｆ（ｍ）ｆ（ｎ）
ｍ＝ｄｍ’と書く。
ｄとｍ’の最大公約数をｖとすると
ｍ’＝ｖｍ”であり、ｄとｍ”は互いに素。
ｎ＝ｄｎ’と書く。
ｄとｎ’の最大公約数をｗとすると
ｎ’＝ｖｎ”であり、ｄとｎ”は互いに素。
また、
ｄはｍとｎの最大公約数だから、ｍ’とｎ’は互いに素。
よって、
それぞれｍ’、ｎ’の約数である、ｍ”とｎ”も互いに素。
ｆ（ｄ）ｆ（ｍｎ）
＝ｆ（ｄ）ｆ（ｄｍ’ｄｎ’）
＝ｆ（ｄ）ｆ（ｄｍ’ｎ’） （∵ｄはｄで割り切れる）
＝ｆ（ｄ）ｆ（ｄｖｍ”ｗｎ”）
＝ｆ（ｄ）ｆ（ｄｍ”ｎ”） （∵ｖとｗはｄの約数）
＝ｆ（ｄ）ｆ（ｄｍ”）ｆ（ｎ”）
（∵ｎ”はｄ、ｍ”とそれぞれ互いに素だからｎ”はｄｍ”と互いに素）
＝ｆ（ｄｍ”）ｆ（ｄｎ”） （∵ｄとｎ”は互いに素）
＝ｆ（ｄｖｍ”）ｆ（ｄｗｎ”） （∵ｖ、ｗはｄの約数）
＝ｆ（ｍ）ｆ（ｎ） □
上の図は、V字で最大公約数を、
曲線矢印で最大公約数を取り去った残りを
表しています。（残り物を吐き出すイメージ）
約数とか互いに素とか、頭の中だけで考えてると
ややこしいので、図で書くと多少わかりやすいかな？
解答例では、素因数を明示しない形で
答案を書きましたが、
誤答例のように素因数を使って
書くこともできます。
上の誤答例は添え字がいっぱいで
「読む気がしない」という人のために、
誤答例を、素因数を使わずに書いてみましょう。
誤答例（その２）
ｍ＝ｄｍ’
ｎ＝ｄｎ’
と表せる。すると、
ｆ（ｄ）ｆ（ｍｎ）＝ｆ（ｄ）ｆ（ｄ）ｆ（ｍ’）ｆ（ｎ’）
ｆ（ｍ）ｆ（ｎ）＝ｆ（ｄ）ｆ（ｍ’）ｆ（ｄ）ｆ（ｎ’）
よって、成り立つ。□
素因数を書いているか書いてないかではなく、
ｄとｍ’（あるいはｄとｎ’）が互い素とは限らない
というところがポイントです。