>>805
どこまで書き出したか知らないが、まずnが偶数のときお話にならないのはすぐわかるな？
その上でn=15くらいまでやっても条件を満たすｎが見当たらないから、ｎが1と3しかないことを示す問題だとあたりをつける。

もうひとつヒントをあげるなら、a>bとして、aとbの最大公約数はa-bとbの最大公約数に等しい（互除法）
これくらいで解けるはず