1. 整數r>s>0，(r, s)=1，2?r+s，x=r^2-s^2, y=2rs, z=r^2+s^2，求證(x, y)=1，(y, z)=1
?證明：由2?r+s（r與s必一奇一偶）知2?r-s，故2?r^2-s^2，以及2?(r+s)(r+s)。又1=(r, s)=(r+s, r)=(r+s, s)=(r+s, rs)。同理得1=(r, s)=(r-s, rs)，故1=((r+s)(r-s), rs)=(r^2-s^2, rs)，又1=(2, r^2-s^2)，故(r^2-s^2, 2rs)=1，即(x, y)=1。?(y, z)=(2rs, r^2+s^2)=(2rs, r^2+s^2+2rs)=(2rs, (r+s)(r+s))=(rs, (r+s)(r+s))=(rs, r+s)=(r, r+s)=(r, s)=1
?注：用最大公約數定義、整除性質、反證法，也可以得出(x, y)=1，(y, z)=1。本法則直接從最大公約數定理推導
2. u^2+3v^2=2p不可能成立，u、v為整數，p為奇素數
證明：u^2+3v^2=2p => u^2+v^2=2(p-v^2) => ?2|u^2+v^2=(u+v)^2-2uv => 2|(u+v)^2 => 2|u+v。得出這個中間結論，再由它可得4|2(u+v)|2v(u+v)=2v^2+2uv，以及4|(u+v)^2=u^2+v^2+2uv，故得4|u^2+3v^2+4uv，繼得4|u^2+3v^2=2p，即2|p，所以矛盾，證畢
?3. 若四個正整數y1*x2=y2*x1，(x1,y1)=(x2,y2)=1，則x1=x2，y1=y2
?證明：由y1*x2=y2*x1可得x1|y1*x2，又因(x1,y1)=1，故x1|x2；另得x2|y2*x1，又因(x2,y2)=1，故x2|x1；終得x1=x2，y1=y2
4. 假設2?z，z^3=x^2+3y^2有解且滿足(x, y)=1，其通解形式為x=a^3-9ab^2，y=3a^2b-3b^2，a、b滿足z=a^2+3b^2，求證(-3/p)=1，p是z的任一素因子；(a, 3b)=1
證明：先論證中間結論3?z，p>3且(p, xy)=1。若3|z，則3|x^2+3y^2=>3|x^2=>3|x=>9|x^2，另有9|x^2+3y^2=>9|3y^2=>3|y^2=>3|y，這與(x, y)=1矛盾，故3?z。又2?z，得p>3，由此若p|x，則p|3y^2得p|y，或若p|y，則p|x^2得p|x，都與(x, y)=1矛盾，故(p, xy)=1。
再論證勒讓德符號(-3/p)=1。由以上中間結論得等價形式x^2+3y^2=(Z^3p^2)p，及p?x^2、p?y^2，推得1=(x^2/p)=(-3y^2/p)=(-3/p)。
最后論證(a, 3b)=1。假設2|z，則2|a^2+b^2=(a+b)^2-2ab或(a-b)^2+2ab =>2|a+b, 2|a-b。因題設是2?z，故2?a+b, 2?a-b，由此推得2?a^2-b^2, 4?a^2-b^2，進而8?a^2-b^2，即(8, a^2-b^2)=1。由1=(x, y)=(a^3-9ab^2, 3a^2b-3b^2)=(a(a^2-9b^2), 3b(a^2-b^2))。又(a^2-9b^2, a^2-b^2)=(8b^2, a^2-b^2)=(b^2, b^2-a^2)=(b^2, a^2)=(a, b)^2，于是令a^2-9b^2=(a, b)^2*A, a^2-b^2=(a, b)^2*B，則得1=(x, y)=(a, b)^2*(aA, 3bB)，故(a, 3b)=1
5. 已知2?u+w，3?u，(u, w)=1，求證(2u, u^2+3w^2)=1
證明：2?u+w=>2?u^2+w^2=>2?u^2+3w^2，即(2, u^2+3w^2)=1。
由3?u，(u, w)=1得(u, 3w)=(u, 3w^2)=(u, u^2+3w^2)=1。
綜上兩式結果得(2u, u^2+3w^2)=1
6. 已知(3v, w)=1，2?3v+w，求證(18v, 3v^2+w^2)=1
證明：(3v, w)=1=>(3v, w^2)=(3v, 3v^2+w^2)=1。
(3v, w)=1=>(3, w)=1=>(3, w^2)=(3, 3v^2+w^2)=1。2?3v+w=>2?v+w=>2?v^2+w^2=>2?3v^2+w^2，即(2, 3v^2+w^2)=1。
綜上三式結果得(18v, 3v^2+w^2)=1
###############################
從1、5和6問題的證明過程可得，如果一個數由兩個或多個因子相乘，那么求證是否互素可以逐一求每個因子與另一個數是否都互素
posted on 2023-09-07 06:43
春秋十二月 閱讀(616)
評論(0) 編輯 收藏 引用 所屬分類:
Algorithm