# 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.

×