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
春秋十二月 阅读(596)
评论(0) 编辑 收藏 引用 所属分类:
Algorithm