> For the complete documentation index, see [llms.txt](https://kurohasu.gitbook.io/fsharpabout/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://kurohasu.gitbook.io/fsharpabout/examples/orijinarunoraiburari.md).

# オリジナルの数学ライブラリ

### 最大公約数を求める関数GCD()

最大公約数はすべての公約数を約数にもつ公約数の事です。\
例えば12と18の場合、最大公約数は6となります。\
これを実装するとGCD(12,18)=6となるようにプログラムを作成する必要があります

$$
GCD(12,18)=6
$$

数字を１から試すのもありですが、「ユークリッドの互除法」というアルゴリズムがあります\
ユークリッドの互除法では、割られる数と２つの数字の剰余を割った時の余った数を使用して最大公約数を出します。12と18を例に挙げると以下のような挙動をします

18/12=1..6\
12/6=2..0

2回目の計算時に余りが0になりました。その時の割った数字(=6)が最大公約数であることが分かります

#### 実装

F#には再帰関数がサポートされているためこれを活用していきます\
もし最大公約数が1の場合はそのまま1を返すようにします

```fsharp
let rec GCD(x,y)=
    match y with
        |1->1
        |0->x
        |_->GCD(y,x%y)
```

### 1次不定方程式を解く関数extend\_euchlid()

2変数(a,b)の最大公約数が分かっている場合、任意の整数gを以下のような形で表現することが可能であり、\
\=gとなるような整数の組み合わせ(a,b)が必ず存在することが知られています

$$
ax+by=g
$$

例としてextend\_euchlid(18,7)を実行すると(2,-5)が帰ってきます\
実装においてはax+by=1となる(a,b)を見つけるため、割った余りが1の時の(a,b)の値が答えとなります

$$
a=18,b=7\\
18/7=2...4\Longrightarrow4=a-2b\\
7/4=1...3\Longrightarrow3=-a+3b\\
4/3=1..1\Longrightarrow1=2a-5b\\
\therefore(a,b)=(2,-5)
$$

{% hint style="success" %}
これだけ見ると「何に使うんだ？」と感じるかもしれませんが、特定の値を掛けて割った余りが1になるような xであるモジュラ逆数の探索に役立ちます。モジュラ逆数はRSA暗号やシミュレーション等において使用されています。
{% endhint %}

#### 実装

```fsharp
let rec extended_euchlid(a:int,b:int)=
    if b=0 then
        (1,0)
    else
        let (xd,yd)=extended_euchlid(b,a%b)
        (yd,xd-(a/b*yd))
```