数论吧 关注:13,691贴子:77,230
  • 3回复贴,共1

x^17 ≡ 2790 (mod 3233)

只看楼主收藏回复

怎么判断x是否有解,有几个解?这个应该怎么算,套用什么公司,请教详细过程


IP属地:美国1楼2019-01-16 16:28回复
    该楼层疑似违规已被系统折叠 查看此楼


    IP属地:北京来自Android客户端2楼2019-01-16 20:21
    回复
      具体过程
      (1) 3233=53×61 φ(3233)=52×60=3120
      (2) 3120=183×17+9
      17=2×9-1

      所以 1=2×9-17=2×(3120-183×17 )-17=2×3120-367×17
      所以 1/17 mod 3120=-367 mod 3120=2753 mod 3120
      (3) 2753×17=3120×15+1
      按模幂算法计算
      x=x^(3120×15+1)=x^(17×2753)=2790^2753=2790×2269^1376
      =2790×1425^688=2790×301^344=2790×^172=2790×2696^86=2790×632^43
      =1295×632^42=1295×1765^21=3177×1765^20=3177×1846^10=3177×134^5=2195×134^4=2195×1791^2=2195×545=65(mod3233)


      IP属地:北京本楼含有高级字体3楼2019-01-16 20:35
      回复
        该楼层疑似违规已被系统折叠 查看此楼


        IP属地:山东来自iPhone客户端4楼2019-02-12 15:32
        回复