3
$\begingroup$

I feel like it's true as for small cases I couldn't find counterexample.

In general, whether it's true that if we have prime number, $p_{1}, p_{2},\dotsc, p_{k}$ and $n=p_{1}p_{2}p_{3}\dotsb p_{k}$ then at least for one $ i \in\{1, 2, \dotsc, k\}$, $p_i$ divides $1^{n-1} +2^{n-1} + \dotsb + (p_{i}-1) ^{n-1}$? Each prime is greater than or equal to 3.

Improve this question
$\endgroup$
3
  • $\begingroup$ @GH from MO yeah, I corrected it. $\endgroup$
    – Raj Pratap Singh
    Commented Oct 31, 2023 at 16:40
  • 2
    $\begingroup$ The title and the text do not agree. $\endgroup$
    – Gerald Edgar
    Commented Oct 31, 2023 at 16:53
  • $\begingroup$ The conjecture is not true in general, the counterexamples $n$ are precisely the Carmichael numbers. See my post below. $\endgroup$
    – GH from MO
    Commented Oct 31, 2023 at 20:22

2 Answers 2

Reset to default
6
$\begingroup$

For a prime $p$, $p$ divides $\sum_{i=1}^{p-1}i^k$ if and only if $p-1$ does not divide $k$.

For completeness, here is a one-line proof: if $k$ is divisible by $p-1$, then all $p-1$ terms are congruent to 1 modulo $p$. Otherwise we induct on $r:=k \pmod {p-1}$ summing up the identity $(x+1)^{r+1}-x^{r+1}=(r+1)x^r+...+1$ over $x=0,1,\ldots,p-1$.

Thus, for two primes you may simply suppose that $p_1<p_2$, then $p_1p_2-1\equiv p_1-1 \pmod{p_2-1}$ is not divisible by $p_2-1$.

Improve this answer
$\endgroup$
5
  • 3
    $\begingroup$ Can you give a reference for the first sentence? $\endgroup$
    – GH from MO
    Commented Oct 31, 2023 at 19:09
  • 5
    $\begingroup$ I see, if $p-1$ does not divide $k$, then picking a primitive root $g\bmod p$, we have $g^k\not\equiv 1\pmod{p}$, while the sum multiplied by $g^k$ is congruent to itself mod $p$, whence the sum is in fact divisible by $p$. $\endgroup$
    – GH from MO
    Commented Oct 31, 2023 at 19:14
  • 3
    $\begingroup$ @GHfromMO For a reference, see e.g. Problem 8.2.12 in the 7th edition of Burton's Elementary Number Theory (it's a standard exercise on primitive roots). $\endgroup$
    – Salvo Tringali
    Commented Oct 31, 2023 at 19:15
  • $\begingroup$ @SalvoTringali Yes, I figured this out while preparing my dinner. See my comment before yours. $\endgroup$
    – GH from MO
    Commented Oct 31, 2023 at 19:15
  • 2
    $\begingroup$ The counterexamples to the original conjecture are precisely the Carmichael numbers (and they have at least 3 prime factors). $\endgroup$
    – GH from MO
    Commented Oct 31, 2023 at 20:16
4
$\begingroup$

By Fedor Petrov's answer and Korselt's criterion, the distinct primes $p_1,\dotsc,p_k$ provide a counterexample to the OP's conjecture if and only if their product $n$ is a Carmichael number. For example, the triple $p_1=3$, $p_2=11$, $p_3=17$ provides a counterexample, because their product $n=561$ is a Carmichael number.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ @above thanks for your effort. It's very much appreciated. $\endgroup$
    – Raj Pratap Singh
    Commented Nov 1, 2023 at 2:12

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .