Juliaであまりのある割り算、最大公約数、modの計算をする方法

どうも、木村(@kimu3_slime)です。

今回は、Juliaであまりのある割り算、最大公約数、modの計算をする方法を紹介します。

 



あまりのある割り算

「divrem(a,b)」で、\(a\)を\(b\)で割った商とあまり(整数の除法)が計算できます。

 

割る数が大きいと、商が0であまりがそのまま返ってきます。

 

あまりは必ずしも正とはならない仕様になっています。あまりは割る数の符号と同じで、絶対値が割られる数より小さいものです

この例では、\(-7\)が負の数なので、それに合わせてあまりが\(-3\)になっています。いずれにせよ、整数の割り算とは、次の等式が成り立つということです。

 

最大公約数

「gcd(a,b)」で、整数\(a,b\)の最大公約数(greatest common divisor)が求められます。

 

「lcm(a,b)」で、最小公倍数が求められます。

 

「gcdx(a,b)」という関数を使うことで、1次不定方程式(ディオファントス方程式)

\[ \begin{aligned}ax+by=c\end{aligned} \]

の特殊解を求めることができます。

例として、\(2x +3y =20\)の特殊解を求めてみましょう。\(a=2, b=3\)です。

この3つの数字は、\(c=1 ,x=-1,y=1\)が特殊解であることを意味しています。

両辺を20倍すれば、もとの方程式\(2x +3y =20\)の特殊解が、\(x=-20,y=20\)であることがわかりました。(一般解は \(x= 3k+7\),\(y=-2k+2\))

 

もうひとつの例として、\(2016x +216 y =14400\)を解いてみましょう。

得られた等式において、両辺を\(14400/ 72 =200\)倍すれば、\(x= 200\),\(y=-1800\)が解であるとわかりました。

 

整数の合同 mod

整数の合同 mod \(x\equiv y\, (\mathrm{mod}\, n)\)における\(y\)は、「mod(x,n)」で求められます。

この結果は、\(1512\equiv 5\, (\mathrm{mod}\, 11)\)、\(1512\)を\(11\)で割ったあまりが\(5\)であることを意味しています。\(0\)に合同でないので、\(1512\)は\(11\)で割り切れません。

 

\(2021^{20}\)は\(7\)を法として何に等しいか計算してみましょう。「BigInt型」を使わないと、べき乗の計算がオーバーフローしてしまいます。

 

べき乗の計算に特化した「powermod(a,k,n)」という関数があります。

特化した関数の方が、計算が速いですね。

 

\(2021^{20}\)を\(10\)で割ったあまりは何か、という問題も簡単に解けます。

 

以上、Juliaであまりのある割り算、最大公約数、modの計算をする方法を紹介してきました。

シンプルな電卓ではできないあまりのある割り算からみの計算が、手計算より圧倒的にできるので便利ですね。

木村すらいむ(@kimu3_slime)でした。ではでは。

 

1から始める Juliaプログラミング
進藤 裕之(著), 佐藤 建太(著)
コロナ社 (2020-03-26T00:00:01Z)
5つ星のうち4.5
¥7,353 (コレクター商品)

 

こちらもおすすめ

整数の除法、割り切れる・約数b|a、最大公約数gcdとは?

1次不定方程式の整数解と、互除法による解き方、解ける条件

倍数同士の和は同じ倍数となること、整数の合同modとは

合同式の性質を使った整数の余りの計算方法

同値関係、2項関係とは? 整数の合同(mod)を例に