>>689
最大公約数が1より大きいならば, 公約数のなかに素数が存在するはずである(最大公約数の素因数分解を考えよ).
ここでA^cの約数のうち素数であるものdを適当にとってくると, これはAの約数である.
一方でkA+1をdで割ると1余るのでdはkA+1の約数でないので, 素数であるような公約数は存在しない.