Largest idempotent

Given the prime power factors of $N$, is there a non-quadratic algorithm for finding the largest idempotent of ring $\mathbb{Z}/N\mathbb{Z}$? (That is, the largest number $A \lt N$ such that $A^{2} \equiv A \text{mod} N$.)

I know that there are at most $8$ prime power factors ($=K$) for $N$ in the range of interest, thus at most $256 (=2^K)$ idempotents, with $0$ & $1$ being trivial.

edited: “range of interest” clause somehow got misplaced.

Solutions Collecting From Web of "Largest idempotent"

Let $N = m_1\ldots m_k$ be a prime power decomposition (distinct $m_i$ coprime).

Then $A$ is an idempotent modulo $N$ iff $A^2 \equiv A \mod{N}$. Equivalently, $A$ is
an idempotent modulo each prime power factor $m_i$, which amounts to:

$$ \forall m_i \; A \equiv 0,1 \mod{m_i} $$

because $A(A-1)$ is divisible by prime power $m_i$ only if $m_i$ divides $A$ or $A-1$.
Henceforth we will refer to $0,1$ as trivial idempotents. For nontrivial
idempotents $A$ we multiply those factors $m_i$ which divide $A$ to get the product $M$.
Then $M$ and $N/M$ are coprime and:

$$ A \equiv 0 \mod{M} $$

$$ A \equiv 1 \mod{N/M} $$

The first of these relations implies that $A = aM$. Require a reduced residue
$1 \lt A \lt N$, and it follows $0 \lt a \lt N/M$. The coprimality of $M$ and $N/M$
gives $a \equiv M^{-1} \mod{N/M}$, thereby satisfying the second relation.

Moreover as @rschwieb pointed out, the nontrivial idempotents occur in pairs $A,A’$ s.t.
$A + A’ = N + 1$ by swapping the roles of $M$ and $N/M$. Searching for large idempotents
(but less than $N$) thus amounts to searching for small ones (but greater than $1$).

All nontrivial idempotents may be formed as distinct sums of “basic” idempotents $A_i$,
$1 \le i \le k$, taking the product $M_i$ of the $k-1$ prime powers other than $m_i$,
so $N/M = m_i$. Then $A_i = a_i M_i$ where $a_i \equiv M_i^{-1} \mod{m_i}$. One way to
solve for $a_i$ uses the extended Euclidean
algorithm to provide:

$$ a_i M_i + b_i m_i = 1 $$

Alternatively one can apply Euler’s generalization of Fermat’s Little
Theorem:

$$ a_i \equiv M_i^{\phi(m_i)-1} \mod{m_i} $$

However one computes those $k$ basic solutions $a_i M_i$, all nontrivial idempotents $\mod{N}$
can be expressed as sums over proper (nonempty) subsets of them. By this accounting there
are $2^k – 2$ of them (excludes the two trivial idempotents).


Example: Let $N = 10^n = 2^n 5^n$. For each $n$ there are two nontrivial idempotents,
adding up to $N + 1$. Their respective decimal representations “stabilize” by truncation
so we may summarize both parallel expansions:

$$ a_n 5^n:\; \ldots 19977392256259918212890625 $$
$$ b_n 2^n:\; \ldots 80022607743740081787109376 $$

allowing us to tell by inspection for given $n$ which of the two is larger. I don’t see
any regular pattern in these results, although the frequency of double digits looks
somewhat improbable.

Cases of this turn up in online puzzles and older
literature.

Readers interested in extending this example may find it useful that squaring an initial
segment of the $a_n 5^n$ adds at least one extra correct digit. The analogous fact about
the $b_n 2^n$ series requires taking a fifth power, so it’s more easily derived by
“complementing” the $a_n 5^n$ series.


The irregularity with which the above two series of idempotents swap top position
doesn’t suggest a shortcut for more general $N$ and higher number of factors $k$.

While an exhaustive search is satisfactory for small $k$, for large $k$ we should perhaps
look to the subset sum problem for
inspiration.

The set of basic solutions $\{A_1,\ldots,A_k\}$ can without loss of generality be assumed
to be ordered. So as a first approximation to finding the largest nontrivial idempotent,
we can compare $A_k$ and $N+1-A_1$. No single basic solution (or sum of $k-1$ of them)
could improve on that, so let’s label that $E_1$.

Using two or basic solutions for an improvement would then amount to a sequence of approximate
subset sum problems
targeting intervals $((j-1)N+E_j,jN-1]$ for $j=1$ up to $\frac{k}{2}$, taking $E_{j+1}$ to be the improvement if one is found, or $E_j$ otherwise.

While this seems promising as far as polynomial-time in $k$, it’s only a sketch of an idea
at this point.