4
$\begingroup$

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]
$\endgroup$
3
  • 1
    $\begingroup$ The smallest counterexample is $41124$. $\endgroup$ – Vepir Feb 21 at 12:22
  • $\begingroup$ @Vepir surprising, thanks, you may put it as ans too $\endgroup$ – Pruthviraj Feb 21 at 12:29
  • 1
    $\begingroup$ 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".) $\endgroup$ – Vepir Feb 21 at 14:04
2
$\begingroup$

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])))
$\endgroup$
5
$\begingroup$

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.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.