数学中国

 找回密码
 注册
搜索
热搜: 活动 交友 discuz
123
返回列表 发新帖
楼主: dxkrs

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

[复制链接]
发表于 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
回复 支持 反对

使用道具 举报

 楼主| 发表于 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都可以任意取?
回复 支持 反对

使用道具 举报

发表于 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}
回复 支持 反对

使用道具 举报

发表于 2021-8-14 01:19 | 显示全部楼层
只要 (M+ 1)(M-1) 是 N 的倍数就可以了。

点评

谢谢,原来如此。  发表于 2021-8-14 22:09
回复 支持 1 反对 0

使用道具 举报

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

本版积分规则

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

GMT+8, 2025-7-11 01:24 , Processed in 0.090089 second(s), 14 queries .

Powered by Discuz! X3.4

Copyright © 2001-2020, Tencent Cloud.

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