請教同餘原理的證明

1. 設c, d為正整數
x=cb+p
y=db+q
x+y=cb+p+db+q=(c+d)b+(p+q)
因為(x+y)除以b之餘數為(p+q),
所以(x+y)除以b之餘數=(p+q)除以b之餘數
證明:
如果(p+q)<b,
(x+y)除以b之餘數=p+q
(p+q)除以b之餘數=p+q
如果(p+q)≧b,
設h為正整數, a為(p+q)除以b之餘數, 使p+q=hb+a
x+y=(c+d)b+(p+q)=(c+d)b+(hb+a)=(c+d+h)b+a
(x+y)除以b之餘數=a
(p+q)除以b之餘數=a
綜合(p+q)的所有可能性, (x+y)除以b之餘數=(p+q)除以b之餘數.

2. 跟第1條問題同樣道理
(留給你做好了)

3. xy
=(cb+p)(db+q)
=cdb^2 + cqb + dpb + pq
=cdb^2 + (cq+dp)b + pq
=(cdb+cq+dp)b+pq
=eb+pq
(e是正整數)
因為(xy)除以b之餘數為(pq),
所以(xy)除以b之餘數=(pq)除以b之餘數
證明跟第1問題的證明同樣道理

4. x^n
=(cb+p)^n
=(nC0)(cb)^n + (nC1)(p)(cb)^(n-1) + (nC2)(p^2)(cb)^(n-2)
+ ... + (nCn-1)[p^(n-1)](cb) + (nCn)(p^n)
(以上用了binomial theorem / 二項式定理)
= b {(nC0)(c^n)[b^(n-1)] + (nC1)(p)[c^(n-1)][b^(n-2)] + (nC2)(p^2)[c^(n-2)][b^(n-3)]
+ ... + (nCn-1)[p^(n-1)](c) } + (p^n)
=bf+(p^n)
=fb+(p^n)
(f是正整數)
因為(x^n)除以b之餘數(p^n),
所以(x^n)除以b之餘數=(p^n)除以b之餘數
證明跟第1問題的證明同樣道理

題目是不小心打錯了吧?
都應該是"???除以b之餘數=(??)"，沒有後面的"除以b之餘數"吧?

設 x=bm+p, y=bn+q, m,n 為正整數
1. (x+y) = (bm+p)+(bn+q) = b(m+n)+(p+q), 故(x+y)/b 之餘數為(p+q)

2. (x-y) = (bm+p)-(bn+q) = b(m-n)+(p-q), 故(x-y)/b 之餘數為(p-q)

3.(xy) = (bm+p)(bn+q) = (b²mn+bmq+bnp+pq) = b(bmn+mq+np)+pq
故(xy)/b 之餘數為(pq)

4.
(x^n)
= (bm+p)^n
= [(bm)^n+(nC1)((bm)^(n-1))p+(nC2)(bm)^(n-2)p²+...+(nC(n-1))*bm*p^(n-1)+p^n]
= Z +p^n
留意：
Z=[(bm)^n+(nC1)((bm)^(n-1))p+(nC2)(bm)^(n-2)p²+...+(nC(n-1))*bm*p^(n-1)]
可被b整除, 即 Z=bz , z為正整數

故(x^n)
= bz + p^n
即(x^n)/b 之餘數為 p^n
(可使用Σ (summation sign) 來表達(bm+p)^n 的展開式，答案會較簡潔。)

設正整數x、y除以b之餘數分別為p、q
所以x=mb+p, y=nb+q, 而且m,n為整數

(x+y)/b=(mb+p+nb+q)/b=m+n+(p+q)/b

(x-y)/b=(mb+p-nb-q)/b=m-n+(p-q)/b

xy/b=(mb+p)(nb+q)/b=(nmb^2+mbq+nbp+pq)/b=nmb+mq+nq+pq/b

x^n/b=(mb+p)^n/b
=[mb^n+pn*mb^(n-1)+.......+n*mb*p^(n-1)+p^n]/b
=[mb^(n-1)+pn*mb^(n-2)+..........+nm*p^(n-1)]+p^n/b

令x=bm+p，y=bn+q1. x+y=bm+p+bn+q=b(m+n)+(p+q)所以x+y≡p+q (≡表示同餘之意) 2. x-y=bm+p-bn-q=b(m-n)+(p-q)所以x-y≡p-q 3. xy=(bm+p)(bn+q)=b^2mn+bmq+pbn+pq=b(bmn+mq+pn)+pq所以xy≡pq 4. 利用3.，當x=y，3.變成 xx≡pp，即x^2≡p^2再乘以一次x可得 x^3≡p^3依此類推乘下去得 x^n≡p^n