V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
Raven316
V2EX  ›  问与答

一个质数相关的问题

  •  
  •   Raven316 · 2019-10-31 19:50:10 +08:00 · 1018 次点击
    这是一个创建于 1610 天前的主题,其中的信息可能已经有所发展或是发生改变。
    假如一个质数 p,一个整数 n 小于 p,那么 0,1,2,3,...,n-1 分别乘以 p 对 n 取模,是不是还是得到 0,1,2,3,..,n-1,只是顺序不同了。

    比如:0,7,14,21,28 对 5 取模,0,2,4,1,3.

    我觉得是正确的,就是不知道怎么证明
    8 条回复    2019-11-01 04:54:17 +08:00
    Raven316
        1
    Raven316  
    OP
       2019-10-31 20:10:44 +08:00
    顶下。。。
    lvybupt
        2
    lvybupt  
       2019-10-31 20:28:35 +08:00   ❤️ 1
    对的。 简单证明一下, 如果 不是 n-1 个不同数,有 a,b 相同。那么有 ap - bp = qn。st. (a-b)p = qn 显然 a-b<n,若 a-b/=0 那么 n 的分解中,含有 p 的因子,与 p 是素数矛盾。
    lvybupt
        3
    lvybupt  
       2019-10-31 20:29:30 +08:00
    随便打的,文字不严谨,意思自己参考一下哈。
    Raven316
        4
    Raven316  
    OP
       2019-10-31 20:34:05 +08:00
    若 a-b/=0 那么 n 的分解中,含有 p 的因子,与 p 是素数矛盾。

    这一点还是没明白
    lvybupt
        5
    lvybupt  
       2019-10-31 20:36:14 +08:00
    p = q n /( a-b )与 p 是素数矛盾。这次呢?
    PonysDad
        6
    PonysDad  
       2019-10-31 20:40:28 +08:00
    线性同余问题
    PonysDad
        7
    PonysDad  
       2019-10-31 20:42:29 +08:00
    列个线性同余方程就解就可以了
    msg7086
        8
    msg7086  
       2019-11-01 04:54:17 +08:00
    反证法。
    任取 a 和 b,令 Ya = a * p mod n ; Yb = b * p mod n ;假设 a < b && Ya = Yb。

    因为 p 和 n 没有公因数,所以
    Ya = a * p mod n
    = (a * p + x * n) mod n ( x 是整数)

    因为 Ya = Yb,所以有
    a * p + x * n = b * p
    x = (b - a) / p

    因为 x 是整数,所以 b - a 是 p 的倍数,因为 a < b 所以 b >= a + p。所以若 a、b 取值小于 p,就不可能得到 Ya = Yb,也就不可能重复。

    (瞎打的,不太严谨,但是过程应该没错。)
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   5949 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 27ms · UTC 02:08 · PVG 10:08 · LAX 19:08 · JFK 22:08
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.