Sum of GCDs

Define $f(x) = \displaystyle \sum_{i=1}^{x} \gcd (i,x).$

Lemma 1: Let $a,b$ be two coprime positive integers. Then for all $1 \leq m \leq a, 1 \leq n \leq b,$ there exists a unique $1 \leq r \leq ab$ such that $\gcd (r, ab)= \gcd (m,a) \gcd (n, b).$

Proof: Consider the system of congruencies $\begin{cases} x \equiv m \pmod{a} \\ x \equiv n \pmod{b}. \end{cases}$
By CRT, this system has a unique solution mod $ab,$ i.e. $x \equiv r \pmod{ab}$ for some $1 \leq r \leq ab.$ Then, note that $\begin{array}{lcl} \gcd (r, ab) & = & \gcd (r, a) \gcd (r, b) \\ & = & \gcd (m, a) \gcd (n, b), \end{array}$ where we have used the fact that $\gcd (p, qr)= \gcd (p,q) \gcd (p,r)$ for all coprime integers $q,r$ and the division algorithm. Conversely, if $\gcd (r, ab)= \gcd (m,a) \gcd (n,b),$ $r$ must satisfy $r\equiv m \pmod{a}, r \equiv n \pmod{b},$ so $r$ is unique. $\blacksquare$

---

Lemma 2: $f(ab)= f(a)f(b)$ for all coprime positive integers $a, b.$

Proof: Note that \begin{array}{lcl} f(a)f(b) & = & \left( \displaystyle \sum_{i=1}^{a} \gcd (m, i) \right) \left( \displaystyle \sum_{j=1}^{b} \gcd (n, j) \right) \\ & = & \displaystyle \sum_{\substack{1 \leq i \leq a \\ 1 \leq j \leq b}} \gcd (i, a) \gcd (j, b) \\ & = & \displaystyle \sum_{1 \leq r \leq ab} \gcd (r, ab) \\ & = & f(ab), \end{array} where the last step follows from lemma 1.

---

Lemma 3: If $p$ is a prime and $k \in \mathbb{N},$ $f \left( p^k \right) = p^{a-1} (a(p-1)+p).$

Proof: Note that the only divisors of $p^k$ are of the form $p^x$ for some $x \in \mathbb{Z^+}.$ For any divisor of the form $p^x,$ we get precisely $\varphi \left( \dfrac{p^k}{p^x} \right)$ numbers $n$ between $1$ to $p^k$ such that $\gcd \left(n, p^k \right) = p^x.$ Using these facts, we can evaluate the sum as $\begin{array}{lcl} f\left(p^k\right) & = & \displaystyle \sum_{0 \leq x \leq k} p^x \varphi \left( p^{k-x} \right ) \\ & =& \displaystyle \sum_{0 \leq x < k} p^{k-1} (p-1) + p^k \\ & = & p^{k-1} (k(p-1)+p), \end{array}$ where we have used the well known fact $\varphi \left ( p^{k-x} \right ) = p^{k-x} \left( 1 - \dfrac{1}{p} \right ) = p^{k-x-1} (p-1).$ $\blacksquare$

---

Using these lemmas, if $n$ is composite, $n$ cannot be ingenious. If $n$ is prime, $f(n)= 2n-1.$ So for $n$ to be ingenious, both $n$ and $2n-1$ have to be primes. A quick search through the list shows that there are $\boxed{7}$ such numbers between $3$ and $100,$ which is our answer. We can omit the primes $>3$ which are $\equiv 2 \pmod{3},$ which makes the search faster.

I did it manually 3,7,19,31,37,79,97 are such numbers

Sreejato Bhattacharya 's lemma proves to be false for b=12 and a=6. The lemma is true if b=an, where gcd(a,n)=1. Generally speaking if f(n) if the sum of gcd(m,n) where m<=n, then f is a multiplicative number theoretic function, i.e f(a,b)=f(a)f(b) whenever gcd(a,b)=1 and f(1)=1.

We use two lemmas that we cite without proof.

Lemma 1: For an arbitrary function $f(n)$ defined over the naturals, we have $\displaystyle \sum_{k=1}^nf(\gcd(n,k)) = \sum_{d|n}f(d)\varphi\left(\frac{n}{d}\right)$ where $\varphi(n)$ is the euler totient function.

Lemma 2: The dirichlet convolution of two multiplicative functions is multiplicative.

In other words, if $f(n)$ and $g(n)$ are multiplicative, then $h(n) =\displaystyle \sum_{d|n}f(d)g\left(\frac{n} {d}\right)$ is a multiplicative function.

Now, the given function is just what happens when our $f(n)$ in lemma 1 is equal to $n$ .

Thus, we get $\displaystyle \sum_{m=1}^n\gcd(m,n) = \sum_{d|n}d\varphi\left(\frac{n}{d}\right).$ Since the latter is function is multiplicative by lemma 2 , it suffices to check the primes.

We now want to find the number of primes $p$ between $3$ and $100$ such that $2p-1$ is also prime. Note that such primes must be congruent to $1 \bmod 6$ . Doing casework we get the correct answer of $7$ .

This sum is the same as the sum of d*phi(n/d) over all divisors of n. If we divide this sum by n we get. the sum of phi(d)/d for all divisors of n. When we expand this in terms of primes we get something that is factorable. It factors as the product of ((m(p-1)+p)/p) over all p that divide n, and where m is the maximum power of p that divides n. Now to get back the original sum we multiply this product by n to get the product of ( p^(m-1))(m(p-1)+p) it is obvious that this can only be prime if m=1 and there is only one prime in the product. So n must be a prime number. In this case the product reduces to just evaluating (p^(1-1)) ((p-1)+p). So this whole thing reduces down to 2p-1. At this point we simply need to check how many primes less than one hundred have the property that twice them minus 1 is also prime. We obtain the list 3,7,19,31,37,79,97, for a total of 7 numbers.

java code:

public class brilliant201409091923{
    public static void main(String[] args){
        int count = 0;
        for(int i=3;i<=100;i++){
            int sum = 0;
            for(int j=1;j<=i;j++){
                sum += gcd(j,i);
            }
            if(isPrime(sum)){
                count++;
            }
        }
        System.out.println(count);
    }
    private static int gcd(int a,int b){
        if(a==0) return b;
        return gcd(b,Math.abs(a-b));
    }
    private static boolean isPrime(int p){
        for(int i=2;i<=Math.sqrt(p);i++){
            if(p%i==0) return false;
        }
        return true;
    }
}

output:

7
Press any key to continue . . .

Python code:

from fractions import gcd

def checkprime(n):

s=0

for i in range(2,n/2):

    if n%i==0:

        s=s+1

if s==0:

    return 0

else:

    return 1

count=0

for n in range(3,101):

s1=0

for m in range(1,n+1):

    p=gcd(m,n)

    s1=s1+p

if checkprime(s1)==0:

    count=count+1

print count