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

小fisher · 发表于 2021-8-13 08:25

dxkrs 发表于 2021-8-12 17:20
可能我在帖子中，对题意表达不够完善了，我在其他楼层补充了题目的原意。原意是想找到一个正整数M，N，使 ...

事实上，任何正整数M=kN-1和N都可以使任何小于N的a，有 aM≡b(mod N) ，bM≡a(mod N) 。不信请在excel中试验一下：
a N k M b bM%N
1 123 1 122 122 1
2 123 1 122 121 2
3 123 2 245 120 3
123 200 2 399 77 123
123 300 3 899 177 123
123 400 3 1199 277 123

dxkrs · 发表于 2021-8-13 09:58

本帖最后由 dxkrs 于 2021-8-13 10:13 编辑

小fisher 发表于 2021-8-13 08:25
事实上，任何正整数M=kN-1和N都可以使任何小于N的a，有 aM≡b(mod N) ，bM≡a(mod N) 。不信请在excel中 ...

确实如19楼所说的，我搞反了M和N。你的假设是成立的。但我有个疑惑，k可以是任意数吗？比如M=77，N=1482，那么k是78/1482，是个无理数。如果K是任意取，那不就是M和N都可以任意取？

小fisher · 发表于 2021-8-13 16:55

本帖最后由小fisher 于 2021-8-13 16:58 编辑

dxkrs 发表于 2021-8-13 09:58
确实如19楼所说的，我搞反了M和N。你的假设是成立的。但我有个疑惑，k可以是任意数吗？比如M=77，N=148 ...

正如你所说，M=kN-1只是一个特例，并不是全部解，比如N=871, M=66或805也成立
通过编程遍历发现，对于任何正整数N，令M=kN+m（见下表），可使得对于任何正整数a<N, 都有aM≡b(mod N) ，bM≡a(mod N)
m与N的完整关系还没总结出来，目前只发现以下规律：
1) m值成对出现，并且两者之和为N；
2) 对于N为素数，N或N/2的非重复质因数只有1个（比如N=9, 25, 27, 49或N=54,98,162），m值只有1和N-1；
3) m+1可被N的一个因子整除；
4) m的个数似乎与N的因子个数相关；
N=3 m={1,2}
N=4 m={1,3}
N=5 m={1,4}
N=6 m={1,5}
N=7 m={1,6}
N=8 m={1,3,5,7}
N=9 m={1,8}
N=10 m={1,9}
N=11 m={1,10}
N=12 m={1,5,7,11}
N=13 m={1,12}
N=14 m={1,13}
N=15 m={1,4,11,14}
N=16 m={1,7,9,15}
N=17 m={1,16}
N=18 m={1,17}
N=19 m={1,18}
N=20 m={1,9,11,19}
N=21 m={1,8,13,20}
N=22 m={1,21}
N=23 m={1,22}
N=24 m={1,5,7,11,13,17,19,23}
N=25 m={1,24}
N=26 m={1,25}
N=27 m={1,26}
N=28 m={1,13,15,27}
N=29 m={1,28}
N=30 m={1,11,19,29}
N=31 m={1,30}
N=32 m={1,15,17,31}
N=33 m={1,10,23,32}
N=34 m={1,33}
N=35 m={1,6,29,34}
N=36 m={1,17,19,35}
N=37 m={1,36}
N=38 m={1,37}
N=39 m={1,14,25,38}
N=40 m={1,9,11,19,21,29,31,39}
N=41 m={1,40}
N=42 m={1,13,29,41}
N=43 m={1,42}
N=44 m={1,21,23,43}
N=45 m={1,19,26,44}
N=46 m={1,45}
N=47 m={1,46}
N=48 m={1,7,17,23,25,31,41,47}
N=49 m={1,48}
N=50 m={1,49}
N=51 m={1,16,35,50}
N=52 m={1,25,27,51}
N=53 m={1,52}
N=54 m={1,53}
N=55 m={1,21,34,54}
N=56 m={1,13,15,27,29,41,43,55}
N=57 m={1,20,37,56}
N=58 m={1,57}
N=59 m={1,58}
N=60 m={1,11,19,29,31,41,49,59}
N=61 m={1,60}
N=62 m={1,61}
N=63 m={1,8,55,62}
N=64 m={1,31,33,63}
N=65 m={1,14,51,64}
N=66 m={1,23,43,65}
N=67 m={1,66}
N=68 m={1,33,35,67}
N=69 m={1,22,47,68}
N=70 m={1,29,41,69}
N=71 m={1,70}
N=72 m={1,17,19,35,37,53,55,71}
N=73 m={1,72}
N=74 m={1,73}
N=75 m={1,26,49,74}
N=76 m={1,37,39,75}
N=77 m={1,34,43,76}
N=78 m={1,25,53,77}
N=79 m={1,78}
N=80 m={1,9,31,39,41,49,71,79}
N=81 m={1,80}
N=82 m={1,81}
N=83 m={1,82}
N=84 m={1,13,29,41,43,55,71,83}
N=85 m={1,16,69,84}
N=86 m={1,85}
N=87 m={1,28,59,86}
N=88 m={1,21,23,43,45,65,67,87}
N=89 m={1,88}
N=90 m={1,19,71,89}
N=91 m={1,27,64,90}
N=92 m={1,45,47,91}
N=93 m={1,32,61,92}
N=94 m={1,93}
N=95 m={1,39,56,94}
N=96 m={1,17,31,47,49,65,79,95}
N=97 m={1,96}
N=98 m={1,97}
N=99 m={1,10,89,98}
N=100 m={1,49,51,99}
N=101 m={1,100}
N=102 m={1,35,67,101}
N=103 m={1,102}
N=104 m={1,25,27,51,53,77,79,103}
N=105 m={1,29,34,41,64,71,76,104}
N=106 m={1,105}
N=107 m={1,106}
N=108 m={1,53,55,107}
N=109 m={1,108}
N=110 m={1,21,89,109}
N=111 m={1,38,73,110}
N=112 m={1,15,41,55,57,71,97,111}
N=113 m={1,112}
N=114 m={1,37,77,113}
N=115 m={1,24,91,114}
N=116 m={1,57,59,115}
N=117 m={1,53,64,116}
N=118 m={1,117}
N=119 m={1,50,69,118}
N=120 m={1,11,19,29,31,41,49,59,61,71,79,89,91,101,109,119}

luyuanhong · 发表于 2021-8-14 01:19

只要 (M+ 1)(M-1) 是 N 的倍数就可以了。

		自动登录	找回密码
密码			注册

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

点评