平成１７年５月６日 当ＨＰの掲示板「出会いの泉」に、ポルテ 様から質問があった。
掲示板上では既に解決されているが、掲示板は時とともに消え去る運命なので、ここにそ
の記録をとどめることにした。解決にご尽力いただいたらすかるさんに感謝いたします。
質問内容
ｍ、ｎ が自然数で互いに素ならば、 ２ｍ−１ と ２ｎ−１ も互いに素？
例 ｍ＝４、ｎ＝５ のとき、ｍ、ｎ は互いに素。このとき、
２4−１ ＝ １５ と ２5−１ ＝ ３１ も互いに素
例 ｍ＝４、ｎ＝６ のとき、ｍ、ｎ の最大公約数は、２。このとき、
２4−１ ＝ １５ と ２6−１ ＝ ６３ の最大公約数は、３ （＝２2−１）
このことから、ｍ と ｎ の最大公約数を、（ｍ ， ｎ）＝ｄ で表すと、
（２ｍ−１ ， ２ｎ−１） ＝ ２ｄ−１
の成り立つことが予想される。
実際に、ｎ＞ｍ とし、ｍ＋ｋ＝ｎ （ｋ は自然数）とすると、
２ｎ−１＝２ｍ＋ｋ−１＝２ｍ２ｋ−１＝（２ｍ−１）２ｋ＋２ｋ−１
上式により、 （２ｎ−１，２ｍ−１）＝（２ｍ−１，２ｋ−１） であることが言える。
この操作を続けることにより、互除法の場合と同様にして、
（２ｍ−１ ， ２ｎ−１） ＝ ２ｄ−１
の成り立つことが分かる。
したがって、ｍ、ｎ が自然数で互いに素ならば、ｄ＝１ なので、
（２ｍ−１ ， ２ｎ−１） ＝ ２−１＝１
となり、２ｍ−１ と ２ｎ−１ は互いに素となる。
これに対して、当ＨＰがいつもお世話になっているらすかるさんは次のような解を示された。
（平成１７年５月６日付）
対偶を示す。すなわち、２ｍ−１ と ２ｎ−１ が共通の素因数 ｋ＞２ を持ったとすると、
２ｍ≡１ （ｍｏｄ ｋ） 、 ２ｎ≡１ （ｍｏｄ ｋ）
となる。このとき、２ｘ≡１ （ｍｏｄ ｋ） となる最小の正の整数を ｐ とすれば、
明らかに ｐ≧２ であり、また、ｍ 及び ｎ が ｐ の倍数となるので、ｍ と ｎ は互いに素でない。
従って、ｍ、ｎ が自然数で互いに素ならば、２ｍ−１ と ２ｎ−１ は互いに素となる。
（追記） 当ＨＰ読者のＨＮ「タニヤン」さんから質問がありました。（平成２５年５月１０日付）
「ｍ 及び ｎ が ｐ の倍数となるので、ｍ とｎ は互いに素でない。」について、
２m≡1≡２n で、２ｘ≡１ （mod ｋ） となる最小の正の整数を ｐ とした時、
「m および n が、必ず ｐ の倍数となる」というのは、証明無しに使えるのでしょうか？
質問を受けて、証明の補足をしてみました。
２ｘ≡１ （ｍｏｄ ｋ） となる最小の正の整数を ｐ とする。
２ｍ≡１ （ｍｏｄ ｋ）において、ｍをｐで割った商をｍ’、余りをｒとすると、
ｍ＝ｍ’ｐ＋ｒ （０≦ｒ＜ｐ）
このとき、 ２ｍ＝２ｍ’ｐ＋ｒ＝（２ｐ）ｍ’・２ｒ≡２ｒ≡１ （ｍｏｄ ｋ） において、ｐの最小性から、
ｒ＝０ でなければならない。すなわち、ｍはｐで割り切れる。
同様にして、２ｎ≡１ （ｍｏｄ ｋ）のとき、ｎはｐで割り切れる。
以上から、ｍ および ｎ は、必ず ｐ の倍数となることが示された。