高次剩余理论研究.doc

高次剩余理论研究参赛队员景琰杰 顾韬指导老师施洪亮学校华东师范大学第二附属中学摘要本文用初等数论的研究方法, 研究了当指数为奇质数、直到一般大于等于2的正整数时, 高次剩余的一些基本性质, 最后讨论了关于符号的一些基本性质. 关键词: 高次剩余引言平方剩余作为同余式理论的一项重要的组成部分, 在初等数论中一直占着举足轻重的地位. 1796年高斯发表的二次互反律为这一理论画上了一个圆满的句号. 但是高次剩余的研究却因为其情形的复杂、规律的不明显而一直没有完成. 本文用初等数论的研究方法, 研究了高次剩余的一些基本性质. 定义 假如有解, 则称为的次剩余, 否则称为的次非剩余. 为方便计, 引入符号. 当时, 表示是的次剩余; 当时, 表示是的次非剩余. 当时即为熟悉的平方剩余, 此时可略去不写, 简记为. 正文因为当为合数时, 等价于一组模为质数的的同余方程组. 故这里先假定为质数. 又因为当时结论是平凡的（此时恒有）. 故又假定为奇质数. 1 的可解性1.1 当为奇质数时当为奇质数时, 由于. 即的完全剩余系的前半部分与后半部分的次剩余一一对应互为相反数. 因此在讨论时, 只需要考虑的完全剩余系的前半部分的次剩余. 1.1.1当=3时有以下结论定理 1. 1. 1（1）当时 , 恒成立, 当时, 在的完全剩余系中只有个使. 证明：当时, , 故有三个不同的解, 除了之外还有两个解, , 且, , , 即, 在上式同时乘以. 其中满足, 则 . 由此即得到剩下的组剩余. 因此的立方剩余有个. 当时, 有, 假如有三个不同的解, 则, 故. 由于, , 故矛盾, 得故至多有两个解, 是其中一个解. 假如只有一个解, 则. 由于是一次式, 其系数不为0, 故必有解, 故解为, 即, 得 , 即, 取, 得, 故, 而, 矛盾, 故无解, 即只有解. 假如有两个解, , 且, 即, 则. 因为, 所以. 设, 则, , , 即有两个解, 这与只有一个解矛盾, 故至多有一个解. 假如无解, 即对任意都成立, 则 对任意都成立. 因为, 所以. 设 , 则对任意都成立, 这与有一个解矛盾, 故至少有一个解. 综上, 只有一个解. 当取遍的完全剩余系时, 的3次剩余也取遍的完全剩余系, 故定理成立. 当 时候 还有以下一些结论：推论1. 1. 1（1）如果满足, , 且, , , 则有. 证明：由上述条件易知, , 即为满足的两个不同解. 而由可知. 故也满足. 而又由于只有两个解, 均不可能, 故. 推论1. 1. 1(2) 如果满足, 且, 则, . 证明：当满足且时, 满足, 故 又 , 即. 证毕. 推论 1. 1. 1(3) 如果满足, , 且, , , , 则. 证明：由推论1. 1. 1（1）得, . 如果, 则由推论1. 1. 1（2）, , 由于, 故且, 这与只有解, 且矛盾, 故必有, 故, 故 . 1. 1. 2 当为大于等于5的奇质数时可以得出类似的结论：定理1. 1. 2（1） 当时 , 恒成立; 当时, 在的完全剩余系中只有个使. 证明：当时, , 故有个不同的解, 除了之外还有个解, , , , , 即. 在上式同时乘以, 其中满足, 则. 即得到剩下的组剩余. 因此p的次剩余有个. 当时, 有. 先来证明一个引理：引理1. 1. 2（1）对于的质因数, 必定有. 证明：必定满足且. 由于是质数, 故有又由于是质数, 故, 即. 证毕. 假设还有其他解, 即满足, 则. 由引理1. 1. 2（1）可得, 这与题设矛盾. 故只有解. 假如有两个解, , 且, 即, 则. 因为, 所以必有解. 设此解为, 此时, 则, 因为, 故, 即有两个解, 这与只有一个解矛盾, 故至多有一个解. 假如无解, 即对任意都成立, 则 对任意都成立. 因为, 所以必有解. 设此解为, 此时, 则对任意都成立, 这与有一个解矛盾, 故至少有一个解. 综上, 只有一个解. 当取遍的完全剩余系时, 的次剩余也取遍的完全剩余系, 故定理成立. 对于1.1.1中的推论也可以进行推广：推论1. 1. 2（1）如果满足, , , 且, , , , , 则有, , , (这里只是表示存在这样的关系, 但不一定依此顺序). 证明：由上述条件易知即为满足的个不同的解. 而由可知, , , , 故也满足. 而又由于只有个解, 对且, 及对, 且, 均不可能, 故有, , , . 证毕. 推论1. 1. 2（2）如果满足, , , 且, , , , , 则. 证明：由推论1. 1. 2（1）可得 . 1. 2 当为时当为时, 由于, 即的完全剩余系的前半部分与后半部分的次剩余一一对应相等. 因此在讨论时, 只需要考虑的完全剩余系的前半部分的次剩余. 1. 2. 1当时 此时即为熟悉的平方剩余, 有关它的理论已经十分完备了, 这里再添加几点. 定理1. 2. 1（1）对于任意的 , 且, 都有. 当时, 对于任意的, , 且, 都有. 当时, 对于任意的, 都存在, 且, 使得 . 证明：假设存在, 且 , 使得, 则, 由于, 故, , 这与矛盾, 故不存在 , , 使得. 假设存在, 且, 使得, 则, 由于是奇质数, 故; 反之, 当时, . 如果有, 则有, 而, 即. 证毕. 由上可知, 当时, 的平方剩余的绝对值能够遍布的完全剩余的前半部分, 但相反数不会同时成为其剩余. 而当时, 的平方剩余的绝对值不能遍布的完全剩余系的前半部分, 但相反数总是同时出现在的剩余中. 由于, 故可得到以下推论：推论1.2.1（1）当时, . 当时, . 即. 特殊地, 当时, 有. 定理1. 2. 1（2）当时, ；当时, 或 . 证明：当时, , 即一定有解. 当时, , 即也是的平方剩余, 又1也是的平方剩余, 因此都是的平方剩余. 当时, , 即一定有解. 根据定理1. 1. 1（2）, 也有解. 当时, , 即也是的平方剩余, 又1, -1也是的平方剩余, 因此都是的平方剩余. 、或不是当、时的必要条件, 它与Mersenne质数息息相关, 但它也与Mersenne质数一样, 规律难以捉摸. 定理1. 2. 1（3）或, 或, 或, 或, 或. 证明：由Gauss引理, 当为奇质数时, , 其中. 当时, , 又当时, , 故的值为或. , , . . 当时, , 当时, 有. 当时, , 当时, 有. 综上, 或. 当时, , 又当时, , 故的值为或或. , , , . 当时, , 当时, 有. 当时, , 当时, 有, 这与是个奇质数矛盾. 当时, , 当时, 有, 同理, 矛盾. 当时, , 当时, 有. 综上, 或. 当时, , 又当时, , 故的值为0或1或2或3. , . , , 当时, , 有. 当时, , 有.当时, , 有. 当时, . 有当时, . 有当时, , 有. 综上, 或, 或, 或. 根据以上的讨论, 似乎可以猜想更一般的结论：猜想1.2.1（1）假设是个奇质数, 则当时, , 其中, 当时, , 其中. 当时, 根据二次互反律, 有, 则且或且, 而当时, , 故. 这个结论或许跟定理1.2.1（2）有关, 但定理1.2.1（2）并没有完整地解决. 1. 2. 2 当时对于, 关于的可解性, 有以下结论：定理1.2.2（1）当时, 有. 证明：由定理 1. 2. 1（1）可知, 当时, 的平方剩余的绝对值能够取遍的完全剩余系的前半部分, 而的四次剩余即为的平方剩余的平方剩余, 所以的四次剩余即为的完全剩余系的前半部分的平方剩余. 即为的平方剩余, 即. 同理可得, , , . 由归纳法原理可知, . 当时的平方剩余中相反数总是同时出现. 但, 故当增加时, 次剩余中的相反数在次剩余中会归为同一值, 但这并不一定会导致高次剩余中相反数的消失. 下面即要证明：定理1.2.2（2）当时, 对于任意的 都存在使得证明：先来证明两个引理：引理1.2.2（1）. 证明：当时, , 此时引理成立. 假设当时引理成立, 即此时有. 则当时, 即此时引理也成立. 综上, 引理成立. 引理1.2.2（2）如果, 则对于的质因数一定有证明：如果, , 则假如可分解为, 其中, , 其中且是使同余式成立的最大正整数, 则. 因为都为奇数, 故也是奇数, 故是使成立的最小值, 故, 引理成立. 当均为奇数时, , 则, 当时有, , , . 当一为奇数, 一为偶数时, , 故. 当均为偶数时, 设, 其中都为奇数, 且, 则. 如果, 则归结到的情形, 如果, 则归结到的情形, 总之都有. 综上, 当时, 有. 反之, 当时, 如果有, 则由后文将要推广的Euler判别法可知, 而由于, 故, 故, 即也有解, 即存在, 使得. 证毕. 1. 3当为时 (为奇质数)类似于前面对的讨论, 可以得出当时的一些性质. 由于奇偶次幂对相反数的影响不同而导致性质略有不同. 当时的情形已与1. 1中讨论完毕. 这里总假定. 定理 1. 3. 1（1）当时, 恒成立. 证明：当时, 根据定理, 的次剩余等于的完全剩余系, 而的次剩余等于的次剩余的次剩余, 即等于的完全剩余系的次剩余, 仍为的完全剩余系. 根据归纳法原理, 可知的次剩余都等于的完全剩余系. 即定理 1. 3. 1（2）当但时, 当时, 有. 证明：当但时, 设, 其中. 如果存在, 使得（即）但, 则由于uyu立。保留着，则由, 得或, 均矛盾, 故若有, 则必有. 如果有但, 则设, 则., 而故, 而, 则, 由前面的引理, 有, 矛盾, 故当时, 有. 类似地可以证明, 当时, 如果有, 则在的大于次剩余中, 不同的剩余仍然保留着互异性, 故原命题成立. 1. 4 当为大于等于2的正整数时现在把推广到一般大于等于2的正整数, 设, 易知的必要条件是对且, 都有. 否则, 假如, 即无解, 则亦无解. 其中. 下面将要证明这也是它的充分条件. 定理1. 4（1）（）的充要条件是对且, 都有. 证明：必要性已经证明, 下面证明充分性. 首先证明一个引理. 引理1.4(1)如果, , 即, 都有解, 且, 则 即也有解. 证明：当时, 一定有解, 不妨设解为, 记, , 其中是使的正整数, 因为有解, 所以也有解, 同理, 也有解, 因而, 即有解. 引理很容易进行推广：如果, , , , 且两两互质, , 则. 现在回到原来的问题, 因为两两互质, 故原命题成立. 2. 符号的性质上文只是讨论了当取不同值时的可解性, 下面讨论一下符号的性质. 显然有, , 并且当时, 有. 容易推广以下的Euler判别法：定理2（1）当时, , . 证明：当时, 如果有解为, 则 , 即; 反之, 当 时, 为方程的一个解. 由于上方程至多有个解, 故即为其全部解. 而必与其中一同余, 即有解. 当时, 当时, , 所以；反之, 当时, 易知, 故. 在二次剩余中有, 这在高次剩余中不一定成立, 接下来即要证明：定理2（2）的必要条件为. 证明：当, 时, 设的解为, 的解为, 则, 即也有解, 即. 此时成立. 当时, 设的解为, 假如有解, 设解为, 即, 故, . 因为有解, 且与都能取遍的完全剩余系, 故由可知一定有解, 故. 又因为无解, 故由 可知无解, 故. 矛盾. 故无解, 即. 此时成立. 当时, 假如有解, 设解为, 即, 则, . 由于, 无解, 故无解, 故.此时, 成立. 但不是的充分条件. 值得注意的是, 当时, 有恒成立, 此时有, 如果是的充要条件, 则使这一性质走向了统一. 致谢感谢施洪亮老师