どうも、木村（@kimu3_slime）です。
今回は、Juliaであまりのある割り算、最大公約数、modの計算をする方法を紹介します。
あまりのある割り算
「divrem(a,b)」で、\(a\)を\(b\)で割った商とあまり（整数の除法）が計算できます。
1 2 3 | divrem(7,3) div(7,3) rem(7,3) |
1 2 3 | (2, 1) 2 1 |
1 | divrem(7,18) |
1 | (0,7) |
割る数が大きいと、商が0であまりがそのまま返ってきます。
1 | divrem(-7,-4) |
1 | (1, -3) |
あまりは必ずしも正とはならない仕様になっています。あまりは割る数の符号と同じで、絶対値が割られる数より小さいものです。
この例では、\(-7\)が負の数なので、それに合わせてあまりが\(-3\)になっています。いずれにせよ、整数の割り算とは、次の等式が成り立つということです。
1 | -7 == -4 *1 +(-3) |
1 | true |
最大公約数
「gcd(a,b)」で、整数\(a,b\)の最大公約数（greatest common divisor）が求められます。
1 2 3 | gcd(10,24) gcd(3,14) gcd(2016,216) |
1 2 3 | 2 1 72 |
「lcm(a,b)」で、最小公倍数が求められます。
1 | lcm(10,24) |
1 | 120 |
「gcdx(a,b)」という関数を使うことで、1次不定方程式（ディオファントス方程式）
\[ \begin{aligned}ax+by=c\end{aligned} \]
の特殊解を求めることができます。
例として、\(2x +3y =20\)の特殊解を求めてみましょう。\(a=2, b=3\)です。
1 | gcdx(2, 3) |
1 | (1, -1, 1) |
この3つの数字は、\(c=1 ,x=-1,y=1\)が特殊解であることを意味しています。
1 2 | c,x,y = gcdx(2, 3) 2 *x +3*y == c |
1 | true |
両辺を20倍すれば、もとの方程式\(2x +3y =20\)の特殊解が、\(x=-20,y=20\)であることがわかりました。（一般解は \(x= 3k+7\),\(y=-2k+2\)）
もうひとつの例として、\(2016x +216 y =14400\)を解いてみましょう。
1 2 3 | gcdx(2016, 216) c,x,y = gcdx(2016, 216) 2016 *x + 216* y == c |
1 2 | (72, 1, -9) true |
得られた等式において、両辺を\(14400/ 72 =200\)倍すれば、\(x= 200\),\(y=-1800\)が解であるとわかりました。
整数の合同 mod
整数の合同 mod \(x\equiv y\, (\mathrm{mod}\, n)\)における\(y\)は、「mod(x,n)」で求められます。
1 | mod(1512,11) |
1 | 5 |
この結果は、\(1512\equiv 5\, (\mathrm{mod}\, 11)\)、\(1512\)を\(11\)で割ったあまりが\(5\)であることを意味しています。\(0\)に合同でないので、\(1512\)は\(11\)で割り切れません。
\(2021^{20}\)は\(7\)を法として何に等しいか計算してみましょう。「BigInt型」を使わないと、べき乗の計算がオーバーフローしてしまいます。
1 | mod(BigInt(2021)^(20),7) |
1 | 4 |
べき乗の計算に特化した「powermod(a,k,n)」という関数があります。
1 2 | @time mod(BigInt(2021)^(20),7) @time powermod(2021, 20, 7) |
1 2 3 4 | 0.000007 seconds (13 allocations: 288 bytes) 4 0.000002 seconds 4 |
特化した関数の方が、計算が速いですね。
\(2021^{20}\)を\(10\)で割ったあまりは何か、という問題も簡単に解けます。
1 | powermod(2021, 20, 10) |
1 | 1 |
以上、Juliaであまりのある割り算、最大公約数、modの計算をする方法を紹介してきました。
シンプルな電卓ではできないあまりのある割り算からみの計算が、手計算より圧倒的にできるので便利ですね。
木村すらいむ（@kimu3_slime）でした。ではでは。
コロナ社 (2020-03-26T00:00:01Z)
￥7,353 (コレクター商品)
