070 : トーティエント関数の置換

オイラーのトーティエント関数$φ(n)$(ファイ関数とも呼ばれる) とは,$n$未満の正の整数で$n$と互いに素なものの個数を表す. 例えば, 1, 2, 4, 5, 7, 8 は9未満で9と互いに素であるので,$φ(9) = 6$となる. 1 は全ての正の整数と互いに素であるとみなされる. よって$φ(1) = 1$である.

面白いことに,$φ(87109)=79180$であり, $87109$は$79180$を置換したものとなっている.

$1 < n < 10^7$で$φ(n)$が$n$を置換したものになっているもののうち,$n/φ(n)$が最小となる$n$を求めよ.