Intereting Posts

Notation/definition problem for commutative binary operation
The cardinality of a language over a set of variables $V$ with $\#V= κ$
Convolution product on the linear dual of the polynomial algebra
How to solve this recurrence relation
Find the asymptotic tight bound for $T(n) = 4T(n/2) + n^{2}\log n$
Standard graded algebra
Beautiful cyclic inequality
4 dimensional numbers
Formal logic systems, how do we prove theorems about them?
A proof that $1=2$. May I know why it’s false?
$\mathbb{Q}/(X^2+Y^2-1)$ is integrally closed
Palindromic Numbers – Fractal or Chaotic?
Every group of order 203 with a normal subgroup of order 7 is abelian
Solvability of Artin-Schreier Polynomial
Group of order 15 is abelian

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.

- Number of Solutions to a Diophantine Equation
- Find all $n$ for the coins
- Algorithm for comparing the size of extremely large numbers
- Repeatedly taking mean values of non-empty subsets of a set: $2,\,3,\,5,\,15,\,875,\,…$
- Would proof of Legendre's conjecture also prove Riemann's hypothesis?
- What are the bases $\beta$ such that a number with non-periodic expansion can be approximated with infinitely many numbers with periodic expansion?

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

- How can we show that $\operatorname{ord}_{p}\left(\binom{2n}n\right) \le \frac{\log 2n}{\log p}$
- The number of solutions of $ax^2+by^2\equiv 1\pmod{p}$ is $ p-(\frac{-ab}{p})$
- Prove that $\sqrt{2}+\sqrt{3}$ is irrational.
- Is $\log(n!) \in\Theta(n \log n)$
- What is the max of $n$ such that $\sum_{i=1}^n\frac{1}{a_i}=1$ where $2\le a_1\lt a_2\lt\cdots\lt a_n\le 99$?
- Counting the Number of Integral Solutions to $x^2+dy^2 = n$
- How can I compute the sum of $ {m\over\gcd(m,n)}$?
- Additive group of rationals has no minimal generating set

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.

- Convergence of Random Variables in mean
- Lie algebras and roots systems
- What is the integral of 1/x?
- Question on problem: Equivalence of two metrics $\iff$ same convergent sequences
- universal property in quotient topology
- Prove that a graph with the same number of edges and vertices contains one cycle
- Nilpotent groups are solvable
- Dimension of $\Bbb Q(e)$ over $\Bbb Q$?
- Decomposition of a primitive ideal of a quadratic order
- Distribution of Difference of Chi-squared Variables
- Why is the postulate $1$ not equal to $0$ not superfluous?
- Prove that $\mathrm{span}(S) = S$ for a subspace $S$.
- Digit function properties
- The group $E(\mathbb{F}_p)$ has exactly $p+1$ elements
- Venn diagram question