丢番图方程及数论密码.pdf

西北大学 硕士学位论文 丢番图方程及数论密码 姓名 常茸茸 申请学位级别 硕士 专业 应用数学 指导教师 袁进 20080612 西北大学硕士学位论文 摘要 数论中最古老的 个分支是丢番图方程 其内容丰富 与代数数论 代数几何 组合 数学等有密切的联系 近三十年来 数论还被广泛地应用于信息编码理论 计算机科学 信号的数字处理等学科中 特别是数论密码的提出给数论的研究增加了新内容 因此 丢番图方程及数论密码一直是众多科研工作者热衷的研究对象 1 9 7 9 年 B e n d e rE A 和H e r z b e r gN P 讨论了不定方程o z 2 幻2 印 c l 2 4 的整数解问题 从而启 发人们考虑更一般的方程o z 2 6 D m 印 的整数解 同时 人们也在寻求将数论更好 地应用于现代密码学的理论 本文利用分解因子法和本原素除子的理论 讨论了丢番图方程矿一1 D 旷和 口z 2 6 D 矿解的情况 并且利用数论中的E u l e r 妒函数和连分数 提出了新的数论 密码系统 全文共分三部分 主要内容如下 第一章 阐述了丢番图方程及数论密码的发展概况以及求解丢番图方程的原则及 困难性 为后面的讨论做好准备 第二章 讨论了丢番图方程妒一1 D 旷和o z 2 6 D 矿解的情况 其中包含 三个定理和一个推论 并给出了严格的证明 第三章 利用E u l e r 妒函数和连分数 可以提出E u l e r 妒二元密码系统和连分数二 元密码系统 关键词 丢番图方程 方程的整数解 数论密码 密码系统 西北大学硕士学位论文 T h eD i o p h a n t i n eE q u a t i o nA n dN u m b e rT h e o r y C r y p t o g r a p h y A b s t r a c t T h ed i o p h a n t i n ee q u a t i o ni st h eo l d e s tb r a n c hi n 肌m b e rt h e o r y w h o s ec o n t e n t i se x t r e m e l ya b u n d a I l t a n di th a sc l o s ec o n n e c t i o n sw i t ht h ea l g e b r a i cm l m b e rt h e o r y t h ea l g e b r a i cg e o m e t r y t h ec o m b i n a t o r i c sa n ds 0o n I nt h er e c e n t3 0y e a r s t h e n u m b e rt h e o r yc r y p t o g r 印h yh a sd e v e l o p e dt o om u c hi nt h em o d e r nc r y p t o g r a p h y t h ei n f o r m a t i o ne n c o d i n gt h e o r ra I l dc o m p u t e rs c i e n c e e s p e c i a l l yi n u 珂 b e rt h e o r r c r y p t o g r a p h y S ot h e r ea r es t i Um a n yp e o p kw h oh a v eg r e a 上i n t e r e s t e di nd i o p h a n t i n e e q u a t i o n I n1 9 7 9 B e n d e rE Aa n dH e r z b e r gN Pd i s c u s s e dt h ei r l t e g e rs 0 1 u t i o no f d i o p h a n t i n ee q u a t i o no z 2 6 秒2 c 矿 c 1 2 4 w h i c hi n s p i r eu st os t u d y8 u c hk i n d o fd i o p h a n t i n ee q u a t i o no z 2 6 D c 矿 A tt h es a m et i m e w ea r ea l l s oi I l s p i r e dt o s e a r c hab e t t e rt h e o r y 1 1 s i n gt h en u l i b e rt h e o r yt om o d e r nc r y p t o g r a p h y I nt h i sp 印e r Id i s c u s 8 e dt h ei n t e g e rs o l u t i o 璐o ft h ed i o p h a n t i n ee q u a t i o nz p 一1 D 旷a n do z 2 6 D 矿而t hd e c o m p o s i t i o nf j a c t o rm e t h o da n dp r i m i t i v ep r i m ed i v i s o r t h e o r y A tt h es 锄et i m e Ir a i s e dan e wn u m b e rt h e o r yc r y p t o g r a p l l yb yu s i n go fE u l e r 妒f u n c t i o na n dc o n t i I m e df a c t i o ni nn u m b e rt h e o r y T h ew h o l ep a p e ri sd i V i d e di n t ot h r e ep a r t s a n di t sc o n t e n ti sa sf b U o w r s I nt h ef i r s tc h a p t e r t h ed e V e l o p m e I l ts u r v e yo f t h ed i o p h a n t i n ee q u a t i o na n dn 1 如叶 b e rt h e o uc 呻t o g r a p h y p r i n c i p l ea n dd i 伍c u l to fs o l v i n gd i o p h a n t i n ee q u a t i o na r es e t f o r t h w h i c hh a sm a d ep r e p a r a t i o nf o rt h ef o l l o w i n gc o n c l u 8 i o I l 8 I nt h es e c o n dc h a p t e r t h es o l u t i o no fd i o p h a n t i n ee q u a t i o nj 沪一1 D 可na n d n z 2 6 D 矿盯e 百v e n w h i c hi n c l u d i n gt h r e ec o n c l u s i o n s ad e d u c t i o na n dt h e s t r i c tp r o o f a r eg i V e n I nt h et h i r dc h a p t e r E u l e r 妒b i n a r yc 珂p t o s y s t e ma n dc o n t i 肌e df r a c t i o nb i n a r y c r y p t o s y s t e mh a r er a i s e d b yu s i n go fE u l e r 妒f u n c t i o na n dc o n t i n u e df r a c t i o n 西北大学硕士学位论文 K e y w o r d s D i o p h a n t i n eE q u a t i o n t h ei n t e g e rS o l u t i o n n u m b e rt h e o r yc r y p t o g r a p l l y c r y p t o s y s t e m 西北大学学位论文知识产权声明书 本人完全了解西北大学关于收集 保存 使用学位论文的规定 学校有权保留并向国家有关部门或机构送交论文的复印件和电子版 本人允许论文被查阅和借阅 本人授权西北大学可以将本学位论文的 全部或部分内容编入有关数据库进行检索 可以采用影印 缩印或扫 描等复制手段保存和汇编本学位论文 同时授权中国科学技术信息研 究所等机构将本学位论文收录到 中国学位论文全文数据库 或其它 相关数据库 保密论文待解密后适用本声明 学位论文作者签名 擞指导教师签名 2 础年6 月f 2 日 袁占厶堕 协8 年6 氐 毛日 西北大学学位论文独创性声明 本人声明 所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究 成果 据我所知 除了文中特别加以标注和致谢的地方外 本论文不包含其他人已经 发表或撰写过的研究成果 也不包含为获得西北大学或其它教育机构的学位或证书而 使用过的材料 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确 的说明并表示谢意 学位论文作者签名 串茸年 泖占年多月 2 日 西北大学硕士学位论文 序言 1 9 5 3 年 M a h l e r 在文 1 中证明了方程 D 1 2 2 D 2 入2 矿 A 1 以 2 9 c d D l D 2 1 只有有限组解 其中p 是素数 1 9 8 9 年 乐茂华在文 2 中证明了 对于给定的正 整数D 奇素数p p 不是D 的因子 假定m o z D p e 印e 印e 印1 0 0 0 如果存在 正整数s 使得D 3 s 2 1 p 4 s 2 1 时 则方程z 2 D m 矿除了正整数 z m n s 1 1 8 s 3 3 5 1 3 之外最多有一组解 z 3 m 3 锄 且如果这第三个 解存在的话 必有2m 3 否则方程z 2 D m 矿最多有两组解扛1 m 1 n 1 与 z 2 m 2 n 2 且如果这两组解都存在的话必有m 2 一m l 三1 m D d2 2 0 0 1 年 B u g e a u d 在文 3 中指出 利用B i l u 等人的本原素除子理论可以将乐茂华在文 2 中的条件 m n z D p e 掣印e 印1 0 0 0 去掉 这就启发我们研究这些方程的相关延伸问题 另一方面 二十世纪中后期 数论被广泛的应用于现代密码学 信息编码等理论中 尤其在数论密码方面 利用数论的基础提出新的密码理论 改进原有的密码理论越来 越多 这就指引我们研究更多的数论密码问题 本文继续了以上的研究工作 其研究成果期望有助于数学其它分支相关的问题的 研究与发展 并能在一些应用科学的研究过程中作为工具而直接使用 论文分为三部分 第一部分概述了丢番图方程及数论密码的发展概况以及求解丢番图方程的原则和 困难性 第二部分介绍了求解方程的基本方法 如分解因子法 p a d i c 方法等 利用以上方 法及本原素除子理论 讨论了 一 丢番图方程 矿一1 D 矿 其中p 是奇素数 n 3 D 2 且满足g c d D 妒 D 1 这里妒 D 表示D 的E u l e r 函数 那么方程至多有一个解使z 是一个礼次完全幂 二 丢番图方程 矿一1 5 矿 西北大学硕士学位论文 无整数解 其中2 I n p 满足p 三1 m o d 3 且3 是模p 的二次剩余 并论证了当p 1 3 3 7 6 1 7 3 9 7 时 方程 2 无整数解 其中2 h 三 丢番图方程n z 2 6 D m 矿解的情况 给出了当D 3 时 该方程 1 E o 6 3 p 1 2 D o 6 3 p 2 如果D n 6 3 p 2 设方程 1 2 1 6 的两个奇解为 z 3 m 3 几3 和 z 4 m 4 强 1 则p l m 4 4 七十3 6 3 字且存在A 1 使得3 A 一6 3 m a 一1 士3 竽成立 第三部分将数论中的E u l e rp 函数和连分数应用于现代密码学中 提出了二元密 码系统的新概念以及新的数论密码系统 即E u l e r 俨二元密码系统和连分数密码系统 并且较好地改进了H i u 密码系统和R S A 密码系统的安全性 由于作者水平有限 论文中漏洞和不妥在所难免 恳切希望专家及同行批评指正 第一章概述 第一章概述 1 1丢番图方程及数论密码概述 今天的数论已经发展了十多个数论分支 诸如代数数论 分析数论 不定方程 丢 番图逼近和丢番图几何等 其中不定方程是最古老的一个分支 所谓不定方程 是指未 知数的个数多于方程的个数的方程 或方程组 数论中的不定方程 通常对解的范围 有一定的限制 例如解限制在有理数 整数等范围内 人们为了与其他分支中的不定方 程区别 也称数论中的不定方程为丢番图方程 正如丢番图几何一样 它是代数几何中 曲线上的 点 带限制的部分 由于不定方程对解的特殊限制 在数论及数学的其他分 支如代数几何 代数数论 组合数学 计算机科学等的研究过程中 许多急待解决而又 有相当难度的问题最终都可归结为某些丢番图方程的求解问题 因此丢番图方程成为 历史上最活跃的数学领域之一 国内外许多著名的数学家都从事过对丢番图方程的研 究 其中R o t h B a k e r D e l i 鲫e F w t i n g s 等人的工作特别突出 他们分别获得了国际数 学家大会的F i e l d s 奖 在一个很长的历史时期内 数论被认为是一门没有应用价值的 纯 理论学科 但 是 二十世纪中后期 数论 4 被广泛地应用于现代密码学 信息编码理论 组合数学 信号的数字处理等学科中 改变了人们的看法 给数论的研究也增加了新的内容 数论 密码也由此产生 数论密码就是基于数论的密码 密码中的加密 解密 破译等问题都 与数论的求解联系在一起 例如信息编码理论中的设计出的各种纠错码 基本上是以 有限域和数论作为理论依据的 而有限域与数论又是紧密相连的 很多密码破译的难题 都是因为数论问题难解 因此 不仅数论本身的理论与方法有实用价值 就是它们中的 难题也为现实生活提供了应用的场所 正因为如此 国际数学大师陈省身先生才会主 张把数论作为一门应用数学学科 特别值得一提的是 数论密码是目前密码学中的主流 学科 成为诸多数学家和密码学家的研究热题 第一章概述 1 2丢番图方程的发展概况 1 9 3 7 年 古希腊数学家丢番图所著 算术 一书的空白处写下的注释 z 可 z n 礼 2 没用正整数解 1 9 5 5 年 K F R D t h 5 证明了一个著名的定理 设口是一个n 2 次的 代数数 则任意E o 适合1 日一引 o 仅有有限组 运用这一 定理得出了二元几次的不可约多项式方程当n 3 时解的个数有限 1 9 6 8 年前后 英 国数学家A B a k e r 6 m 成功地将G e l f o n d 和S c h n e i d e r 有关H i l b e r t 第七问题的结果 推广到一般的情况 给出了一大类丢番图方程的整数解的绝对值的上界 A B a k e r 的工 作给数论中包括丢番图方程的许多领域带来了突破性进展 1 9 7 3 年 R D e l i g n e 8 证明 了关于有限域上不定方程 z l z n 0 的解的个数的猜想 即著名的A w e i l 猜 想 1 9 8 3 年 G F a l t i n g s 9 证明了L J M o r d e U 猜想 即有理数域里亏格 2 的代数曲线 上仅有有限个有理点 由此可以导出F e r m a t 方程矿 旷 驴 z y 1 在n 4 时最多有有限组正整数解 1 9 8 5 年 利用G F 赳t i n g s 定理 D R H e a t h B r 嗍l 1 0 证明了 跣m 型导 o s o o 这里 s 表n s 使矿 旷 扩 2 有正整数解的那些 佗的个数 即对 几乎所有 的正整数n 2 方程矿 旷 扩均没有正整数解 进入二十一世纪后 关于丢番图方程的研究异常活跃 新理论新思想层出不穷 极 大的丰富了数论的内容 促进了数学的发展 尤其在2 0 0 1 年 B i l u H a n r o t 和V r o u t i e r 1 1 在L u c a s 数和L e h m e r 数的本原素除子的存在性理论研究方面取得重大突破后 国内 外学者利用Y B i l u 等人关于L u c a s 数与L e h m e r 数的本原素除子存在性的深刻结果 在研究一些指数型丢番图方程解的存在性和解数的上界取得了一些进展 1 3丢番图方程的困难性及求解原则 丢番图方程的内容异常丰富 但又没有一个统一的研究方法 这就决定了研究丢番 图方程的困难性 有一些看上去简单的方程 但解决起来却相当困难 例如求不定方程 1 z 2 2 y 4 2 第一章概述 的正整数解z y 问题 在很长时间内数学家们只知道它有两组解 z 秒 1 1 2 3 9 1 3 但要回答它是否存在另外的解却不容易 直到1 9 4 2 年W L j u n g g r e 在认真研究四次 域的单位数后 用了大量的现代数论的成果才最终证明 方程最多有两组正整数解 后 来 人们感到W L j u n g g r e n 的证明复杂又不初等 且方法上的技巧又太特殊 故大数学 家L J M o r d e l l 向全世界提出了一个公开性的问题 是否能找到一个简单的或初等的 证明 这个问题到现在仍为解决 还有很多类似的不定方程 都在各位数学家的研究 下 使得结果和证明过程都更加明了 就其研究目的而言 人们希望尽可能找到某种类型的一个一般性的求解过程 以便 在更多的场合更好地应用 有些问题在整数环上已经解决了 为了得到新的解题方法 人们把它拓展到代数整环上去研究 有些问题用高深的方法解决了 人们还想将其转 化为容易处理的问题 以期找到较为初等的方法解决 通过这些研究能不断产生新的 结构或新的技巧 而构成这种新结构或新技巧的往往可能是新数学分支的萌芽 也可能 对科学技术的发展产生某些特殊的应用 实际上 解决丢番图问题的方法自古至今从来都是不同问题采用不同方法 一般 说来 我们只能给出丢番图方程的求解原则 即综合利用各种初等的 高深的方法 将丢 番图方程转化为若干容易处理的或有熟知结果的方程 对于一个具体的丢番图方程 z l z n 0 z l 皿t i 1 n 其中 z 1 z 是关于未知数z l z n 的整系数多项式 皿t i 1 n 是未知 数的取值集合 一般情况下 我们需要解决下列问题 1 方程是否有解 z 1 z n 2 方程有解时 它的解是否为有限组 3 a 如果方程的解是有限多组 能否可以具体找出各组解 b 如果方程的解是无限多组 能否可以找到一个统一的求解公式 1 4数论密码的发展概况 密码学有两个显著特点 一是历史悠久 二是数学性强 几乎所有的密码体系都不 3 第一章概述 同程度地使用了数学的方法 尤其是数论1 1 2 1 3 1 代数几何方法 随着密码学的发展 由 新的加密 解密 破译等需要提出了新的数论问题 随着数论的发展也给密码学提供了 强大的知识基础 二者相辅相成 共同发展 早期的密码学称为古典密码和近代密码 最早产生于公元前两世纪 它们的基本技 巧都是数学中较为简单的代替 置换或者二者混合使用 此时的研究还称不上是一门 科学 直到1 9 4 8 年 C E S h a n n o n 14 在B e U 系统技术期刊上发表了一篇题为 保密系 统的通信理论 的著名论文 该文利用数学方法对信息源 密钥源 接收和截获的密文 进行了数学描述和定量分析 提出了通用的秘密密钥密码体制系统 从而使密码研究真 正成为了一门学科 至此展开了对密码学的广泛研究 1 9 7 6 年以前的密码体系均属于 对称密码体系 直到1 9 7 6 年 美国斯坦福大学教授E H e l l D l a n 他的研究助理W D i f h e 以及博士生R C M e r k l e 简称为D H M 1 5 首先提出了一种体现公钥密码体制思想 基 于离散对数问题的新技术 1 9 7 8 年 美国M I T 的三位数学家R L R i v e s t A S h a m i r 和 L A d l e m a n 简称为R S A 1 6 提出了一种基于整数分解困难性的公钥密码体系 目前 国际上公认比较安全的公钥密码体系是椭圆曲线密码体系 其思想是在基于有限域的 椭圆曲线上对信息进行加密解密 其难点是椭圆曲线上的离散对数问题 总之 密码学中的很多问题最后都可以归结为十分纯粹的数论 17 1 8 问题 这些问 题虽然已经产生了许许多多的成果 但是还有很多未解决的难题和未知的领域有待于 众多学者的研究 尤其是将数论的基础知识应用于实际密码问题的需要 4 第二章几类丢番图方程的研究 一 分解因子法 第二章几类丢番图方程的研究 2 1简单同余法和分解因子法 分解因子法 是将所给的丢番图方程经过整理 化为 z l z n D y 佗 1 然后分解 为两项乘积的形式 即 2 根据唯一分解定理 可得 D 1 卯 2 D 2 孵 其中D 旷 D 1 D 2 秒1 耽 这种方法是一种技巧性很强的初等方法 很多步骤上的想法 都是跳跃性的 由于这种方法的实质 是把丢番图方程不断展开 化为容易处理或有熟 知结果的方程 因此一方面这样可使问题简化 另外一方面就需要有这方面较为丰富的 知识 例如著名的C a t a l a n 方程 z 2 1 秒n n 3 z 0 在2z 时无整数解 这是因为上式可化为 一1 z 1 旷 而在2z 时 z 一1 z 1 1 故有 z 一1 z 1 聍 耖 秒1 耽 给出 2 鳝一卯 抛一秒1 访一1 聍一1 2 故论断正确 现在我们举一个例子 以说明这种方法的用法 例1 设p 是一个奇素数 则丢番图方程 4 2 4 一硎2 1 1 除开p 3 z 秒 1 和p 7 z 2 夕 3 外 无其他的正整数解 5 第二章几类丢番图方程的研究 证明 所给方程化为 2 2 2 1 2 2 2 1 删2 由于 2 2 2 1 2 2 2 1 l p 是一个奇素数 故上式给出 2 2 2 士1 册 2 2 2 千1 谚 可 秒1 沈 2 其中 y 1 耽 1 由 2 的前两式得 4 2 2 瑚 裾 此式可整理成 2 z 耽 2 z 一耽 硎 3 由于 2 z 耽 2 z 一沈 耽 1 故由 3 式给出 2 z 士抛 磁 2 z 千抛 谚 可1 驺玑 4 其中 蜘 驰 1 由此解出z 华 秒1 蜘玑 代入 2 的第一式得 2 华 z 士1 磁贸 由此整理得 秘 2 华 士1 5 取 号时 由 5 式给出贸 1 华 o 即给出方程 1 的正整数解p 3 z 剪 1 取 号时 5 式是方程z 4 箩4 2 2 2 z 秒 1 的特殊情形 于是给出 贸 1 华 士1 此给出 1 的正整数解p 7 z 2 可 3 证毕 二 p a d i c 方法 有一大类丢番图方程都可以化为 z l u l z n u n o 的形式 其中u 1 是n 次代数数域Q 口 的整底 为u 的范数 口为给定的 有理整数 利用代数数域的知识 上式可以化为 z l u P z n 挈 c o u 歹 1 n 6 第二章几类丢番图方程的研究 这里u o 表示u 的共轭 c E o 分别满足 c o o s u 1 且c o 只取有限个 Q 口 中的整数 比较u P u g 的系数可以得出若干等式 有一部分等式是 卯 z 1 z n O Z 1 扎一m 其中m 是 个给定的正整数 卯是关于z l 的有理系数多项式 然后利用p a d i c 数的性质可以给出方程的全部解 这种方法的实质是根据代数数论的知识把研究的问 题化为方程的形式 根据单位数的性质建立等式 然后比较素数p 的方幂 因此 p a d i c 方法是初等方法中比较素数幂的进一步深化 为了说明这个方法 我们引进p a d i c 数域锡和p a d i c 整数环乙的概念 这里的 定义及性质参考文献 1 9 定义1 设z Q Q 为有理数域 p a d i c 赋值lzI p 定义为 fo z o l zI p 1 p 一 z p 笔 z 1 z 2 1 p t z l z 2 显然 p a d i c 赋值有如下性质 1 IzI p 0 l zI p o 今z o 2 lz l z 2I p Iz 1l p Iz 2l p 3 Iz l 士z 2I p Iz 1l p lz 2f p 定义2 一个Q 上的p a d i c 收敛序列 z n Z l Z 2 这里 Q 定义为 对任给的E O 存在L 使得当m 几 L 时 有 z m z nl p 成立 如果上式换为Iz n nl p 2 无平方因子 n t 如 果方程有整数解z z 1 秒 则2z 这里九表示二次域Q 佃 的类数 1 9 4 2 年 L j u n g g r e n 2 8 证明了方程z 3 1 7 耖2 仅有整数解 z 剪 1 o 2 士1 4 士3 和 2 2 土3 9 1 9 8 5 年 曹珍富证明了护一1 D 2 当D 7 时无解 随后 又一般性地证明了 2 9 设D 不含2 m 佗 1 型的素因子 则除3 5 1 2 1 1 2 外 方程如果有解 必有2 他 1 9 8 7 年 孙琦 给出方程扩一1 D 秒2 当D 1 5 2 3 时 仅有整数解z 0 曹珍富给出了在2 D l 以及几 2 9 第二章几类丢番图方程的研究 至此 对于更广泛的方程 矿一1 D 旷 2 1 其中 p 是奇素数 n 3 D 2 的情形尚未研究 因此 本文将讨论方程 2 1 解的情 况 为了完成定理的证明我们先给出下面几个引理 引理1 嘲 不定方程 等叫 哪 m 1 n 1 I 抄1 没有使z 是一个n 次完全幂的整数解 z 剪 m n 引理2 不定方程 扩一切 士1 其中 6 口 1 z 可 n 6 n 除了n 3 6 口 1 2 o m 饥 o 3 佗 8 3 并且 1 7 礼 3 4 7 外 至多有一组解 下面我们来证本节的主要定理 二 丢番图方程妒一1 D 圹解的情况 定理1 丢番图方程 矿一1 D 矿 其中p 是奇素数 n 3 D 2 且满足g c d D 妒 D 1 这里妒 D 表示D 的E u l e r 函数 那么方程 2 1 至多有一个解使z 是一个礼次完全幂 证明 设g 是D 的任一奇素因子 p 3 为奇素数且 g 1 我们首先证明 g 等 1 2 2 g J l 2 z Z l 我们用反证法证叽若 g 等 1 由 2 1 知矿三1 m o d 口 g z 1 设9 是 g 的一个原根 则存在 使得矿兰z m o dg 所以严三1 m o dg 故有口一1J 印 由题 设有0 g 一1 1 故g 一1 l t 9 三1 m o dg 则z 三1 m o dg 与 一1 碧 1 或p 矛盾 故式 2 2 成立 1 n 第二章几类丢番图方程的研究 i 三乩 仁3 i 篡姚咖姚H 印幽H 仁4 囊 仁5 臻蚴乩 眨6 第二章几类丢番图方程的研究 利用定理1 本文研究了D 5 时方程 2 1 的解的情况 有 定理2 丢番图方程 矿一1 5 旷 无整数解 其中2 I n p 满足p 三1 m o d3 且3 是模p 的二次剩余 证明 由定理1 的讨论过程知 此时 2 7 如果有解 仅下面三式成立 当 z 一1 智 1 时 悖三乩 当 z 一1 碧 p 时 爱问 由 2 7 得 矿三l m o d5 它的全部根为 z 兰1 m o d5 2 7 2 8 2 9 2 1 0 2 1 1 对于 2 8 星尹 1 由于模5 的全邵二次剩余为1 4 这与 2 1 1 式矛盾 故 2 8 式不成立 对于 2 9 p I z 一1 则z 三1 m o dp z 2 z 1 三3 m o dp 再由定理条件知 生笋 1 且 南 芝吝蕞铲 南 1 这里2 t z 2 z 1 可得 兰专产 1 所以 垂铲 1 但由 2 1 1 知z 2 z 1 兰3 m d5 可得矛盾 故 2 9 式不成立 1 2 卯 沈矿嘶乩 咖 k m 一 一J q 卜碧炉 第二章几类丢番图方程的研究 对于 2 1 0 的讨论同 2 9 利用定理2 在计算机辅助的基础上研究了p 1 0 0 时 方程 2 7 的解 即 推论当p 1 3 3 7 6 1 7 3 9 7 时 方程 2 7 无整数解 其中2 h 证明 在p e 印e 印e 印1 0 0 0 如果存在正整数s 使得D 3 s 2 1 p 4 8 2 1 时 则方程z 2 D m 矿除了正整数 z m n s 1 1 8 s 3 3 s 1 3 之外最多有一组解 z 3 m 3 n 3 且如果这第三个解存在的话 必有2m 3 否则方程 z 2 D p n 最多有两组解 z l m 1 扎1 与 z 2 m 2 礼2 且如果这两组解都存在的话必 有m 2 一m 1 三1 m D d2 1 9 9 2 年 C o h e n 在文 3 8 中完全解决了方程z 2 2 七 圹在后为奇数时的求解问 题 13 第二章几类丢番图方程的研究 1 9 9 7 年 乐茂华在文 3 9 中证明了方程z 2 2 旷在尼为偶数时无解 这样就 使得方程z 2 2 圹的求解问题得到完全解决 2 0 0 1 年 B u g e a u d 在文 3 中指出 利用B i l u 等人的本原素除子理论可以将乐茂 华在文 2 中的条件m n z D p e 印e z 弘印1 0 0 0 去掉 即对于给定正整数D 奇素 数p p 不是D 的因子 如果存在正整数s 使得D 3 s 2 1 p 4 s 2 1 时 则方 程z 2 D 矿除了正整数解 z m n s 1 1 8 5 3 3 s 1 3 之外最多有一组解 z 3 m 3 n 3 且如果这第三组解存在的话必有2m 否则方程z 2 D m 矿最多有两 组解 z 1 m 1 n 1 与 z 2 m 2 几2 且如果这两组解都存在的话必有m 2 一m 1 三1 m o d2 B u g e a u d 没有给出这个结论的证明 实际上B u g e a u d 的这个结论不是完全正确的 2 0 0 7 年 胡永忠在文 4 0 中证明了当D 3 p 1 3 时 方程z 2 D 矿恰有两组正整数 解 z m 礼 2 2 1 4 6 4 3 适合2m 此外 该方程适合2Im 的解数不超过1 本文将利用B i l u 等人关于本原素除子的深刻理论讨论方程n 一 6 D m p n 的求 解问题 并给出了结果的完整证明 结合二次丢番图方程解的表示的精细结果 我们还 得到了于此相关的问题的一些结果 为了更好的证明结果 先给出一些定义和引理 定义1 设口 p 为代数整数 Q p 与a p 是非零互素的有理整数 且Q 伊不 是单位根 则称 a p 为L u c a s 数偶 对于给定的L u c a s 数偶 Q p 我们定义对应的 L u c a u s 数序列如下 让 锄 邢 箬小 0 1 1 2 定义2z 设Q 卢为代数整数 Q p 2 与Q p 是非零互素的有理整数 且口 p 不 是单位根 则称 Q p 为L e h m e r 数偶 对于给定的L e h m e r 数偶 Q p 我们定义对应 的L e h m e r 数序列如下 一姒郇 善 省 显然 L u c a u s 数偶也是L e h m e r 数偶 定义3 设Q 卢为L u c a s 数偶 素数p I 让 a 卢 且p 不是 Q 一卢 2 u 1 u n l 的因 子 则称p 是u Q p 的本原素除子 设o 卢为L e h m e r 数偶 素数p I u n Q p 且p 不 是 Q 2 一p 2 2 u 1 u 一1 的因子 则称p 是札 Q p 的本原素除子 第二章几类丢番图方程的研究 引理1 1 1 对于任意大于3 0 的正整数n L u c a s 数和L e h m e r 数u Q p 具有本 原素除子 当n 3 0 时 没有本原素除子的Q p n 可以完全决定 引理2 l l 设5 扎 3 0 且礼 6 则所有使u n Q p 不具有本原素除子的L u c 鸽 数偶 Q p 可表为 郇 学 学 及与它们等价的L u c a s 数偶 引理3 1 l 设7 佗 3 0 且佗 8 1 0 1 2 则所有使u n Q 不具有本原素除子 的L e h m e r 数偶 Q p 可表为 a 捌 掣 每学 及与它们等价的L e h m e r 数偶 引理4 2 1 设n 1 6 1 是无平方因子的正整数 奇数P 1 则丢番图方程 口X 2 6 y 2 P n x 凡 Z g c d n x 6 y 1 佗 0 的解最多属于掣 P 1 个类中 且在每个类S 中存在一个唯一的解 x l M n 1 满足 X 1 0 M 0 n 1 在所有的属于类S 的解中最小 即任意 恐 蚝 n 2 S 有n 1 礼2 并且 n 2 酬僦 蚝问 A 1 皿l 沁M 俩 这里 是正整数 u P 表示P 的不同素因子的个数 A 2 士1 且如果6 1 则 A 2 1 一1 如果6 1 贝0A 2 1 一1 i 一i 引理5 1 l 4 l 设R M Z 其中g c d R M 1 R O Q 和p 是方程z 2 一 赢 M 0 的两个根 记K Q n 矿 则 1 g c d u o 卢 u Q p u g c d r n Q p 2 若m g c d m 佗 与佗 g c d m n 均为奇数 则g c d V n K K d n 否则 g c d K 1 或2 其逆定理也成立 引理6 4 2 丢番图方程 4 2 2 5 可2 士1 z 0 可 0 1 5 第二章几类丢番图方程的研究 仅有正整数解 z 可 1 1 下面来证本节的主要定理 二 丢番图方程o z 2 6 D m 矿解的情况 我们的工作将围绕着指数丢番图方程 o z 2 6 D m 矿 o 6 z D p 2l 佗 6 1 D t 6 3 1 展开 如果m 是奇 偶 数 则方程 3 1 的正整数解 z m n 叫做奇 偶 解 为方便起 见 我们以 n 6 D p 表示方程 3 1 的正整数解的个数 以D 口 6 D p 表示方程 3 1 的奇解个数 以E 口 6 D p 表示方程 3 1 的偶解的个数 记 z l m 1 n 1 为方 程 3 1 所有偶解 z m n 中使m 为最小者 称为最小偶解 如果有不止一个这样的 解时 则称所有这样的解中使n 1 最小者为最小偶解 因此 最小偶解是唯一的 同样 我们可以定义最小奇解且最小奇解也是唯一的 我们首先考虑n 1 且n 6 都不是完全平方数的情况 假设方程 3 1 除了最小 偶解外还有其他的偶解 z 2 m 2 n z 由引理4 知存在整数x l M l 2 使得 3 2 及 J 痂m 2 胆怕2 厅 3 慨 4 M 厅 2 3 3 I 怕D m 2 2 一z 2 二石 A 3 5 x 1 一A 4 M 丽 2 其中X 1 M 匿 g c d x 1 K 1 1 2 o M 2 p 磊 A l A 2 A 3 A 4 一1 1 五M 啦 i 1 2 由 3 2 式可得 2 以D m 2 士 以x 1 M 厂乏 以x 1 一M 厂乏 v t 3 4 由 3 3 式可得 2 以D 2 士 以x 1 M 厂石 2 以x 1 一M 厂乏 2 3 5 1 6 M M 厅厅 H K 肋 沁 一 X X 以以 舡 厅厅 现 研 一 肛 胆 m 帆 D D 以瓶 J l 第二章几类丢番图方程的研究 设a 政1 M 磊 p 议1 一M 磊 由于 a 卢 2 4 1 2 及口 p 6 x 1 2 n M 2 p 而 且g c d 4 以1 2 p 1 同时Q 是一元二次方程p z z 2 2 凸M 2 6 x 1 2 z p z o 的根 而 2 o M 2 一 1 2 p 1 从而口伊不是单位根 于是由定义 1 知 Q p 是L e h m e r 数偶 设d g c d 1 2 2 纪 由 3 4 3 5 及引理5 知 t 为奇数 且 2 以D m 2 士g c d 2 勋m 2 2 西m 2 士 撖1 M 厅 d 锨1 M 伍 d 3 6 令 y 狐x 1 M d 由于2 I n 则由前面的讨论知2 于是 y A B 何 同理令7 7 一A B 何再由 3 6 式可得 以D m l 2 士A A 2 0 6 8 2 p z 婵 g c d A B 1 A B 3 7 容易验证 7 7 7 是L e h m e r 数偶 由 3 5 3 7 式可得 D 竽 士u t 7 7 7 3 8 由于 y 2 7 7 2 2 一4 口6 2 8 2 D 如果m 1 仇2 则t 1 且m 7 叩 的任何素因 子都是 7 2 一叩2 2 的因子 根据本原素除子的定义知u t 7 7 7 没有本原素除子 运用引 理1 及引理3 知 3 或5 如果m 1 m 2 则 2 1 从而t 1 同样可知t 是奇数 注意到此时 3 8 式 的左边为1 根据本原素除子的定义知u t 7 叩 没有本原素除子 运用引理1 及引理3 知 t 3 或5 假设方程 3 1 除了最小奇解 z 3 仇3 n 3 外还有其他的奇解 钆 m 4 n t 由引理 4 知存在正整数拖 蚝 3 4 使得 廊 D 忡3 胆俩 戚 2 K 俩 3 3 9 l 玉3 一D a 一1 2 j 万 A 1 戚一A 2 K j 面 3 及 向彻 4 胆何 3 佩 4 蚝佃 4 3 1 0 I 石z 4 一D 玎 一1 2 j 万 A 3 伍 硷一A 4 蚝 习万 4 第二章几类丢番图方程的研究 其中尥 砼 g c d 恐 蚝 1 2 6 D M 2 p z 2 入l 入2 h A 4 一1 1 易M 啦0 3 4 由 3 9 式可得 2 D 哟一1 2 j 西 士 儡 A 2 M 莎 3 一 偶一A 2 K j 西 飓 3 1 1 由 3 1 0 式可得 2 D m a 一1 2 面 士 以 A 2 蚝 面 4 一 以恐一A 2 蚝 二面 4 3 1 2 设Q l 俑 K 硒 历 僦一M 二面 由于 Q 1 岛 2 4 n 砖 及Q p n 脚 6 D 曙 谚 且g c d 4 n 镌 p 1 由于a 胪是一元二次方程 妒z 2 2 n 磁2 6 D 蚝2 z p z 2 o 的根 而 2 n 2 一阳K 2 p 1 从而Q p 不 是单位根 于是由定义1 知 o p 是L e h m e r 数偶 设d 1 g c d 3 4 4 t d l 由 3 1 1 3 1 2 及引理5 知 为奇数 且 2 D m 3 1 2 何 土g c d 2 D m 3 1 2 何 2 D m 4 1 2 向西 士 瓦砭 K 二面 d 1 一 以恐一砼 面 d 1 3 1 3 同上 令7 1 僦 蚝 厂习万 d A 1 B 1 面西 7 7 1 偶一M 习万 d A 1 一B 1 石面 则由 3 1 3 式知 D 1 3 1 2 士B 1 伍 A n 6 D B p z 2 d 1 g c d A 1 B 1 1 A 1 B 1 3 1 4 由于饥 叼1 2 A l 所以 饥 叩1 是L u c a s 数偶 并由 3 1 2 3 1 4 式 可得 D 盟产 士让t 7 l 7 7 1 3 1 旬 由引理2 以及前面的讨论知 z 3 其次 对于o 1 的情况 n 6 为完全平方数时也可以归于此类情形 方程即为 z 2 c 矿这类方程在文 3 2 3 8 4 1 中已经得到了较为满意的结果 这里利用L u c a u s 数 L e h m e r 数的本原素除子理论 类似上面的讨论方法也能得到相同的结果 在此省 略证明过程 因此 对于任意的口 6 方程n z 2 6 D 矿解的情况都可由 3 8 式和 8 第二章几类丢番图方程的研究 3 1 5 式出发 讨论t 的取值以及相对应的L u c a u s 数和L e h m e r 数 就可以求出方程的 解 本文作为例子只讨论了当D 3 时 丢番图方程 口z 2 6 3 p 解的情况 D 为其他情况时都可以用此方法推出结果 定理3 设整数o 6 1 且无平方因子 素数p 3 则对于方程 3 1 6 1 E o 6 3 p 1 3 1 6 2 0 o 6 3 p 2 如果D 口 6 3 p 2 设方程 1 2 1 6 的两个奇解为 z 3 m 3 n 3 和 z 4 m 4 砌 则p 3 m 4 4 七 3 6 3 竽且存在A l 使得3 钟一6 3 m a 一1 士3 罕成立 证明 1 设 z 1 m 1 n 1 为方程 3 1 6 的最小偶解 如果方程 3 1 6 还有其他偶解 z 2 m 2 n 2 由前面的分析 我们可以得到 3 7 和 3 8 式 其中D 3 t 3 5 如果t 3 从 3 8 式可得A 2 3 n 6 8 2 士3 z 一 2 由 3 7 式知6 扩 A 2 因此有 6 3 m 1 3 0 6 J E 7 2 士3 m 2 一m 1 2 3 1 7 由于A B 互素 A 士饥 3 M 2 以及m 1 2 于是有 及 3 m 2 一m 1 2 3 6 3 1 1 一o B 2 A A 1 一1 由 3 1 8 式推得6 3 一 一2 2 再从 3 7 式和 3 1 9 式可得 3 1 8 3 1 9 p z l d A 2 0 6 8 2 4 6 3 1 1 士6 6 4 3 m 1 1 士1 3 2 0 注意到由 3 2 0 式可知p 1 6 又因为6 3 一m 一2 2 因此p 3 则 3 2 0 式变为 3 2 1 d 一三亡笋兰 4 3 m 1 1 士l 3 2 3 m 1 2 2 2 士1 3 2 1 对 3 2 1 模3 知 3 2 1 式无解 第二章几类丢番图方程的研究 同理 当t 5 时 由 3 7 式得 6 2 3 2 m l 一1 0 0 8 2 3 1 5 0 2 8 4 士3 旦产 3 2 2 由于A J E 7 互素 A 士怕 3 胁 2 及m l 2 将 3 2 2 式两边模3 得6 3 丑 且 3 2 2 式右边只能取 1 这就推得5 3 一o J E i 2 2 4 3 2 一1 与引理6 矛盾 因 此E 6 3 p 1 2 设 z 3 m 3 n 3 为方程 3 1 6 的最小奇解 如果方程 3 1 6 还有其他奇解 甄 m 4 n 4 由前面的分析 我们可以得到 3 1 4 和