## 2018年3月27日火曜日

### 数学 - Python - JavaScript - 数学の中の女王 - 数論へのプレリュード – 合同式 - 合同式の除法(素数、二項定理、剰余)

1. $\begin{array}{}{\left(a+b\right)}^{p}\\ =\sum _{k=0}^{p}\left(\begin{array}{c}p\\ k\end{array}\right)\end{array}{a}^{k}{b}^{\left(p-k\right)}=\left(\begin{array}{c}p\\ 0\end{array}\right){a}^{0}{b}^{\left(p-0\right)}+\sum _{k=1}^{p-1}\left(\begin{array}{c}p\\ k\end{array}\right){a}^{k}{b}^{\left(p-k\right)}+\left(\begin{array}{c}p\\ p\end{array}\right){a}^{p}{b}^{0}\\ ={b}^{p}+\sum _{k=1}^{p-1}\left(\begin{array}{c}p\\ k\end{array}\right){a}^{k}{b}^{\left(p-k\right)}+{a}^{p}$

よって、

$\begin{array}{}{\left(a+b\right)}^{p}-\left({a}^{p}+{b}^{p}\right)\\ =\sum _{k=1}^{p-1}\left(\begin{array}{c}p\\ k\end{array}\right)\end{array}{a}^{k}{b}^{\left(p-k\right)}$

また、前問4より、

$p|\left(\begin{array}{c}p\\ k\end{array}\right)\left(k=1,\dots ,p-1\right)$

ゆえに、

${\left(a+b\right)}^{p}\equiv {a}^{p}+{b}^{p}\left(modp\right)$

が成り立つ。

（証明終）

コード(Emacs)

Python 3

#!/usr/bin/env python3
from sympy import pprint, randprime
import random

for p in [randprime(1, 100) for _ in range(10)]:
for _ in range(10):
a = random.randrange(100)
b = random.randrange(100)
expr = (a + b) ** p - (a ** p + b ** p)
for t in [f'p = {p}, a = {a}, b = {b}', expr, expr % p == 0]:
pprint(t)
print()
print()
print()


$./sample5.py p = 59, a = 93, b = 72 678504462930853642816265347225970933817459141439565250879478478002559770244314 62479174687222375714481880621023094108352678503355160 True p = 59, a = 87, b = 75 229818961593614919704264591712237457050209913162250259707808486104872429988792 83663142242058175931675838573786669020521750309878950 True p = 59, a = 68, b = 94 229818961593612349298357834696169959332571790505774296495534863736319140884809 58003338249138562355224341869653173021833158996262912 True p = 59, a = 13, b = 41 162641657450610154722506515494504811431772793707896716507465323145557632853146 2060845878135340947775506 True p = 59, a = 63, b = 76 274077393202801490458609662935882798411395365335631102630521891697530843986799 0956676783892794267194731392243664684743596601556 True p = 59, a = 13, b = 74 270149981444987737164947419754276993736051210415465605619954811468654367700245 4706013574495492742944227152558699922 True p = 59, a = 73, b = 58 829863080221721214437805017445668176153916536643757361426409591255236951192536 30750028787086076457275720097049491315217944162 True p = 59, a = 41, b = 48 103278611857003601083304674778764536858721424871807349824899676107278024553525 31185936709199379141389898130807729936 True p = 59, a = 18, b = 68 136586635125415640267204695603622097409479793525379105712681943858441547569831 5293417114023748079679939347115671552 True p = 59, a = 69, b = 37 311204630688710049155183062495258471796670237497749233381491019399046515491311 593027047760619809927674313752602939286694 True p = 67, a = 33, b = 22 402068635553985089087381217598734269719310960684283960772525563045841489149246 210545435599464315001118843481504914310 True p = 67, a = 25, b = 19 129219877375000476634855066108282133317693848914284014386093171181743233047931 454356709792018583406311938496300 True p = 67, a = 61, b = 8 159505751115177106149919667163350465251816158806295798263849303202806184287653 8217286320414805874334356018003233444817739416 True p = 67, a = 48, b = 38 408692090984008614674797230948502925472467362290399661332142694407877934468921 8223006767252460743522279320411679298738391646994432 True p = 67, a = 93, b = 69 109019948957167189001205290675735337026396638555343824083694875995223397650799 36272885072592872477476501175805169064355284233455331125863437229865662 True p = 67, a = 25, b = 50 425700977335732355238047879302325572609811923827942338303364413469010839642618 903308837752241799989860737696290016174316406250 True p = 67, a = 74, b = 59 198636907296847035783216135726123001765746358824873607411224369583960454975427 96278462375706875993472439170003243321180826018439304606371797434 True p = 67, a = 26, b = 98 181657295481832469751956747907856196390042495899647932910879304037696838499372 495431652097935627743919484654700394315112540464456270218264576 True p = 67, a = 21, b = 48 159547160511530203752456160367990261644912587094683381356662387846335833751856 2377924071726462778423742832342748470926498576 True p = 67, a = 38, b = 61 509985746249561467045605590332064518903716607675526253166845399669225085505558 14943277079055257920004180626438741297644057761717345686 True p = 43, a = 35, b = 93 407406753933505517841171876360668823853967385455993553354181772142585255236312 3750262779520 True p = 43, a = 71, b = 99 811528206347815956893218293960277885594998551615135346335182604171018402863482 561967240931934990 True p = 43, a = 43, b = 41 554637590706890044309042286292844476602567660809525729793746213859543684811564 05076 True p = 43, a = 78, b = 5 308491913292103218958386185576626089365443109584912420847767542321952807192678 88910 True p = 43, a = 20, b = 20 773712524553186749951508480000000000000000000000000000000000000000000 True p = 43, a = 20, b = 19 260482230539703789001349929591191671313461828425919593091479539613260 True p = 43, a = 58, b = 32 107752635971004869975998050595769411183623456110480861811556333094667590612729 9870720 True p = 43, a = 20, b = 62 196785476417117724246732162232957067220061523176240287480789642416568137199019 62240 True p = 43, a = 45, b = 28 132703685605775131290533342135396306552271192343124231985472696967698853148787 140 True p = 43, a = 91, b = 30 362884860329714451099265402246618491583109828668093791545468421114564248757631 598807249190 True p = 41, a = 31, b = 90 247855095685376644559793954530997065609773017602040368349512769749406793769442 44433690 True p = 41, a = 12, b = 73 127446584499866938751228787933647484682026920375226843191121628392143919497321 40 True p = 41, a = 41, b = 58 662282040784205541193902912011402639701516865389740828229326276491532343558711 3050 True p = 41, a = 53, b = 11 113028631674187539132671944575304247443846162993576644478058185861974244800 True p = 41, a = 46, b = 73 125148433031604604936302440111094072185982390559745006356005044253056938081979 69669550 True p = 41, a = 93, b = 32 940390377947786077452373233417996632531318613522340578902352651858638339659162 32948000 True p = 41, a = 29, b = 54 481062803377103296707877631893909076424240817679878802469314266638273618988095 0 True p = 41, a = 48, b = 64 104217086883019433186668457761634878212216079320595422261036334084812221875004 3750400 True p = 41, a = 16, b = 38 106694961841981929292173791410817806673433161161190780105907856264396800 True p = 41, a = 39, b = 13 22705643428677496279467120568410072007338380365932657342650435997537900 True p = 37, a = 66, b = 29 14989004361011337670375891271953206518928220937033580801048917913774271410 True p = 37, a = 77, b = 11 876481124754147315574300373486046195009743237758528791698685528847853640 True p = 37, a = 88, b = 97 767987145468966540697382216195398409832067522230134957404160801208267347395363 450680 True p = 37, a = 51, b = 51 208068509055974040133581976659063927847314478085145682089169478537580422970 True p = 37, a = 30, b = 3 148611468792007672266585281836147300650896007945910360110 True p = 37, a = 4, b = 23 91055517817211605409861803318496227992974297933724660 True p = 37, a = 76, b = 76 534826298117923186141965123102965897003777082136440036153696665393890390148382 720 True p = 37, a = 13, b = 40 6283391488977368536677644704642752810427336470310094292215687880 True p = 37, a = 66, b = 24 2027534915174293077309797420318260422958445882842005217427625299222200320 True p = 37, a = 82, b = 12 10068094923531997873295536675365826118147808958134915920236346747167703040 True p = 11, a = 32, b = 41 313140327739624495968 True p = 11, a = 0, b = 3 0 True p = 11, a = 84, b = 29 36889428983977116162924 True p = 11, a = 99, b = 10 16850881510366913399610 True p = 11, a = 76, b = 81 1427079038002144572747636 True p = 11, a = 57, b = 60 56182976548670982350340 True p = 11, a = 70, b = 89 1639009002032428634493270 True p = 11, a = 57, b = 19 467959542474533845164 True p = 11, a = 62, b = 64 126953822442777507201024 True p = 11, a = 71, b = 85 1329685619655977596644060 True p = 29, a = 74, b = 81 3308409382649879221134023137902596717815038992385487811328044730 True p = 29, a = 86, b = 81 28759256950556371988414631692917603085063621931734706663854331510 True p = 29, a = 12, b = 3 12763622589375624960636714666708540 True p = 29, a = 22, b = 49 485828339831729497221302046427623824343051041869806390 True p = 29, a = 7, b = 92 6580783947910113845043132604854550807086121985505992049420 True p = 29, a = 43, b = 38 22185312103371479654877622489372115666033339079915216630 True p = 29, a = 0, b = 46 0 True p = 29, a = 52, b = 74 8142274176055149639185169070646481135708380246518030758051840 True p = 29, a = 6, b = 24 6852417699981893283186997103799589907988480 True p = 29, a = 31, b = 23 173547751149910975895676889237177499735853001805610 True p = 53, a = 12, b = 85 198840743840341972734057515230911943191314512668775004564045021084868260635894 0231927043332975399121865180 True p = 53, a = 36, b = 28 533996758980197039315010682450519088198052866782131019778162902611009597444260 285052360264253440 True p = 53, a = 38, b = 72 156247225155419411725534500204319398588978463223159650701721554914998369708014 7565855221381915781083818885120 True p = 53, a = 48, b = 57 132749486769829840296655513213569649952428969866291372926976428584281024219346 543508236796771922319112306160 True p = 53, a = 49, b = 37 337612032045268065403486880623949015528027331360242075055229957071877431934753 5313252564985165311746810 True p = 53, a = 0, b = 18 0 True p = 53, a = 33, b = 3 301783758629580105945588031251229310557389312597784341003840839782155697112609 20620 True p = 53, a = 85, b = 82 636755889909470828763913624094437116946597781298694135726105598144784485856862 2010012695759123712803545236220213182530 True p = 53, a = 62, b = 32 376509761797910301517783487533551694872919328063037559669986179608578709900217 154649002821134013096263680 True p = 53, a = 38, b = 35 570310787482700460507950139813984727756684777749469502800364476567234439570918 307158067715725358230 True p = 47, a = 81, b = 39 526645721275276751037527824098806382062492139868306275282742915550871886908448 14448438832626165560 True p = 47, a = 68, b = 53 777879640599363303377533037871013095086050590118637691770245147542486893803353 39863834592019880172 True p = 47, a = 6, b = 57 367327402853481868118855060084442811160945414032494700543180736844756793810175 5594038 True p = 47, a = 55, b = 35 706965048952436623996874049651841045537808655797369900731425218509684782475233 07800292968750 True p = 47, a = 35, b = 98 662257479227532027511105179666924867431393567690163427923385177354325852564543 0664601795835667579330 True p = 47, a = 7, b = 35 19617071573157761063941600245842612699958807865346091187737825187192911698430 True p = 47, a = 4, b = 11 18892480075482572973742773856793673229842197704737998220 True p = 47, a = 86, b = 40 521693725690980725698992515551322493321669775871528313336121245764057706369708 617141686885448417280 True p = 47, a = 50, b = 91 103109408220517939199672566884721176324604686329885048331949238297032676830143 088077928916765913908850 True p = 47, a = 93, b = 44 266603993798585864992266230912282662715738276614093079995830127166386326770786 70389836481580716091012 True p = 97, a = 31, b = 23 110203326217262136306691952185716448719003977535374482254282627717129123039285 105554508404415768643900661551554240411989760493534833787593328997123011091066 2091603015370 True p = 97, a = 64, b = 74 370059349366971221099059468389821172370164563893426410385985002544597187797487 961824114384052720992111562910481954891086572891179923942718431537184841879464 5681760782500189868159545975932478532108957704519680 True p = 97, a = 18, b = 52 942996066945710232754545705554412927711259925777167166365698820279469193364706 953472209740765289041344763781795550935278134573866045676036827270622946172853 14710466143253702901760 True p = 97, a = 38, b = 81 212840982530258107125011275850233813554305652754172519548152520358230412770747 838605337881496498868005514322280565101628943781630495437941754866719804598869 2384292389054057743122023929290163208236888870 True p = 97, a = 19, b = 25 259961850136707676844643822512519998451911848793733325596205410078092109178287 155700558870187329793252998572785514479205154086312149020171771269289572127943 3300 True p = 97, a = 75, b = 5 397098363424627772079504887973678532962826242509060763122323699556005070842390 594540284270928149685127835257221452138014959457762821826056886392875000524327 33355090022087097167968750000 True p = 97, a = 66, b = 93 343179280270392643474808755621340256805159649871702002076754928540206241913823 278710230194600245017371659412113237163604089278243303626681352491187464370517 1893932090330387958290760347775513470342045217241021528770 True p = 97, a = 94, b = 3 496284474122144858994649504489498857615277779945292949687052852290616720494927 958459520204890207651724620822348211731745416218993546424362496670870043190169 2078615302318272300182355307673055710 True p = 97, a = 76, b = 4 395111210906523370963615822866692141745664856712080978882026813781783093026535 314664799583134071436216565023866864098712562941659252391043588537791758283745 43692732083161987128376688640 True p = 97, a = 43, b = 29 144961326291866235642504921569750901198492185416469108828279272771359855892862 855042383483098104561223385608753374989274953102894307632201709383764463190146 9353450925785109440767160 True$


HTML5

<pre id="output0"></pre>
<label for="p0">p = </label>
<input id="p0" type="number" min="2" step="1" value="11">
<label for="a0">a = </label>
<input id="a0" type="number" step="1" value="10">
<label for="b0">b = </label>
<input id="b0" type="number" step="1" value="20">

<button id="run0">run</button>
<button id="clear0">clear</button>

<script src="sample5.js"></script>


JavaScript

let pre0 = document.querySelector('#output0'),
btn0 = document.querySelector('#run0'),
btn1 = document.querySelector('#clear0'),
input_p = document.querySelector('#p0'),
input_a = document.querySelector('#a0'),
input_b = document.querySelector('#b0'),
inputs = [input_p, input_a, input_b],
p = (x) => pre0.textContent += x + '\n',
range = (start, end, step=1) => {
let res = [];
for (let i = start; i < end; i += step) {
res.push(i);
}
return res;
};

let factorial = (n) => range(1, n + 1).reduce((x, y) => x * y, 1),
is_prime = (n) =>
range(2, Math.floor(Math.sqrt(n) + 1)).every((m) => n % m !== 0),
f = (p, a, b) => {
let m = ((a + b) ** p - (a ** p + b ** p)) % p;

return [m, m === 0];
};

let output = () => {
let p0 = parseInt(input_p.value, 10),
a0 = parseInt(input_a.value, 10),
b0 = parseInt(input_b.value, 10);

if (!is_prime(p0)) {
return;
}
p(f(p0, a0, b0));
};

inputs.forEach((input) => input.onchange = output);
btn0.onclick = output;
btn1.onclick = () => pre0.textContent = '';
output();