0
$\begingroup$

I was considering the properties of factorials in the following context:

Wilson's Theorem affords a simplistic, exact, but impractical, algorithm for the prime number counting function $\pi (n)$ because for $k\ge 5$, $(k-1)!\equiv 0 \bmod k$ if $k$ is composite, and $(k-1)!\equiv -1 \bmod k$ if $k$ is prime. The requirement for $k\ge 5$ arises because the number $4$ behaves idiosyncratically: $3!\equiv 2 \bmod 4$. Making allowance for the two primes $2,3$, we can say $$\pi (n)=2-\sum_{k=5}^n((k-1)! \bmod k)$$ For each prime greater than $3$, the sum is augmented by $-1$, and for each composite greater than $5$, $0$ is added. Adding the negative of the sum to $2$ (corresponding to the primes $2,3$) affords an exact count of primes up to $n$. Alas, this algorithm is highly inefficient due to the huge amount of computation required as $n$ increases. As a matter of minor interest, this approach yields a similar algorithm for counting composite numbers up to $n$: $$1+\sum_{k=5}^n(((k-1)! \bmod k)+1)$$ Here, the outside $1$ accounts for the composite number $4$, and the summand is $(-1+1)=0$ when $k$ is prime, and $(0+1)=1$ when $k$ is composite.

In thinking about shortcuts that might mitigate the computation of factorials, I observed (looking at several examples, using numbers small enough to permit hand calculation) that there seems always to be some positive integer $1<a<a+1<n-1$ such that $a(a+1)\equiv 0 \bmod n$ when $n$ is composite. It is plain that this relationship cannot be true when $n$ is prime. Although the relationship holds for all of the specific examples I examined, I have not been able to work out a general proof (or disproof) of the statement.

In writing this post, I found several previous questions that came close to this question but none that addressed it.

My questions are: 1. Is it true that $\exists a \ | \ (1<a<a+1<n-1)$ such that $a(a+1)\equiv 0 \bmod n$ when $n$ is composite? 2. Can anyone in the community provide a proof, disproof, or counterexample? 3. If true, is this observation already known? Where might I find literature or references about it?

$\endgroup$
  • $\begingroup$ $\!\bmod n\!:\ 0\equiv x+x^2\equiv 0\iff \color{#c00}{-x}\equiv x^2\equiv \color{#c00}{(-x)^2}\iff \color{#c00}{-x}\,$ is $\rm\color{#c00}{idempotent}$, and there are well known characterizations of such idempotents, e.g. see the dupe and many others. $\endgroup$ – Bill Dubuque Dec 17 '19 at 22:06
  • $\begingroup$ Or, equivalently, $a+1$ is idempotent. $\endgroup$ – Bill Dubuque Dec 17 '19 at 22:11
  • $\begingroup$ @Bill Dubuque So I guess my question boils down to for composite $n$ (other than $4$), is there always an idempotent? $\endgroup$ – Keith Backman Dec 17 '19 at 22:15
  • $\begingroup$ You need to consider prime powers too, see the 2nd dupe. $\endgroup$ – Bill Dubuque Dec 17 '19 at 22:21
  • $\begingroup$ @Bill Dubuque Thanks for steering me to good information. $\endgroup$ – Keith Backman Dec 17 '19 at 22:25
2
$\begingroup$

The smallest counter example $n=4$, since $1\times 2$ and $2\times 3$ are not multiples of $4$.

$\endgroup$
  • $\begingroup$ I suppose I should have made it more explicit, but since the sum in my expression runs from $k=5$ and I specifically discussed the anomaly of $4$, I was interested in the truth of the conjecture for composites other than $4$. $\endgroup$ – Keith Backman Dec 17 '19 at 22:12
  • 1
    $\begingroup$ @KeithBackman like $9$? $\endgroup$ – peterwhy Dec 17 '19 at 22:16

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