2019-10-02 2次整环的素性分析

考虑形如:

$\ x+y\times \sqrt{D} 的数字其中 x,y是整数 ,D=+-1或者为素整数(可为负），$

$\ 所有这样的数字，关于+，和 \times 运算构成一个环；也就是关于 + ,和 \times 是封闭的$

$\ 显然 (a+b\times \sqrt{D}) \times (c+ d \times \sqrt{D})=ac+bdD + (bc+ad)\sqrt{D}$
$\ (a+b \times \sqrt{D})+(c + d \times \sqrt{D})=(a+c)+(b+d) \times D$
$\ 乘积以及和仍然具有x+y \times \sqrt{D}的形式$

$\ 就像所有整数组成的集合被记作 Z 一样，所有这样的数字组成的集合被记作 Z[\sqrt{D}] 且Z是Z[\sqrt{D}]的子集$

$\ 下面研究Z[\sqrt{D}]中什么样的数字是素数，$

首先给出若干定义：
1.整除
$\ 在环R中，如果存在数字y使得 x \times y=z ，则称x整除 z ，记作 x|z$
2.可逆元
$\ 环R中，整除1的所有数字都被称为可逆元$

素数
环R中，如果1个数字p ，如果满足：
$\ 1，给定R中任意a,b , 如果p|(ab) 必有 p|a \ or\ p|b$
$\ 2, p不是可逆元$
$\ 则p称为环R中的素数，简称素数$

4.不可约数
$\ 环R中，一个数p不可约当且仅当不存在非可逆元a和非可逆元b 使得 p=a\times b成立$

容易证明，素数一定不可约，但反之未必

下面为以上抽象概念举个例子，来整数环Z来说，
可逆元是 +1 和 -1
正素数包括 2,3,5,7,11,13,17,... 以及负素数 -2,-3,-5,-7,...
Z中的不可约数就是素数，对于Z来说不可约和素是等价的

下面开始正式分析：

首先，上述定义都相对某个环而言才有意义，因此
$为了区别Z[\sqrt{D}]中的素数和Z中素数，我们把Z中的素数称为整素数，$
$Z[\sqrt{D}]中的素数称为素数，$

同时，我们必须先证明一个命题，该命题在后文中会隐晦的使用到
$\ 假设 a,b都属于Z ，则$
$\ a,b看作Z[\sqrt{D}]中的元素，如果a|b,$
$\ 则必然a,b看作Z中的元素，也有a|b$

$\ 证明：看作Z[\sqrt{D}]中的元素，如果 a|b$
$\ 则有 a \times (x+y\sqrt{D})=b => a \times x + a \times y \times \sqrt{D}=b$
$\ =>a \times x=b ,a\times y =0$
$\ =>a|b$
证明完毕

$\ 其次，我们证明如果 x+y\sqrt{D}是一个可逆元素，必有x^2-y^2 D=+-1$
证明:
$\ 首先在Z中,gcd(x,y)=1,否则 gcd(x,y)|(x+y\sqrt{D})|1导出矛盾,$
$\ 1/(x+y\sqrt{D})=(x-y\sqrt{D})/(x^2 - y^2D)$
$\ => (x^2 - y^2 \times D)|x$
$\ 且 (x^2 - y^2 \times D)|y$
$\ 结合gcd(x,y)=1 ,必有 x^2 - y^2 D|1 证明完毕$

$\ 在Z[\sqrt{D}]中给定数字 x+y\sqrt{D} ,首先假定它是一个素数，$
$\ (x+y\sqrt{D}) \times (x-y\sqrt{D}) = x^2 - y^2D$
$\ 根据整除定义，有 (x+y\sqrt{D})|(x^2 - y^2D)$
$\ 我们把 x^2 - y^2D 分解为整素因子，$
$\ 根据素数定义，则 (x+y\sqrt{D}) 必然整除其中某个整素因子，不妨设这个整素因子为p 则 , (x+y\sqrt{D})|p$

$\ 不妨设 (x+y\sqrt{D}) \times (a+b \sqrt{D})=p$
则容易推导出:

$\ x \times a + y \times b \times D=p$
$\ y \times a + x \times b =0$

根据线性代数知识：
$\ x^2 - y^2\times D \neq 0 且$
$\ a= (px)/(x^2 - y^2D)$
$\ b= (-py)/(x^2 - y^2D)$
$\ 由于a,b必须为整数，则 (x^2 - y^2 \times D)|(px) 且 (x^2 - y^2 \times D)|(py)$

$\ 由于假定x+y\sqrt{D}是素数，显然 gcd(x,y)=1, 立刻得到$
$\ (x^2 - y^2D)|p$

$\ 则 x^2 - y^2D有4个可能的值$
$\ 1，-1，p,-p$

$\ 前2个是不可能的，因为如果x^2 - y^2D =+-1$
$\ 根据 (x+y\sqrt{D})|(x^2 - y^2D) 将得到$
$\ (x+y\sqrt{D})|1 则这与 x+y\sqrt{D}是素数定义相矛盾$

$\ 所以必有 x^2 - y^2D=(+-p)$

$\ 下面证明如果 x + y\sqrt{D} 是一个素数， x-y\sqrt{D} 也是一个素数$
$\ 假设 (x-y\sqrt{D})|(a+b\sqrt{D}) \times (c+d\sqrt{D})$
$\ => (x+y\sqrt{D})|(a-b\sqrt{D})\times (c-d\sqrt{D})$
$\ => x+y\sqrt{D} |(a-b\sqrt{D}) \ or\ x+y\sqrt{D}|(c-d\sqrt{D})$
$\ => x- y\sqrt{D} |(a+b\sqrt{D}) \ or\ x-y\sqrt{D}| (c+d\sqrt{D})$
证明完毕

综上：
$\ 如果 x+y\sqrt{D}是一个素数，则 x-y\sqrt{D}也是一个素数且两者乘积 x^2 - y^2\times D 必然是一个整素数q$

$\ 既然 x+y\sqrt{D}和 x-y\sqrt{D}都是素数，它们有没有可能互相整除（举例来说 (-7)|7，且-7!=7）？$
$\ 假设 x+y\sqrt{D}|(x-y\sqrt{D}) ,两边同时乘以 x-y\sqrt{D}$
立刻得到
$\ q|(x^2 + y^2 \times D)$
$\ q|(2xy)$

$\ 首先D!=q$
$\ 否则，q|(x^2 + y^2 \times D) => q|x =>D|x ,设D \times z=x$
$\ 则x+y\sqrt{D}= Dz+y\sqrt{D}= \sqrt{D} \times (y+z\sqrt{D})$
$\ 显然与 x+y\sqrt{D}是素数相矛盾，$

$\ 先假定q是奇素数：$

$\ 则q|x \ or \ q|y$
$\ 如果 q|x$
$\ 有q|(y^2\times D)=>q|y$

$\ 如果 q|y$
$\ 则 q|x$

$\ 以上都会导致 gcd(x,y)！=1,矛盾$

$\ 所以，当q是奇素数，x+y\sqrt{D}无法整除x-y\sqrt{D} ，类似可以证明 x- y\sqrt{D}也无法整除x+y\sqrt{D}$
$\ 简单而言，x+y\sqrt{D}和x-y\sqrt{D}不是相伴数$

$\ 如果q是偶素数，只能为2;此时，商为$
$\ (x^2 + y^2 \times D)/2 -xy\sqrt{D}$
判断其是否可逆元，计算
$\ ((x^2 + y^2 D)/2)^2 - x^2 y^2 D ,化简为:$
$\ (1/4) (y^2 D - x^2 )^2 = (1/4) 2^2=1 ，确实可逆$

$\ 说明当q=2时， x+y\sqrt{D}和x-y\sqrt{D}只差一个可逆元；$

综上，得到定理：
$\ 如果x+y\sqrt{D}是素数，则必有x^2 - y^2D是一个素数q，且q !=D;$
$\ 当q为奇素数时 q = (x + y\sqrt{D}) \times (x - y\sqrt{D}) 恰好是把其分解为2个不同素数的一个分解;$
$\ 当q为2时，q= (x + y\sqrt{D}) \times (x-y\sqrt{D}) 的2个素因子相差一个可逆元；$

下面考虑其逆命题：
$\ x^2 - y^2D 是一个素数q, 且 q!=D ,则x+y\sqrt{D}是否一定是素数$

$\ 首先x+y\sqrt{D}|1 不成立，否则$
$\ 1/(x + y\sqrt{D}) =( x-y\sqrt{D})/(x^2 - y^2D) =>$
$\ q|x且q|y => q^2 | x^2, q^2 | y^2 => q^2 | q 矛盾$
$\ 并且，同样的理由 gcd(x,y)=1$

$\ 且q|y也不成立，否则$
$\ x+y\sqrt{D}|x => q|x$
$\ (如果q|x不成立 ,存在 ,m,n使得 mq+nx=1, 则x+ y\sqrt{D} |1 ,矛盾）$
$\ 与 gcd(x,y)=1矛盾$

$\ 则，存在整数 m使得 q|(my-1)$
$\ 于是 x+y\sqrt{D} |(x+y\sqrt{D}) 且x+y\sqrt{D}|my-1$
$\ =>x+y\sqrt{D} |m\times (x+y\sqrt{D})$
$\ =>x+y\sqrt{D}| m x + \sqrt{D}$
$\ 设 k=-m x 则 x+y\sqrt{D}| \sqrt{D} - k$
$\ 也就是说，存在整数k 使得 x+y\sqrt{D}|\sqrt{D} - k$

$\ 现在来证明 x+y\sqrt{D}是素数$
$\ 假设 x+y\sqrt{D}| (a+b\sqrt{D})\times (c+d\sqrt{D}) ，通过上述$
$\ 方法找到 k,则有 x +y \sqrt{D} | \sqrt{D}-k$

$\ => (x+y \sqrt{D}) | (a+b\times k) \times (c+d \times k)$

$\ 此时，必有 q|(a+bk) \times (c+dk)，否则$
$\ 存在 m,n使得 mq+ n[(a+bk)\times (c+dk)]=1 => x+y\sqrt{D}|1 ，矛盾$

$\ 则 q|(a+bk) \times (c+dk) ,根据q是素数，$
$\ q|(a+bk) \ or \ q|(c+dk)$
$\ 则 x+y\sqrt{D} |(a+bk) \ or\ x+y\sqrt{D}|c+dk$

$\ 再次结合x+y\sqrt{D}| \sqrt{D}-k$
$\ => x+y\sqrt{D}|a+b\sqrt{D} \ or\ x+y\sqrt{D} |c+d\sqrt{D}$

$\ 综上，根据定义x+y\sqrt{D} 为素数$

全文结论可以概括为以下2个定理
$Theorem1：$
$\ D是素数时，Z[\sqrt{D}]中的可逆元素x+y\sqrt{D}必然满足 x^2 - y^2\times D=+-1$

$Theorem2：$
$\ 当D是奇素数时，在环Z[\sqrt{D}]中$
$\ x + y\sqrt{D}是素数当且仅当 x^2 - y^2\times D是一个不等于D的素数q.$
当以上条件成立时，
$\ q= (x + y\sqrt{D}) \times (x-y \sqrt{D}) 是q在Z[\sqrt{D}]下的一个素因子分解$
$\ 当q为2时，两个素因子相差一个可逆元；当q为奇素数时，两个素因子彼此不相整除.$

最后，给出这2个定理的一个应用
$\ 设p,q为不相等的奇素数，$
$\ 则不定方程x^2 - qy^2 = p 的整数解，可以由 x^2 - qy^2 =+-1的解派生出来，$

证明:
$\ 假设x^2 -qy^2 =p 至少存在一个解 a,b$
$\ 则 (a-\sqrt{q} b)\times (a+\sqrt{q} b) =p 根据定理，a+\sqrt{q}b和a-\sqrt{q} b是两个素数$
$\ 则如果 x^2 - q\times y^2 =p还有另一组解 ,u,v$
$\ 则(u- \sqrt{q}v)\times (u+\sqrt{q}v)= p 根据素数性质,有$

$\ a+\sqrt{q} b| u-\sqrt{q} v \ or\ a+\sqrt{q} b| u+\sqrt{q} v$
$\ 因为可以通过用-v取代v改变符号，因此不妨假设 a+\sqrt{q} b|u+\sqrt{q} v$

$\ 则 u+\sqrt{q}v = (m+n\sqrt{q})\times (a+\sqrt{q}b) 且 m+n\sqrt{q}是一个可逆元素$
$\ 则根据定理1: m^2 - n^2 \times q =+-1$

$\ 这就意味着，x^2 -q \times y^2 =p的所有整数解 (u,v)，可以表为形式:$
$\ u = ma+nbq$
$\ v = na+mb$
$\ 其中 (m,n)是 m^2 -q\times n^2 =+-1的解$

$\ 举例来说， x^2- 3y^2 =1 有解 (2,1) 根据佩尔方程性质$
$\ x^2-3y^2 =1的通解可由 (2+sqrt(3))^a 和 (2-sqrt(3))^a 派生出来，$
$\ 得到 (7,4) ,(26,15),(97,56)....$

$\ 且 x^2-3y^2 =13 有解 (4,1)$
$\ 则x^2-3y^2=13的其余解可根据 (7,4) ,(26,15),(97,56) 求出为:$
$\ u=7\times 4+4\times1\times 3=40$
$\ v=4\times 4+7\times 1=23$
$\ u=26 \times 4+15\times1 \times 3 = 149$
$\ v=15\times 4+26\times 1=86$
$\ u=97\times 4+56\times 1\times3=556$
$\ v=56\times 4+97\times 1=321$

$\ (40,23),(149,86), (556,321) ...$
$\ 都是方程 x^2 -3y^2 =13 的解...$

$继续前文的分析$

最后编辑于：2019.10.21 22:14:51

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 203,098评论 5赞 476
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 85,213评论 2赞 380
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 149,960评论 0赞 336
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 54,519评论 1赞 273
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 63,512评论 5赞 364
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 48,533评论 1赞 281
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 37,914评论 3赞 395
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 36,574评论 0赞 256
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 40,804评论 1赞 296
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,563评论 2赞 319
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 37,644评论 1赞 329
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,350评论 4赞 318
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 38,933评论 3赞 307
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 29,908评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,146评论 1赞 259
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 42,847评论 2赞 349
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,361评论 2赞 342

2019-10-02 2次整环的素性分析

推荐阅读更多精彩内容