2018年3月27日火曜日

学習環境

数学読本〈6〉線形写像・1次変換/数論へのプレリュード/集合論へのプレリュード/εとδ/落ち穂拾い など(松坂 和夫(著)、岩波書店)の第23章(数学の中の女王 - 数論へのプレリュード)、23.2(合同式)、合同式の除法、問5.を取り組んでみる。


  1. a + b p = k = 0 p ( p k ) a k b p - k = ( p 0 ) a 0 b p - 0 + k = 1 p - 1 ( p k ) a k b p - k + ( p p ) a p b 0 = b p + k = 1 p - 1 ( p k ) a k b p - k + a p

    よって、

    a + b p - a p + b p = k = 1 p - 1 ( p k ) a k b p - k

    また、前問4より、

    p | ( p k ) k = 1 , , p - 1

    ゆえに、

    a + b p a p + b p m o d p

    が成り立つ。

    (証明終)

コード(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()

入出力結果(Terminal, Jupyter(IPython))

$ ./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();






















						

0 コメント:

コメントを投稿

関連コンテンツ