# Show that $\sum_{k=1}^{a-1}(k,a)\equiv0\pmod{a-1}\iff a$ is prime

Denote $$\gcd(a,b)$$ as $$(a,b)$$

Let $$a\ge 2$$, can it be shown that

$$(1,a)+(2,a)+\cdots+(a-1,a)\equiv0\pmod{a-1}$$

Satisfy if and only if $$a$$ is prime?

Clearly if $$a$$ is prime then $$(1,a)+(2,a)+\cdots+(a-1,a)\equiv1+1+\cdots +1\equiv a-1\equiv0\pmod{a-1}$$

Claim's hold true upto $$10^4$$ source code Pari GP

forcomposite(a=2,10000,if(sum(k=1,a-1,gcd(k,a))%(a-1)==0,print([a])))


Update #1

Sequence1 for composite $$a$$, $$[a,\sum_{k=1}^{a-1}(k,a)\equiv\pmod{a-1}]$$

[4, 1][6, 4][8, 5][9, 4][10, 8][12, 6][14, 12][15, 2][16, 2][18, 11][20, 14][21, 4][22, 20][24, 7][25, 16][26, 24][27, 2][28, 22][30, 18][32, 18][33, 8][34, 32][35, 14][36, 27][38, 36][39, 10][40, 23][42, 30][44, 38][45, 12][46, 44][48, 4][49, 36][50, 47][51, 14][52, 46][54, 30][55, 26][56, 39][57, 16][58, 56][60, 5][62, 60][63, 24][64, 3][65, 32][66, 54][68, 62][69, 20][70, 5][72, 64][74, 72][75, 28][76, 70][77, 44][78, 66][80, 36][81, 56][82, 80][84, 21][85, 44][86, 84][87, 26][88, 71][90, 32][91, 54][92, 86][93, 28][94, 92][95, 50][96, 84][98, 10][99, 48][100, 24]

• The smallest counterexample is $41124$. – Vepir Feb 21 at 12:22
• @Vepir surprising, thanks, you may put it as ans too – Pruthviraj Feb 21 at 12:29
• Btw, the following modification of your conjecture $$\sum_{k=1}^{a-1}(k,a)\equiv a-1\pmod{a}\iff a \text{ prime,}$$ appears to have no small counterexamples. (See comments in A018804: "Conjecture: n>1 divides a(n)+1 iff n is prime. - Thomas Ordowski, Oct 22 2014".) – Vepir Feb 21 at 14:04

Up to $$10^8$$, there are $$4$$ counterexamples: $$41124, 230867, 358267, 37539572$$.

This was possible thanks to Thomas Andrews, where they write a formula for $$f(a)$$.

I obtained counterexamples by running the formula in PARI/GP:

forcomposite(a=2,10^8,s=0;fordiv(a,d,s+=d*eulerphi(a/d));if(s%(a-1)==1,print([a])))


Not an answer, but too long for a comment.

Adding $$a$$ to both sides means you can define:

$$f(a) =\sum_{k=1}^a (k,a)\tag 1$$

And you want $$f(a)\equiv 1\pmod{a-1}\iff a$$ is prime.

Then show that:

$$f(a)=\sum_{d\mid a} d\phi(a/d)$$

Thus $$f$$ is multiplicative.

So then compute $$f(p^n)=np^{n-1}(p-1)+p^n$$, when $$p$$ is prime.

So that gives you a general formula for $$f(a)$$ in terms of the prime factorization of $$a.$$

But I don’t see where to go from there. I’m not even sure there isn’t a counterexample.