# 最大公約數與最小公倍數 ## 求最大公約數 ```C++ // 歐幾里得算法 int gcf(int a, int b){ return !b?a:gcf(b,a%b); } ``` ## 求最小公倍數 最小公倍數=數1*數2/最大公約數 ## 二元一次方程整數解 方程 $$ax+by=c(a,b,c ?\in Z,\ a,b \neq 0)$$ 存在整數解的充要條件是 $$c\%gcf(a,b)=0$$ . 設 $$(x_0,y_0)$$ 是方程 $$ax+by=gcf(a,b),(a,b ?\in Z,\ ?a,b\neq 0)$$ 的一組整數解，則 $$(\frac{cx_0}{gcf}, \frac{cy_0}{gcf})$$ 為方程 $$ax+by=c$$ 的一組整數解。 設 $$(x^*,y^*)$$?是方程 $$ax+by=c(a,b \neq 0)$$ 的一組整數解，則方程的通解為 $$(x^*+\frac{b}{gcf}K,y^* -\frac{a}{gcf}K)$$? ```C++ // 求解方程 ax+by=gcf(a,b) ，最后函數返回 gcf int exgcf(int a, int b, int& x, int& y){ if(b==0){ x=1; y=0; return a; } int g=exgcf(a,a%b,x,y); int tmp=x; x=y; y=tmp-a/b*y; return g; } // 求解方程 ax+by=c int solve(int a, int b, int c, int& x, int& y){ int g=exgcf(a,b,x,y); if(c%gcf!=0) return 0; // 無整數解 x=c*x/gcf; y=c*y/gcf; return 1; } ``` ## 同余式求解 同余式 $$ax \equiv c\pmod{m} \ (a,c,m\in Z,\ m\geq 1)$$ 等價于 $$(ax-c)\%m=0$$ ，即存在整數 y ，使得 $$ax+my=c$$ 。 - 若 $$c\%gcf(a,m) \neq 0$$ ，則同余式方程 $$ax \equiv c\pmod{m} \ (a,c,m\in Z,\ m\geq 1)$$ 無解。 - 若 $$c\%gcf(a,m) = 0$$ ，則同余式方程 $$ax \equiv c\pmod{m} \ (a,c,m\in Z,\ m\geq 1)$$ 恰有 $$gcf(a,m)$$ 個模 $$m$$ 意義下不同的解，解為 $$x=x^*+\frac{m}{gcf(a,m)}K$$ ，其中 $$K=0,1,\cdots ,gcf(a,m)-1$$ ，$$x$$ 是方程 $$ax+my=c$$ 的一個解。 ## 乘法逆元求解 已知 $$ab\%m=(a\%m)(b\%m)\%m$$?，則 $$a/b\%m=?$$?，其中 $$(a\%b=0)$$?.這里需要用到逆元。? 設 $$a,b,m \in Z,\ m>1$$ 且有 $$ab \equiv 1 \pmod{m}$$ ，則稱 $$a,b$$ 互為乘法逆元。求解逆元即求解同余式方程 $$ax \equiv 1\pmod{m} \ (a,c,m\in Z,\ m>1)$$ ，且在 $$(0,m)$$ 內有唯一解，實際使用中一般稱方程在 $$(0,m)$$ 內的解為 $$a$$ 的逆元。 由此 - 若 $$gcf(a,m) \neq 1$$ ，則 $$a$$ 不存在模 $$m$$ 的逆元。 - 若 $$gcf(a,m) =1$$ ，則存在逆元如下 ```c++ int inverse(int a, int m){ int x, y; int g=exgcf(a,m,x,y); return (x%m+m)%m; } ``` 費馬小定理：設 $$m$$ 是素數，$$a$$ 是任意整數且 $$a \not\equiv 0 \pmod{m}$$ ，則 $$a^{m-1} \equiv 1 \pmod{m}$$ 當 $$gcf(a,m) =1$$ 時，逆元等于 $$a^{m-2}\%m$$? ## ChangeLog > 2018.09.04 初稿