数学吧 关注:838,806贴子:8,560,056
  • 4回复贴,共1

初等数论,为什么x=1(mod y)有解等价于x 与 y互质?

只看楼主收藏回复

我只知道下面一个定理:
对于整数a,c,当a,c互质时,存在b,使得ab=1(mod c)。
根据这个定理我怎么推也推不出来“x=1(mod y)有解等价于x 与 y互质”
——————————————
注:“=”表示同余的意思,三个横杠打不出来。


IP属地:山东来自Android客户端1楼2024-03-21 19:03回复
    裴蜀定理


    IP属地:上海来自iPhone客户端3楼2024-03-21 19:46
    回复
      …我十分好奇这个方程是关于哪个未知数的.
      按楼主所述,x和y应当是事先给定的常数,不存在所谓“有解”.
      以及,楼主所述的定理就是1L说的裴蜀定理.


      IP属地:安徽来自Android客户端4楼2024-03-21 20:40
      回复
        如果x≡1(mod y),则x=ky+1,假设x=ly,即ky+1=ly,当且仅当l=k+1,且y=1,所以x和y必定互素


        IP属地:北京来自Android客户端5楼2024-03-21 20:45
        回复
          设 x=ry+1,gcd(ry+1,y)=gcd(1,y),辗转相除。


          IP属地:浙江来自Android客户端6楼2024-03-21 20:52
          回复