■N 桁の数 X を素数(2, 3, 5, 7, 11, 13, ...)で割った余りを簡単に求める方法、repunit数にも関連して

■N 桁の数 X を素数(2, 3, 5, 7, 11, 13, ...)で割った余りを簡単に求める方法、repunit数にも関連して
　　　version 1.00 (2024/6/27) by 澤田石　順 jsawa@nifty.com
　　　
▼はじめに

• 用語の定義: n は自然数

• 用語の定義: p は素数 (2, 3, 5, 7 ...)

• 用語の定義: 自然数 X ≡ r (mod p) おける ≡ という記号は X を素数 p で割った余りのこと

• 表現の定義: 例えば p = 7 の時で X = 12 の場合 r = 5 であるが、5 - 7 = -2 であるから、 -2 ≡ 5 (mod 7)。 r が p の半分未満の時、r を r - p と置換してもよい

X を素数 p で割った余り(X mod p)を求める方法で良く知られているのは
p = 2: X の一桁目が偶数なら 0, 奇数なら1、何故ならば N 桁の数 X おいて10, 100, 1000, ... は必ず 2 の倍数なので一桁だけ考えたら良い
p = 3: X = abcdef..と表記される時、N 桁の数 X の全桁の数値を足して 3 で割った余り。何故ならば 10 の n 乗は常に 999 +1 のごとく3で割って余り1だから。それぞれの桁における数値はそのまま3で割った余りなのであるから、N 桁の１つ１つの数字を足して 3 で割れば X の余りとなる
p = 5: 3の時と同様に、10, 100, 100 は常に 5 で割って余り0。だから、一桁の数を5で割った余りが n の余りとなる
ここまでは中学生水準

さて、7 で割った余りのこと。幾つか方法はあるがややこしい。私が見出した方法は簡単明瞭であり、なんと、これまで web 検索したところ誰も記してない。まさか、私が最初の発見者ではないと思うが・・・。

▼ X を 7 で割った余りを簡単に計算する方法
1桁目からN桁目まで、１つずつ余りを求める
1桁目 = 10^0 = 1: 7で割った余りは1。よって、一桁目が x なら 7で割った余り⇒例えば 2 なら 2, 6 なら 6 (≡-1)
2桁目 = 10^1 = 10: 10を7で割った余りは 3。10 ≡ 3 (mod 7)。従って、2桁目の数値かける3の余りが7の余り。例えば 6 ならば 6×3=18 を7で割り、4 or -3 となる
3桁目 = 10^2 = 100: 100を7で割った余りは 2。100 ≡ 2 (mod 7)。従って、3桁目の数値かける2の余りが7の余り。例えば 3 ならば 3×2=6 を7で割り、6 or -1 となる
4桁目 = 10^3 = 1000: 100 ≡ 2 (mod 7) であるから、2×10 = 20 = 3×7 -1 なので 1000 ≡ -1 (mod 7)。なんと一桁目の 1 を負記号とした -1
5桁目 = 10^4 = 10000: 100 ≡ 2 (mod 7)なので、10000 ≡ 2×2 ≡4 ≡ -3 (-3 + 7)。なんと、3桁目の 3 を負にした数
6桁目 = 10^5 = 10^2×10^3 ≡ 2 × -1 ＝ -2
7桁目 = 10^6 = 10^3×10^3 ≡ -1 × -1 ＝ 1　←ここで 1に戻り、8, 9, 10.. 桁目の10の n 乗は繰り返す。

以上の単純なやり方により判明したことは、X(自然数)を7で割った余りを求める方法
素数7の余りサイクルは一桁目から(1, 3, 2, -1, -3, -2)である。例えば、 X が 下一桁から n1 n2 n3 n4 n5 n6 ならば
n1×1 + n2×3 + n3×2 + n4×-1 + n5×-3 + n6 ×-2 の合計を 7 で割った余りが、X の余りとなる。
X の桁数 N が6の倍数であれどうであれ、簡単にできるのだ。この 1, 3, 2, -1, -3, -2 に関して円グラフを描くならば理解は容易となる。その円グラフは 360÷6、つまり六十度に分割される。素数 7 で X を割った余りの計算はこうなる

k = 0, 1, 2, 3 ...の整数とする。k桁目に関して
6k + 1(1桁目+7桁目+13桁目..)の合計 - 6k+4(4桁目+10桁目+16桁目..)の合計 +
6k + 2(2桁目+8桁目+14桁目..)の合計 - 6k+5(5桁目+11桁目+17桁目..)の合計 +
6k + 3(3桁目+9桁目+15桁目..)の合計 - 6k+6(6桁目+16桁目+22桁目..)の合計
を求める。その総計を 7 で割った余りが X の余りとなる。

このように記載するとややこしいかもしれないが具体例を示すと容易さがわかると思う。
7635の余り: 1, 3, 2, -1, -3, -2 の順番は逆に適用する
5×1 + 3×3 + 2×6 + 7×-1 = 5 + 9 + 12 -7 = 19 ≡ 4 となる。
ある数がabcdef(の6桁)ならば
a×1 + b×3 + c×2 + d×(-1) + e×(-3) + f×(-2)
すなわち(a-d)+3×(b-e)+2×(c-f)を7で割った余りとなる。

以下、いろいろな素数についてサイクルを求めてみた。一部のみ抜粋

▼素数 13 のサイクル
(1, -3, -4, -1, 3, 4) の6サイクル

▼素数11のサイクル: (1, -1)の２サイクル (1-1=0)
　なので、数値の奇数合計から偶数合計を引いた数で11の余りが算定できる

▼素数37: (1, 10, -11) [1+10-11=0]、サイクルは3

▼素数101: (1, 10, -1, -10)の4サイクル

▼素数41: (1, 10, 18, 16, -4)の5サイクル。その合計は0 (mod 41)

▼素数271: 5サイクル

▼素数73 (1, 10, 27, -22, -1, -10, -27, 22)の８サイクル

▼素数9091: (1, 10, 100, 1000, 909, -1, -10, -100, -1000, -909)の10サイクル

▼素数17: 16サイクル(1, -7, -2, -3, 4, 6, -8, 5, -1, 7, ,2, 3, -4, -6, 8, -5)

■数値 X を素数 p で割った余りに関して: repunit数を取り上げる
R(n)=1111.. (1の数がn個)と定義する
　極めて単純なやりかたで、簡単に素因数分解を試みることかできることが判明した。重要なことはサイクルの数である。例えば7や13の如き偶数サイクルの場合は、10のゼロ乗から5乗であり、(0+6)÷2=3 が常に -1 となる。7とか13のような偶数サイクルの場合、具体的には7 and 13は(1, 3, 2, -1, -3, -2)、(1, -3, -4, -1, 3, 4)であり合計は０であり、なおかつプラスとマイナスが交替している。偶数サークルの時、必ず -1 を含むのである。自明なことは奇数であれ偶数であれ、サイクルにおける余りを合計すると常に余り０となること。すなわち、サイクルの数が偶数 n ならば、R(n)は必ず偶数サークルの数 n で割り切れるのであり、7や13の偶数ならばabcabcの如き繰り返しでR(偶数)が割り切れること。
　サイクルが奇数の場合、例えば37とか41の時、37のサイクルは3なのでR(3)=111を必ず割り切るし、41のサイクルは5なのでR(5)=11111を41は割り切る。3に関しては、nが三の倍数ならばR(n)が割り切れるし、nが9の倍数のときもそう。
以上のことを別の観点から表現すると、R(n)においてnが2の倍数ならば必ず11で割り切れ、nが3の倍数ならは37及び3で、9の倍数ならば9で割り切れ、6の倍数ならば7 and 13で割り切れ、R(5)ならば41 and 271で割り切れる。
　私はたまたま、7 で割った余りがいくつになるのか単純な検討をした、素数マニアではあるが、いまだに整数論をよくわかってないが、それなりに面白い結果が得られたと思う。