Sum of GCDs
Number Theory
Level
4
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.
by
Sreejato Bhattacharya