整数に関するメモ

非常に苦手。ブラックボックスは良くないので雑に勉強。内容は無益です。

合同式

1. のとき(cとmが互いに素)
   
2. のとき
   

特に

[証明]


不定方程式に変形ができて

1. のとき(cとmが互いに素)
   左辺は整数よりは整数であるから
   
2. のとき
   と変形できて上の1.に帰着される。
   

モジュラ逆数 が存在する必要十分条件

aとmが互いに素であること。
このときならばはのモジュラ逆数である。

ユークリッドの互除法

２つの自然数a, bの最大公約数を求めるアルゴリズム。
とするととかける。
このとき



よって余りであるrはaとbの最大公約数Gを約数とするので, bとrについて同様にして余りとなるまで計算を行えばよい。

ex.1 : 1071と1029の最大公約数を求める。
として

このとき42はgcd(a, b)を約数とする。


よって42と21の最大公約数は21である。
21が1071と1029の最大公約数である。

拡張ユークリッドの互除法

不定方程式を満たす整数解(x, y)が存在する。
また, 整数解(a, b)は計算できる。←”拡張”部分

ex.2 : 2元1次不定方程式 の一般解を求める
↓の定理より↑の不定方程式が解を持つ-5がgcd(27, 11)の倍数であるから, 解を持つと仮定すると27a - 11b = gcd(27, 11)の両辺を-5/gcd(27, 11)倍してやれば解が求まる。よってまずgcd(27, 11)と27x - 11y = gcd(27, 11)の解を求める。ユークリッドの互除法→拡張ユークリッドの互除法をやる。



よってgcd(27, 11) = 1がわかる。上の式を変形して




↑をに引いて


x - 10とy - 25がそれぞれ11と25を約数に持つことがわかり, 一般解は

定理1: 不定方程式が整数解(x, y)を持つcがgcd(a, b)の倍数である。
[十分条件の証明]
整数解(x, y)が存在すると仮定すると
よりcはGの倍数である。
また, aとbが互いに素である任意の整数がax + byの形で表せる=必要条件

定理2: 不定方程式が整数解(x, y)を持つaとbが互いに素である。
[証明]定理1よりc = 1がgcd(a, b)の倍数であれば良い。すなわちgcd(a, b) = 1であり, aとbが互いに素であれば良い。

1次合同式

1. のとき(cとmが互いに素)
   1つの解をもつ。
2. のとき
   Gがbの約数であるときのみd個の解をもつ。
   (1次合同式は不定方程式を解くことと同値である。)

中国余剰定理(CRT: Chinese Remainder Therorem)

整数が次の連立合同式を満たすとする。

がどの2つも互いに素であるならば, は の範囲に一意に存在する。よって, の一般解は次のように表される。

なお, は で計算できる。→(https://atcoder.github.io/ac-library/production/document_ja/math.html)

中国余剰定理の一般化(法が互いに素でない場合への拡張)

整数が次の連立合同式を満たすとする。

上の連立合同式の一般解が存在する必要十分条件は
「任意のiとjに対してが成り立つ」

詳しく→(https://manabitimes.jp/math/838)

フェルマーの小定理

素数について整数がの倍数でなければ