数学中国

 找回密码
 注册
搜索
热搜: 活动 交友 discuz
查看: 13299|回复: 28

是否有整数 M,N 使得对任何整数 a,b 都有 aM≡b(mod N) ,bM≡a(mod N) ?

[复制链接]
发表于 2021-8-11 12:22 | 显示全部楼层 |阅读模式
(axM)%N=b
(bxM)%N=a

求解是否存在这样的 M 和 N,可以使上面等式成立?如果可以的话能找到这样的 M 和 N ?

本人码农一枚,对比较深奥的数论知识不太懂
发表于 2021-8-11 13:47 | 显示全部楼层
1 N>a  N>b  且 M=kN+1  就能满足
回复 支持 反对

使用道具 举报

 楼主| 发表于 2021-8-11 14:15 | 显示全部楼层
想了解可以运用什么知识可以推算出来?
回复 支持 反对

使用道具 举报

 楼主| 发表于 2021-8-11 14:27 | 显示全部楼层
lihp2020 发表于 2021-8-11 13:47
1 N>a  N>b  且 M=kN+1  就能满足

按照你的推论,得出的M和N,会使得a等于b吧?

点评

题看错了 对不起  发表于 2021-8-11 14:41
这个是 M N 满足这样的条件 a b 可以任意了 你的问题是a b 满足什么条件 M N 可以任意?  发表于 2021-8-11 14:40
回复 支持 反对

使用道具 举报

发表于 2021-8-11 15:40 | 显示全部楼层
题看错了 看成了
(axM)%N=a
(bxM)%N=b


原题 还是 有  N>a  N>b  M 每a*b/gdb(a,b)N  为周期  你也是程序员   就在M在 0~a*b/gdb(a,b) 遍历 找一个结果  就可以 了

提示 当gdb(a,b) ~=1  很有可能无解

点评

另外好奇问一下,gdb是什么函数?  发表于 2021-8-11 16:22
回复 支持 反对

使用道具 举报

 楼主| 发表于 2021-8-11 16:21 | 显示全部楼层
lihp2020 发表于 2021-8-11 15:40
题看错了 看成了
(axM)%N=a
(bxM)%N=b

或许我说的题意还未够清晰,我再补充说一下。

我之前看到别人的论文中(不记得哪里了),有用到特定数字的M和N,然后可以使题目中的式子成立,a和b只是代替数字,我希望找到找到这样的M和N,以及更加想知道这是怎样的数学关系。

另外,我还记得注释中要求了a必须要少于N,以及,应用场景都在整数内。

这种关系直白说就是,通过特定的计算,得出一个数的余数,然后再通过这个余数用同样的计算方法恢复原来的数。
回复 支持 反对

使用道具 举报

发表于 2021-8-11 17:20 | 显示全部楼层
意思 a b是确定的值   只是你为了说明问题 用了 ab 代替 原题可能是

4M%N=5 5M%N =4  求一个 M N 或者MN满足什么关系?
回复 支持 反对

使用道具 举报

发表于 2021-8-11 18:41 | 显示全部楼层
\(aM\equiv b\pmod{N}\)
\(bM\equiv a\pmod{N}\)

\(M\equiv a^{-1} b\equiv ab^{-1}\pmod{N}\)
\(a^2\equiv b^2\pmod{N}\)
\(a\equiv \pm b\pmod{N}\)

\(M\equiv \pm 1\pmod{N}\)
\(N\mid (a\mp b)\)

\(a=4,~b=5\)
\(4(1)\equiv 5\pmod{1}\)
\(5(1)\equiv 4\pmod{1}\)
\(4(-1)\equiv 5\pmod{9}\)
\(5(-1)\equiv 4\pmod{9}\)

\(a=7,~b=5\)
\(7(1)\equiv 5\pmod{2}\)
\(5(1)\equiv 7\pmod{2}\)
\(7(-1)\equiv 5\pmod{12}\)
\(5(-1)\equiv 7\pmod{12}\)

点评

不明觉厉。不过看后面的例子,这好像是确定了ab得出MN?与题意不是符合  发表于 2021-8-12 10:37
回复 支持 1 反对 0

使用道具 举报

发表于 2021-8-11 20:10 | 显示全部楼层
本帖最后由 simpley 于 2021-8-11 12:11 编辑

m=b(a的逆)=a(b的逆)(mod n)
m的平方=b(a的逆)*a(b的逆)=1(mod n)
这就是m,n的关系
回复 支持 1 反对 0

使用道具 举报

发表于 2021-8-11 20:38 | 显示全部楼层
如果要求解mx=b(mod n),直接计算就可以,不必用上面的关系式
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 注册

本版积分规则

Archiver|手机版|小黑屋|数学中国 ( 京ICP备05040119号 )

GMT+8, 2025-7-11 03:21 , Processed in 0.130266 second(s), 16 queries .

Powered by Discuz! X3.4

Copyright © 2001-2020, Tencent Cloud.

快速回复 返回顶部 返回列表