初等数论吧 关注:857贴子:2,615
  • 10回复贴,共1

问题A54:如果一个自然数n满足以下条件,我们就称n是好数:

只看楼主收藏回复

问题A54:如果一个自然数n满足以下条件,我们就称n是好数:“对任意整数a,当n|a^n-1时,必然有n^2|a^n-1。”
①证明所有素数都是好数;
②证明有无穷多个合数是好数。


来自iPhone客户端1楼2020-02-12 22:54回复
    对任何素数p和任意给定的整数b,如果整数a使a^p-b^p是p的倍数,那a^p-b^p 一定也是p² 的倍数
    理由:
    ⑴当p=2,a²-b²是偶数
    要么a, b都是偶数,则a², b²都是4的倍数,要么a, b都是奇数,则a²≡b²≡1(mod 8),都会得到 4整除a²-b²
    ⑵当p 是奇素数,设a-b=t,a^p-b^p =(t+b)^p-b^p ≡ t^p (mod p)
    如果p整除a^p-b^p,则p整除t
    而a^p= (t+b)^p≡pb^(p-1)×t+b^p (mod t²)
    所以当p 整除t 时,a^p≡pb^(p-1)×t+b^p≡b^p(mod p²),也就是p²整除a^p-b^p


    IP属地:安徽来自Android客户端2楼2024-04-10 20:38
    收起回复
      2025-06-25 18:10:45
      广告
      同理,对任何无平方因子数 (不同素数的乘积) m和对任意给定的整数b,如果整数a使a^m-b^m是m的倍数,那a^m-b^m一定也是m²的倍数
      理由:
      如果p是m的素因子,设m=kp
      a^m-b^m是m的倍数,那也是p的倍数,相当于(a^k)^p-(b^k)^p 是p的倍数
      所以(a^k)^p-(b^k)^p 也是p²的倍数
      对m的每个素因子p,a^m-b^m都是p²的倍数,那a^m-b^m是∏p²的倍数,相当于a^m-b^m是m²的倍数


      IP属地:安徽来自Android客户端3楼2024-04-10 20:47
      回复
        另外,当m有大于4的平方因子时,对任何与m互素的整数b,都存在整数a使a^m-b^m是m的倍数而不是m²的倍数
        可以设m的所有素因子乘积为n,取a=b+n或a=b+2n,由LTE引理 (对奇素数和2分开讨论) ,两种情况都能满足m整除a^m-b^m
        并且
        ①如果奇素数p^α ℓℓ m, α≥2,那p^(α+1)ℓℓa^m-b^m,由于 α+1<2α,所以p^(2α)不整除 a^m-b^m,也就说明m²不整除a^m-b^m
        ②如果 2^α ℓℓ m, α≥3,取a=b+2n,由于b与m互素是奇数,则4 ℓℓ a-b, 2ℓℓ a+b
        所以ν2(a^m-b^m) = ν2(a²-b²)+ν2(m)-1 = 2+α < 2α ,2^(2α)不整除a^m-b^m,所以m²也不整除a^m-b^m


        IP属地:安徽来自Android客户端4楼2024-04-13 22:06
        回复
          最后如果a⁴-b⁴是4的倍数,那a⁴-b⁴一定也是16的倍数
          类似3楼的过程可以说明,当m=4×p₁×p₂×…×p(k),p₁, …, p(k)是不同奇素数时,如果a^m-b^m是m的倍数,那一定也是m²的倍数


          IP属地:安徽来自Android客户端5楼2024-04-13 22:09
          收起回复