◆東京都 px さんからの解答。
【問題１】
１０a＋１が２a＋１で割り切れるためには
１０a＋１≡０ ｍｏｄ ２a＋１
１０a≡−１ ｍｏｄ ２a＋１
１０a≡２a ｍｏｄ ２a＋１
これを満たすａは
２a＋１＝２，４，８
のどれかなのでこれをみたす自然数ａは存在しない。
◆出題者のコメント
pxさんの回答の中でわからないところがあるので教えてください。
10a≡2a(mod 2a + 1) ...(1)
まではわかりますが、そこから
「これを満たすaは 2a + 1 = 2, 4, 8」
となるところがわかりません。
2a + 1と2aとは互いに素なので、(1)から
5a≡1 (mod 2a+ 1)となると思いますが、
これからでも「2a + 1 = 2, 4, 8」は言えるのでしょうか。
◆埼玉県 \aleph_0 さんからの解答。
＃文字を多少変えてしまいましたが，ご了承ください．
【問題１】
以下，正整数mおよびmと互いに素な整数aに対して，
om(a)でaの法mに関する位数を表す．
また，素数pおよび整数a≠0に対して，vp(a)でaのp進付値（aを割り切るpの最高べき指数）を表す．
補題1．
整数aおよび正整数n, mに対して，m|an−1ならば，次が成り立つ．
(a) om(a)|gcd(n, φ(m)). （φ(m)はEuler関数）
(b) mが奇数で，mの任意の素因数pに対して
v2(p−1)＞v2(n)ならば，(a/m)＝1.
（(a/m)はJacobi記号）
証明．
(a) an≡1 (mod m)より，om(a)|nであり，
Eulerの定理より，om(a)|φ(m)である．
(b) p|mならば，(a)より，op(a)|gcd(n, p−1)|(p−1)/2であるから，
Eulerの規準より，(a/p)≡a(p−1)/2≡1 (mod p).□
補題2．
kを非負整数とするとき，Fk＝22k＋1の任意の素因数pに対して，
v2(p−1)≧k＋1.
証明．
22k≡-1 (mod p), 22k+1≡1 (mod p)であるから，
Fermatの定理より，op(a)＝2k+1|p−1.□
定理3．
任意の正整数nに対して，2n＋1は10n＋1を割り切らない．
証明．
2n＋1|10n＋1と仮定すると，
10n≡-1≡2n (mod 2n＋1)より，
5n≡1 (mod 2n＋1)であるから，2n＋1|5n−1.
このとき，k＝v2(n)とすると，Fk|2n＋1|5n−1であり，
補題2より，Fkの任意の素因数pに対して，v2(p−1)＞v2(n).
したがって，補題1(b)より，(5/Fk)＝1，すなわちFk≡±1 (mod 5).
ところが，F0＝3, F1＝5, Fk≡2 (mod 5) (k≧2)であるから，これは矛盾．□
【問題２】
＃こちらは完全に解けたわけではないので，分かったところまで書きます．
まず，正整数nに対して，Mn＝2n−1とおく．
このとき，Mn|(10n−1)/9ならば，10n≡1≡2n (mod Mn)より，
5n≡1 (mod Mn)であるから，Mn|5n−1に注意する．
また，d|nならば，Md|Mnにも注意する．
命題4．
正整数nに対して，Mn|(10n−1)/9ならば，nは奇数である．
証明．
nが偶数であると仮定する．
このとき，3|M2|Mn|(10n−1)/9より，
10n≡1 (mod 27)であるから，o27(10)＝3|n，
したがって，6|n.
このとき，9|M6|Mn|(10n−1)/9より，
10n≡1 (mod 81)であるから，o81(10)＝9|n.
このとき，73|M9|Mn|5n−1より，
5n≡1 (mod 73)であるから，o73(5)＝72|n，
特に，4|n.
このとき，5|M4|Mn|5n−1となり矛盾．□
命題5．
正の奇数nに対して，Mn|5n−1とする．
このとき，Mnの任意の正の約数Dに対して，D≡±1 (mod 5)が成り立つ．
また，nの任意の正の約数dに対して，d≡1 (mod 4)が成り立つ．
証明．
D|Mn|5n−1であり，Dの任意の素因数pに対して，
v2(p−1)≧1＞0＝v2(n).
したがって，補題1(b)より，(5/D)＝1，すなわちD≡±1 (mod 5).
特に， d|nならば，Md|Mnより，Md≡±1 (mod 5).
このとき，d≡3 (mod 4)と仮定すると，
2d≡23≡3 (mod 5)より，Md≡2 (mod 5)となり矛盾．□
命題6．
正の奇数nに対して，Mn|5n−1とする．
このとき，nの最小の素因数qに対して，次が成り立つ．
(a) q≡1 (mod 4).
(b) Mqの任意の素因数pに対して，p≡±1 (mod 5).
(c) Mqの任意の素因数pに対して，
s＝「p−1の素因数rで，r≧qかつr≡1 (mod 4)であるもの全体（重複を含む）の積」
とおくとき，5s≡1 (mod p).
証明．
(a), (b)は命題5から従う．
(c)については，補題1(a)より，op(5)|gcd(n, p−1)|sに注意すればよい．□
以下は，小さな素数q≡1 (mod 4)に対するMqの一つの素因数p，および命題6のsと5s mod pの値である．
| q | p | s | 5s mod p |
|---|---|---|---|
| 5 | 31 | 5 | 25 |
| 13 | 8191 | 13 | 6586 |
| 17 | 131071 | 17*257 | 36977 |
| 29 | 233 | - | - |
| 37 | 223 | - | - |
| 41 | 13367 | - | - |
| 53 | 6361 | 53 | 4612 |
これより，Mn|(10n−1)/9ならば，nの素因数≧61が分かる．
最後に，与えられた条件を満たすMnの素因数の上界を与える．
補題7．
互いに素な整数a, b＞1および正整数nに対して，
奇素数巾peがan−1とbn−1の両方を割り切るならば，
A＝{axby＜pe | x, yは非負整数}とおくとき，#A≦nが成り立つ．
特に，log pe＜√(2n log a log b) （底は任意の実数＞1）が成り立つ．
証明．
an≡bn≡1 (mod pe)より，
任意の非負整数x, yに対して，(axby)n≡1 (mod pe)が成り立つ．
ところが，法peに関する1のn乗根は高々n個しか存在しないから，前半の主張が従う．
このとき，#Aはxy平面上の三角形「x≧0, y≧0, x log a＋y log b＜log pe」に含まれる格子点の個数に等しいから，
#A＞(1/2)*(log pe/log a)*(log pe/log b).
これより，後半の主張が従う．□
命題8．
正整数nに対して，Mn|5n−1ならば，Mnの任意の素巾因数peに対して，
pe＜2√(2cn) (c＝log25).
特に，ω(N)を「Nの相異なる素因数の個数」とするとき，
ω(Mn)＞√(n/2c)が成り立つ．
証明．
a＝2, b＝5に対して，底を2として補題7を適用すれば，前半の主張が従う．
後半は前半から従う．□
【問題３】
残念ながら，今のところ特に思いつきません．もう少し考えてみます．