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

dxkrs

(axM)%N=b
(bxM)%N=a

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

本人码农一枚，对比较深奥的数论知识不太懂

lihp2020

1 N>a  N>b  且 M=kN+1  就能满足

dxkrs

想了解可以运用什么知识可以推算出来？

dxkrs

lihp2020 发表于 2021-8-11 13:47
1 N>a  N>b  且 M=kN+1  就能满足

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

lihp2020

题看错了 看成了
(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  很有可能无解

dxkrs

lihp2020 发表于 2021-8-11 15:40
题看错了 看成了
(axM)%N=a
(bxM)%N=b

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

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

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

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

lihp2020

意思 a b是确定的值   只是你为了说明问题 用了 ab 代替 原题可能是

4M%N=5 5M%N =4  求一个 M N 或者MN满足什么关系？

fungarwai

\(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}\)

simpley

m=b(a的逆)=a(b的逆)(mod n)
m的平方=b(a的逆)*a(b的逆)=1(mod n)
这就是m,n的关系

simpley

如果要求解mx=b(mod n),直接计算就可以，不必用上面的关系式