2018年3月30日金曜日

学習環境

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


  1. p - 1 - 1 m o d p p - a - a m o d p

    が成り立つので、

    p - 1 p - a - 1 a a ! m o d p

    よって、

    ( p - 1 a ) a ! - 1 α a ! m o d p

    また、問題の仮定より、

    a ! , p = 1

    ゆえに、

    ( p - 1 a ) - 1 α m o d p

    が成り立つ。

    (証明終)

コード(Emacs)

Python 3

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

for p in [randprime(2, 100) for _ in range(10)]:
    print(f'素数: {p}')
    for _ in range(2):
        a = random.randrange(p)
        l = combinatorial.numbers.nC(p - 1, a)
        r = (-1) ** a
        print(f'a = {a}: {(l - r) % p == 0}')

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

$ ./sample7.py
素数: 47
a = 1: True
a = 22: True
素数: 37
a = 32: True
a = 8: True
素数: 67
a = 30: True
a = 54: True
素数: 5
a = 4: True
a = 3: True
素数: 53
a = 34: True
a = 16: True
素数: 59
a = 22: True
a = 44: True
素数: 53
a = 52: True
a = 23: True
素数: 71
a = 66: True
a = 46: True
素数: 5
a = 0: True
a = 0: True
素数: 79
a = 26: True
a = 71: 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" min="0" step="1" value="5">

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

<script src="sample7.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'),
    inputs = [input_p, input_a],
    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),
    comb = (n, m) => factorial(n) / (factorial(n - m) * factorial(m)),
    is_prime = (n) =>
    range(2, Math.floor(Math.sqrt(n) + 1)).every((m) => n % m !== 0);

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

    if (!(is_prime(p0) && a0 <= p0 - 1)) {
        return;
    }
    
    let l = comb(p0 - 1, a0),
        r = (-1) ** a0;

    p((l - r) % p0 === 0);
};

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




















						

0 コメント:

コメントを投稿

関連コンテンツ