0%

Problem 515


Problem 515


Dissonant Numbers

Let d(p,n,0) be the multiplicative inverse of n modulo prime p, defined as n × d(p,n,0) = 1 mod p.

Let d(p,n,k) = $\Sigma^n_{i=1}$d(p,i,k?1) for k ≥ 1.

Let D(a,b,k) = $\Sigma$(d(p,p-1,k) mod p) for all primes a ≤ p < a + b.

You are given:

  • D(101,1,10) = 45
  • D(103,102,102) = 8334
  • D(106,103,103) = 38162302

Find D(109,105,105).


不和谐的数

记d(p,n,0)是n在模素数p同余下的乘法逆元,即n × d(p,n,0) = 1 mod p。

记d(p,n,k) = $\Sigma^n_{i=1}$d(p,i,k?1),其中k ≥ 1。

记D(a,b,k) = $\Sigma$(d(p,p-1,k) mod p),对于所有的素数a ≤ p < a + b。

已知:

  • D(101,1,10) = 45
  • D(103,102,102) = 8334
  • D(106,103,103) = 38162302

求D(109,105,105)。