# For any composite modulus $n$, there are two consecutive integers whose product $\equiv 0 \bmod n$ [duplicate]

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 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 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?

• $\!\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. – Bill Dubuque Dec 17 '19 at 22:06
• Or, equivalently, $a+1$ is idempotent. – Bill Dubuque Dec 17 '19 at 22:11
• @Bill Dubuque So I guess my question boils down to for composite $n$ (other than $4$), is there always an idempotent? – Keith Backman Dec 17 '19 at 22:15
• You need to consider prime powers too, see the 2nd dupe. – Bill Dubuque Dec 17 '19 at 22:21
• @Bill Dubuque Thanks for steering me to good information. – Keith Backman Dec 17 '19 at 22:25

The smallest counter example $$n=4$$, since $$1\times 2$$ and $$2\times 3$$ are not multiples of $$4$$.
• 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$. – Keith Backman Dec 17 '19 at 22:12
• @KeithBackman like $9$? – peterwhy Dec 17 '19 at 22:16