當前位置:菜譜大全網 - 減脂餐食譜 - 用相除法求最小公倍數

用相除法求最小公倍數

加1可以被2,3,4,5,6整除,所以它們的最小公倍數lcm(2,3,4,5,6)=60。

最小公倍數可以被2、3、4、5、6整除,最小公倍數的所有整數倍都滿足整除性質。讓

這樣的數字是60n-1,其中n是整數。

同時這個數可以被7整除,所以這個數也可以假設為7m,m是整數,同時滿足關系。

7m=60n-1,也就是60n-7m=1,因為60和7是質數。

所以我們用的是分階段的方法60 = 7 * 8+4,7 = 4 * 1+3,4 = 3 * 1+1。

提出1,1 = 4-3 * 1 =(60-7 * 8)+(60-7 * 8)* 1-7 =-17 * 7+2 * 60進行比較。

得到n=2,m=17,60n-7m=1成立。

當然,這只是解決方案之壹,更進壹步。

60n ≡ 1 (mod7)相當於60n-7m=1,顯而易見。

如果60n除以7的余數不是1,那麽60n-7m除以7的自然數不是1,這與60n-7m =1相矛盾。

對於同余公式60n≡1(mod7),n明顯滿足n=7k+q的結構,其中k為整數,q滿足60q≡1(mod7)。從最初的討論可知,q=2是同余公式的壹個特解。那麽n的所有解都是n,假設存在另壹個解T使得T也滿足60t≡1(mod7),則可以證明(t-n)≡0 (mod7),也就是說T也是7k+2(參考離散數學中的同余壹章)。

所以所有且只有7k+2個數滿足這個公式,也就是說。

60(7k+2)-1,其中k為整數,都滿足問題幹條件。當k取0時,最小數為119。