Sum of GCDs

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

Details and assumptions

  • You may refer to this list of primes.

  • As an explicit example, when \(n=3,\) we have \[\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...