ASP 討論版

	昌爸工作坊論壇
\|─	有關餘數問題之研討


回覆	搜尋	返回	管理

作者	標題: 有關餘數問題之研討
yes	發表於: 2005/10/2 下午 11:05:40 設n為正整數，求以下各題之最小值? 1.若n以5除餘1，以7除餘2，以9除餘3 2.若n以123除餘1，以321除餘2 3.若n以1234除餘1，以4321除餘2 4.若n以1234除餘3，以4321除餘7 5.若n以13除餘1，以35除餘2，以57除餘3 其中第1題希望各位先進能提供更多不同的解法， (我目前僅用三種解法)
小昭	回覆於: 2025/2/23 下午 06:51:53 第五題由於13,35,57為等差級數(公差R=22) 及1,2,3為等差級數(公差r=1) 公差比R/r=22 ____ n=1 (mod 13) n=2 (mod 35) n=3 (mod 57) ____ 22n=22=9 (mod 13) 22n=44=9 (mod 35) 22n=66=9 (mod 57) ____ 設22n=133557k+9 22n=13(-9)(-9)k+9 (mod 22) 22n=1381k+9 (mod 22) 22n=13(-7)k+9 (mod 22) 22n=-91k+9 (mod 22) 22n=-3k+9 (mod 22) 22n-3(k-3) (mod 22) 當k=3時,則n為整數 22n=1335573+9 n=(133557+9)/22 n=3537
小昭	回覆於: 2025/2/23 下午 06:53:05 更正 n=(133557*3+9)/22 n=3537
有感而發	回覆於: 2025/2/24 下午 03:11:38 20年前的台灣學生的數學能力很強ㄡ.
小米	回覆於: 2005/10/2 下午 11:10:56 n=1(mod5)=2(mod7)=3(mod9) 2n=2(mod5)=4(mod7)=6(mod9)=-3(mod5)=-3(md7)=-3(mod9) 2n=-3(mod315) 2n+3=315k k=1, n=156
小米	回覆於: 2005/10/2 下午 11:12:11 中國剩餘定理也可
小米	回覆於: 2005/10/2 下午 11:14:09 輾轉相除也可採用，並留給其他人處理
小米	回覆於: 2005/10/2 下午 11:17:59 2.若n以123除餘1，以321除餘2 n=123a+1=321b+2，123a-321b=1，但(123,321)=3，所以無解
yes	回覆於: 2005/10/2 下午 11:29:12 除數小通常較少用輾轉相除法，第3、4、5題倒可用之
yes	回覆於: 2005/10/2 下午 11:42:37 請教小米若第1題改為”若n以5除餘1，以7除餘2，以9除餘4” 則您提供的第1個解法如何解呢?
二箭東去	回覆於: 2005/10/2 下午 11:44:13 2.無整數解 3.n=3996927 4.n=5323479 5.n=3537
小米	回覆於: 2005/10/2 下午 11:46:13 n=1(mod13)=2(mod35)=3(mod57) 設n=a+b+c，且a=1(mod13)=0mod(1995)，b=2(mod35)=0mod(741)，c=3(mod57)=0 (mod455) a=1995P，當P=11，a=21945 b=741Q，當Q=12，b=8892 c=455R，當R=54，c=24570 n=21945+8892+24570+25935N=3537+25935K n=3537
yes	回覆於: 2005/10/2 下午 11:48:08 二箭東去答案沒錯,可否提供解法供參考嗎?
yes	回覆於: 2005/10/2 下午 11:56:05 小米第5題即利用中國剩餘定理來解
yes	回覆於: 2005/10/3 上午 12:31:13 我常使用第1題的三個解法為解1：設n=[5,7,9]t+[7,9]a+9b+3 n=2b+3=2 (mod 7) 取b=3 ,則n=315t+63a+30 n=3a=1 (mod 5) 取a=2 所以n=315t+156 解2：設n=5a+1=7b+2=9c+3 則a=(9c+2)/5=2c+(-c+2)/5 , 取c=2,7,12,17,… b=(9c+1)/7=c+(2c+1)/7 , 取c=3,10,17,… 則當c=17 時 ,n=156為最小值解3：利用中國剩餘定理 126=(79)2=1 (mod 5 ) 225=(59)5=1 (mod 7 ) 280=(57)8=1 (mod 9 ) 所以2252=2 (mod 7 ) ,2803=3 (mod 9 ) 所以n=[5,7,9]t+126+2252+2803=315t+1416 取t=-4時,n=156為最小值
yes	回覆於: 2005/10/9 上午 10:07:20 第3題設n=1234a+1=4321b+2, 則1234a-4321b=1 令c=1234,d=4321, 利用輾轉相除法可求得 -1082c+309d=1,即-10821234+3094321=1 所以a=-1082, b=-309為1234a-4321b=1的一組整數解則a=-1082+4321t, b=-309+1234t 為一般解(想想為什麼?) 取t=1, 則a=3239, 此時n=12343239+1=3996927即為所求第4題設n=1234a+3=4321b+7, 則1234a-4321b=4 承上題，利用輾轉相除法得-10821234+3094321=1, 兩邊同乘以4 , 則-43281234+12364321=4 所以 a=-4328, b=-1236為1234a-4321b=4的一組解則a=-4328+4321t, b=-1236+1234t 為一般解取t=2, 則a=4314, n=12344314+3=5323479即為所求