# 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$$を求めよ.
