０以上の整数ｎを用いて、 Ｆｎ＝２2ｎ＋１の形の数をフェルマー数という。フェルマー数
は素数のときもあれば合成数のときもある。（→ 参考：「フェルマー素数」）
例 Ｆ0＝３、Ｆ1＝５、Ｆ2＝１７、Ｆ3＝２５７、Ｆ4＝６５５３７ までは素数が続くが、残念ながら、
Ｆ5＝４２９４９６７２９７＝６４１・６７００４１７ は合成数である。
Ｆｎ−２＝Ｆ0・Ｆ1・Ｆ2・・・・・Ｆｎ-1
と表される性質を用いて、
どの２つのフェルマー数も互いに素
であることが分かる。
実際に、Ｆｍ、Ｆｎ が１以外の最大公約数ｐを持つと仮定すると、
Ｆｎ−Ｆ0・Ｆ1・Ｆ2・・・・・Ｆｎ-1＝２ は、ｐで割り切れる。
よって、ｐ＝２ でなければならないが、すべてのｎに対して、Ｆｎは奇数なので、素因数に
２を持つことはあり得ない。矛盾が示されたので、どの２つのフェルマー数も互いに素となる。
２００２年度の同志社大学商学部で次の問題が出題された。
２16＋１、２32＋１の最大公約数を求めよ。
同志社大学は理系学部も有する総合大学であるが、上記の問題が商学部で出題された
のはとても興味深い。
Ｆ4＝２16＋１＝６５５３７とＦ5＝２32＋１＝４２９４９６７２９７はともにフェルマー数で、すべて
のフェルマー数は互いに素という事実を知っていれば、答えは、１ ということは即答だろう。
ただ、受験生にそのような知識は望むべくもないので、実際の入試問題は次のように出題
された。
次の各問に答えよ。
（１） ２０８５３と３８４３の最大公約数を求めよ。
（２） ａ、ｂ（ａ＞ｂ）を正の整数とし、ａをｂで割った余りをｒとする。ｒ≠０のとき、ａとｂの
最大公約数はｂとｒの最大公約数に等しいことを示せ。
（３） ２8−１と２16−１は３の倍数であることを示せ。
（４） ２16＋１と２32＋１の最大公約数を求めよ。
（解）（１） ２０８５３＝６３×３３１ 、３８４３＝６３×６１ で、３３１と６１は互いに素より、
最大公約数は、６３
（２） ａをｂで割った商をｑとすると、 ａ＝ｂｑ＋ｒ と書ける。
ａとｂの最大公約数をｄとおくと、 ｒ＝ａ−ｂｑ はｄで割り切れ、ｄは、ｂとｒの公約数である。
ｂとｒの最大公約数をｄ’とおくと、 ｄ’はｄで割り切れる。
逆に、ｂとｒの最大公約数をｄ’とおくと、 ａ＝ｂｑ＋ｒ はｄ’で割り切れ、ｄ’は、ａとｂの公約
数である。
このとき、ｄはｄ’で割り切れる。よって、 ｄ＝ｄ’となり、ａとｂの最大公約数はｂとｒの最大
公約数に等しいことが示された。
（３） ２8−１＝２５５＝３・８５は３の倍数
２16−１−（２8−１）＝２16−２8＝２8（２8−１）は３の倍数なので、２16−１も３の倍数
である。
（４） ２16＝ｘ とおくと、 ２16＋１＝ｘ＋１ ２32＋１＝ｘ2＋１
ｘ2＋１＝(ｘ＋１)(ｘ−１)＋２ より、２32＋１と16＋１の最大公約数は、２16＋１と２の最大
公約数に等しい。
２16＋１は奇数なので、２16＋１と２の最大公約数は、１
以上から、２32＋１と16＋１の最大公約数は、１ （終）
（コメント） （４）を解くのに（３）が必要と思いきや、必要なのは（２）の方でしたね。とんだ肩
すかしです！また、（２）が控えているので、（１）で互除法も使いづらい。問題配列
に問題有りと感じた。