数论吧 关注:13,627贴子:76,929
  • 1回复贴,共1

求助一道题

只看楼主收藏回复

n是大于二的整数 Sn是[lbk]1.n[rbk]中与n互素的元素和Tn是区间里余下的元素即不与n互素的元素的和若 n|Sn-Tn 求n表达式


IP属地:安徽来自Android客户端1楼2024-06-28 19:32回复
    1~n中与n互素的整数一共有φ(n)个,φ(n)是欧拉函数
    n≥2时,对1~n中每一个和n互素的整数i,n-i也是1~n中和n互素的整数
    这样用倒序相加法可以求出来Sn= n×φ(n)/2
    所以 Tn= n(n+1)/2 - Sn = n×(n+1-φ(n))/2
    Sn-Tn = n×(2φ(n)-n-1)/2
    如果 n ℓ Sn-Tn,只需要 2φ(n)-n-1 是偶数就可以,也就是n可以取所有大于1的奇数


    IP属地:北京来自Android客户端2楼2024-06-28 19:44
    回复