Sum of GCDs

A positive integer nn is called ingenious if m=1ngcd(m,n) \displaystyle\sum_{m=1}^{n} \gcd (m,n) is a prime. Find the number of ingenious integers between 33 and 100100 (inclusive).

Details and assumptions

  • You may refer to this list of primes.

  • As an explicit example, when n=3,n=3, we have m=13gcd(m,3)=gcd(1,3)+gcd(2,3)+gcd(3,3)=5,\displaystyle\sum_{m=1}^{3} \gcd (m, 3) = \gcd (1, 3) + \gcd (2, 3) + \gcd (3, 3)= 5, which is a prime.

  • This problem was inspired by IMOSL 2004 N2.

×

Problem Loading...

Note Loading...

Set Loading...