10821×11409=123456789
でした
【解方の例】
123456789は9で割り切れる。
なぜならば、(1+2+3+4+5+6+7+8+9=45となり
45は9で割り切れる)から(説明済み)。
123456789÷9=13717421
したがって、
13717421を素因数分解すれば良いことになる。
この数は8桁の数なので8桁の電卓で十分解ける。
電卓の「メモリー」に13717421を記憶させ、
7、11、13、17、19・・・・・・・3701、3703まで
割り切れるかどうか試す。
何故、3703までなのかは、
13717421の平方根√を計算すると、
3703.70・・・になるから。
だから3703以下の直近で割り切れる約数を求める。
この作業をコツコツやると、
13717421=3067×3803 であることがわかる。
123456789=3×3×3067×3803
そして、これらの素因数を組み合わせると答えになる。
10821×11409=123456789
※ 3067を一発で出したい人は、以下をご参照ください
例えば、
フェルマーの小定理を使います。
僕が学生の頃は、フォトラン(懐かすぃ)とかを使いましたが・・
x2-y2=(x+y)(x-y)
さて、ある数nが上のように2つの2乗数の差で表すことができた
としよう。
このとき、上の因数分解の公式をつかって、nをx+yとx-yに
素因数分解することができる。
xの初期値として、
x=int(sqrt(n))+1
から始める。yの初期値は、x2-nの平方根の整数部、
すなわち、
y=int(sqrt(x2-n))とする。
この初期値から以下の処理を繰り返す。
1.w=x2-n-y2を求める。
2.w=0なら、x+y、x-yが求める素因数である。
3.w>0なら、y=y+1とする。
4.w<0なら、x=x+1とする。
5.1.へ
プログラムは以下のとおり。
5 ' Fermat method
10 input "n=";N
20 X=isqrt(N)+1:Y=isqrt(X^2-N):print X,Y
30 W=X^2-N-Y^2
40 if W=0 then print X+Y,X-Y,X,Y:end
50 if W>0 then inc Y:goto 30
60 if W<0 then inc X:goto 30
yに比べてxの増え方は大きいので、xが変わるごとに、
yを計算し直すようにした方がよい。
このプログラムを実行して、13717421 を代入すると、
xの初期値は 3704。
次の 3705 で、y=98 となり、因数 3803、3607 が見つかる。
この方法によれば、素因数がnの平方根に近いとき、一瞬にし
て見つけられます。
これをp法とい言います。PINOT先生のPじゃないよ
P.S(補足)
フェルマーの小定理というのは、「素数 p に対して、勝手な整数 n
の p 乗を p で割ると余りは n に戻る」というものです。
例えば、7は素数ですが、
2の7乗 = 128 → 7で割ると商18、余り2
3の7乗 = 2187 → 7で割ると商312、余り3
4の7乗 = 16384 → 7で割ると商2340、余り4
5の7乗 = 78125 → 7で割ると商11160、余り5・・・・
という感じで、余りは7乗されたもとの数に戻ります。
式で書けば、
np ≡ n (mod p)
mod pというのは、pで割った余りで分類して考えるという意味です。
例えば、
10の7乗 = 10000000
の場合、7で割ると商1428571、余り3ですが、
3は7を法として10と合同ですから、やっぱり
10の7乗 ≡ 10 (mod 7)
が成り立ってます。「7を法にすると合同」というのは
初めて聞くと難しそうですが、3も10も7で割れば3余る仲間同士、
というだけのことです。それが mod 7 の意味です。
「7で割った余りで考えるモード」では、3も10も73も「同じグループ」
として同一視できるわけです。
この場合の「同じ」は等号 = の「等しい」とは意味が違うので
三本線の合同記号 ≡ を書いて「合同だ」といいます。
10の7乗 も 10 も「7で割った余りで考えるモード」では、どっちも
「3余るグループ」なので、これらは合同です。
以 上