数论吧 关注:11,981贴子:56,370
  • 1回复贴,共1
有没有这个引理的简洁证明或思路,两三行啥的。
这迫真答案直接给省略的,我做的还挺长的




IP属地:北京1楼2021-10-07 21:39回复
    反证 使用数学归纳法。若存在{aibi}为模 n 全系
    (1)n不能有平方因子,若n=p²m, 其中p为素数。
    注意ai=0(mod p) 时 必然 bi=0(mod p), 否则aibi中为p的倍数者会超过pm个,必然出现模n相同者。
    这样 aibi序列中不存在模n余p,因为aibi mod n 后要么不是p的倍数,要么是p²的倍数,矛盾。

    (2)n为素数时,注意ai=0,则bi=0,否则aibi中已有两个0,矛盾。
    将两个0去掉,其他的数值乘积πai=πbi=(n-1)!=-1 (mod n)
    {aibi}为模 n 全系,对应πaibi=-1 (mod n)
    而πaibi=πai πbi=-1×-1 =1 ,所以 1=-1(mod n) 只能n=2,矛盾。


    (3) n为合数时,且没有平方因子,即n=pm,其中p为n的最小素数,这样m≥3。
    仍旧考察ai=0(mod p)这些ai , 对应bi=0(mod p)。
    考察对应 {ai/p} ,{bi/p} ,由归纳假设 可知存在(ai/p)(bi/p)=(aj/p)(bj/p) mod m
    这样明显 aibi=ajbj(mod pm),矛盾。


    IP属地:北京3楼2021-10-22 15:41
    回复