Q26.[PPC]Remainder theorem

#!/bin/bash

# 拡張ユークリッドのアルゴリズム
ext_gcd() {
    local a=$1
    local b=$2
    if (( b == 0 )); then
        echo "1 0"
        return
    fi

    local arr=($(ext_gcd $b $((a % b))))
    local x=${arr[0]}
    local y=${arr[1]}

    echo "$y $((x - (a / b) * y))"
}

# 各モジュラスと数値の定義
m1=1584891
a1=32134
m2=3438478
a2=193127

# 逆元を求める
arr1=($(ext_gcd $m1 $m2))
y1=${arr1[0]}
y2=${arr1[1]}
# 連立合同式の解を計算
x=$((a1 * y2 * m2 + a2 * y1 * m1))

# 2つのモジュラスの積でモジュロを取る
x=$((x % (m1 * m2)))

# 結果が負の場合、正の値に変換
if (( x < 0 )); then
    x=$(( x + m1 * m2 ))
fi

echo "x = $x"

# 連立合同式にxを代入して確認
result1=$(( x % m1 ))
result2=$(( x % m2 ))

echo "x mod m1 = $result1 (Expected: $a1)"
echo "x mod m2 = $result2 (Expected: $a2)"

if [[ $result1 -eq $a1 && $result2 -eq $a2 ]]; then
    echo "The solution is correct!"
else
    echo "The solution is incorrect."
fi

% bash gcd.bash
x = 35430270439
x mod m1 = 32134 (Expected: 32134)
x mod m2 = 193127 (Expected: 193127)
The solution is correct!