インテジャーズ

インテジャーズ

数、特に整数に関する記事。

全ハーシャッド数

6といえば最小の完全数であるという事実が真っ先に思い浮かびますが、最大の全ハーシャッド数であるという性質も持っています。

ハーシャッド数とは「各桁の数の総和が自分自身を割り切るような正整数」として定義され、

integers.hatenablog.com

において「ハーシャッド数が21連続して出現することはない」ことの証明を解説しました。そこでは十進表記のみ扱っていますが、b \geq 2に対して b進法表記におけるハーシャッド数を考えることができます(b-ハーシャッド数)。

この記事では全ハーシャッド数を考えます。

定義 任意のb \geq 2に対して b-ハーシャッド数であるような正整数のことを全ハーシャッド数(all-Harshad number)という。

b進表記を右下に{}_{(b)}を付けて表します。

最も自明な基本性質: 正整数nに対して、
b > nならば n=n_{(b)}であり、nb-ハーシャッド数。

1は全ハーシャッド数: 基本性質より。

2は全ハーシャッド数: 2=10_{(2)}であり、1+0=1 \mid 2なので、22-ハーシャッド数。あとは基本性質。

32-ハーシャッド数ではない: 3=11_{(2)}であり、1+1=2 \nmid 3である。

4は全ハーシャッド数: 4=100_{(2)}=11_{(3)}=10_{(4)}であり、41+0+0, 1+1, 1+0で割り切れる。あとは基本性質。

54-ハーシャッド数ではない: 5=11_{(4)}であり、1+1=2 \nmid 5である。

6は全ハーシャッド数: 6=110_{(2)}=100_{(3)}=12_{(4)}=11_{(5)}=10_{(6)}であり、61+1+0, 1+0+0, 1+2, 1+1, 1+0で割り切れる。あとは基本性質。

全ハーシャッド数はこれらで尽くされます。

定理 全ハーシャッド数は1, 2, 4, 6の4数のみである。

それでは証明しましょう。

補題 pを素数とし、nを全ハーシャッド数とする。このとき、もしn \geq 2p-1であれば、npで割り切れなければならない。

証明. n-p+1 > p-1であれば

n=1\times (n-p+1)+(p-1)=1(p-1)_{(n-p+1)}

なので、nは各桁の総和 1+(p-1) = pで割り切れなければならない。 Q.E.D.

定理の証明. n \geq 7であるような全ハーシャッド数が存在したと仮定する。このとき、補題よりn6より大きい6の倍数である。従って、p\geq 3nの最大素因数とすると、n \geq 4pであることがわかる。Bertrandの仮説より

p < q < 2p

なる素数qが存在するが、2q-1 < 4p \leq n なので、補題よりnqで割り切れなければならない。これはpnの最大素因数であることに矛盾する。 Q.E.D.