主に、強化学習

情報系の大学2年生が確率に関連したことを多めに書いてるブログ

数学との出会い 整数

定理1

P を 4 で割って1余る素数とすると P = x^2 + y^2(x,yは整数)の形に書ける \\ 
P が 4で割って3余る素数とすると、Pはその形にかけない.

命題

a,bの最大公約数をd とすると、dはax+by(x,yは整数)の形に書ける。

系1

 aを素数P で割れない整数とすると、ax+by=1となる整数x,yがある

系2

次の(1),(2)は同値

(1)P は素数 \\ (2) P \mid ab ならば、 P \mid a または、 P \mid b.
 (1) \Rightarrow (2)を示した.
 (2) \Rightarrow (1)の証明. (2)を仮定して、 (1)が成り立たないとする(背理法) \\
すると、P = xy , x \neq 1 , y \neq 1 (x >0 , y > 0とする) \\
となるx,yがある。このとき、
x < P , y < P なので、 P not \mid x かつ P not \mid y . \\
しかし P \mid xy なので、 (2)に反する.矛盾.

 ガウスの整数 \mathbb{z} [ i ]
 \hspace{10pt} i^2 = -1
 \mathbb{z} [ i ] = \left\{ a+bi \mid a,bは整数 \right\}

 \mathbb{z} [ i ] には \\
和 (a+bi)+(c+di) = a+c+(b+d)i \\
積 (a+bi)(c+di) = (ac-bd)(ad+bc)i
が定義される.
 \alpha = a+bi \in  \mathbb{z} [ i ] の共役 \bar{\alpha} を a-biと定める
 また、 \alpha = a+bi の絶対値 \mid \alpha \mid を \mid \alpha \mid = \alpha \bar{\alpha}  = \bar{\alpha} \alpha = a^2 + b^2 と定める.

 \mid \alpha \mid \geq 0 であり、 \mid \alpha \mid = 0 \Leftrightarrow \alpha = 0 + 0i = 0
 である. \mid \alpha \mid は整数 これも大事

命題2  \alpha, \beta \in \mathbb{z} [i ]とすると、

(1) \bar{\alpha \beta } = \bar{\alpha} \cdot \bar{\beta}
(2) \mid \alpha \beta \mid = \mid \alpha \mid \cdot \mid \beta \mid
が成り立つ。

レポート問題1

この命題2 を証明せよ
 \mathbb{z} [i ] の素数は、 \pm 1, \pm i と自分自身以外の約数を持たない数

 1 = (i)(-i)なので、 \pm i はどんな数も割りきってしまう\\
x^2 +y^2 = (x+yi)(x-yi)と因数分解する. \\
定理1を次のように言い換える.

定理1'

4で割って1余る素数 P は、\mathbb{z} [ i ]において、 P = \alpha \bar{\alpha}と因数分解する
4で割って3余る素数は \mathbb{z} [ i ] においても素数のままである

つまり、定理1は、素数が \mathbb{z} [ i]において 分解する様子を \\
表しているものと見られる

補題'  \alpha , \beta \in \mathbb{z} [ i ] とすると

 \hspace{20pt} \alpha = q \beta + \gamma \hspace{2pt} q,\gamma \in \mathbb{z} [ i ]

 (0 \leq ) \mid \gamma \mid <  \mid \beta \mid
 \hspace{5pt} となる q, \gamma が存在する

(証明は難しくない)

  • > やろうな

命題'

 \alpha, \beta \in \mathbb{z} [ i ] 、 \alpha を \alpha, \beta の最大公約数 \\
(絶対値が最大の公約数)とすると
 \alpha = \alpha x + \beta y となる. x, y \in \mathbb{z} [i ]が存在する

証明は、先週の命題と同様にできる

系1'

 P \in \mathbb{z} [ i ] を素数、 \alpha \in \mathbb{z} [ i ] を \\
Pで割り切れないとすると, \\
Px + \alpha y = 1となる x,y \in \mathbb{z} [ i ]がある

系2'

次の(1),(2)は同値

(1) P \in \mathbb{z} [ i ] は素数 \\
(2) P \mid \alpha \beta ならば、 P \mid \alpha または、 P \mid \beta
これらの証明も先週と同様

定理1' の証明に必要な事実
Pを4で割って 1余る素数とすると、
Pは、 n^2 + 1 という形の整数の約数
(普通の整数の範囲で)
これを認めて定理1' を証明する.
Pを4で割って1余る素数とする.
 P \mid n^2 + 1 =(n+i)(n-i)
 P not \mid n+i, P not \mid n-i である
 \mathbb{z} [ i ] において P \mid a+bi ならば \\
P \mid a , P \mid b である

 系2' により P は \mathbb{z} [ i ] の素数 ではない.
 よって P = \alpha \beta \hspace{10pt} \alpha \neq \pm 1, \pm i \hspace{10pt} \beta \neq \pm 1, \pm i

 と \mathbb{z} [ i ]において分解する.  \beta = \bar{\alpha}ならよい。

 \mid P \mid = P \times \bar{P} = P^2

 一方 \mid P \mid = P \times \bar{P} = ( \alpha \beta ) \bar{ ( \alpha \beta ) }
 = \alpha \beta \bar{\alpha} \bar{\beta} = \alpha \bar{\alpha} \beta \bar{\beta} = \mid \alpha \mid \mid \beta \mid
命題212)

 \mid \alpha \mid , \mid \beta \mid  は、普通の整数で \\
P^2 = \mid \alpha \mid \mid \beta \mid  . あり得るのは \\

 1) \mid \alpha \mid = P^2 , \hspace{20pt} \mid \beta \mid = 1
 2) \mid \alpha \mid = P , \hspace{20pt} \mid \beta \mid = P
 3) \mid \alpha \mid = 1 , \hspace{20pt} \mid \beta \mid = P^2

 \mid \beta \mid = 1 とすると、 \beta = \pm 1, \pm i となる
 \mid \alpha \mid = 1 とすると、 \alpha = \pm 1, \pm i となる

 (補足: a^2 + b^2 = 1となるのは、 (a,b) = (1,0),(-1,0),(0,1),(0,-1)のみ

これらは\alpha , \beta の条件に反する \\
よって 2) が成り立ち、 P = \mid \alpha \mid = \alpha \bar{\alpha} \\
\alpha = x+yi とすれば、 P = x^2 + y^2

レポート問題 2

100以下 の素数で 4で割りきって1余る
もの (15,133, 17 , 29, ... )
を、 x^2 + y^2 の形で表わせ

In [7]: def is_prime(n):
   ...:     i = 2
   ...:     while i*i <= n:
   ...:         if n%i == 0:
   ...:             return False
   ...:         i += 1
   ...:     return True
   ...:
In [10]: [i for i in range(4,100) if (i%4==1)&is_prime(i)]
Out[10]: [5, 13, 17, 29, 37, 41, 53, 61, 73, 89, 97]

In [19]: for i in range(1,10):
    print(i,s(97 - i**2))
   ....:
1 9.797958971132712
2 9.643650760992955
3 9.38083151964686
4 9.0
5 8.48528137423857
6 7.810249675906654
7 6.928203230275509
8 5.744562646538029
9 4.0