Intereting Posts

When we say, “ZFC can found most of mathematics,” what do we really mean?
Proving “The sum of n consecutive cubes is equal to the square of the sum of the first n numbers.”
Cardinalities of $\mathbb{R^{2}}$ and $\mathbb{C}$ and isomorphisms
Proof of dividing fractional expressions
Simple solving Skanavi book exercise: $\sqrt{9+\sqrt{80}}+\sqrt{9-\sqrt{80}}$
Expressing a positive integer as a sum of positive integers
Group With an Endomorphism That is “Almost” Abelian is Abelian.
Prove that a metric space is countably compact if and only if every infinite sequence in $X$ has a convergent subsequence.
When do surjections split in ZF? Two surjections imply bijection?
Calculating the integral $\int_{0}^{\infty} \frac{\cos x}{1+x^2}\mathrm{d}x$ without using complex analysis
product of two uniformly continuous functions is uniformly continuous
Help with graph induction proof
To determine whether the integral $\int_0^{\infty} \frac{\sin{(ax+b)}}{x^p} \,\mathrm dx$ converges for $p>0$
$\mathbb Q/(x^2+1)$ is not isomorphic to $\mathbb Q/(x^2+2)$
Differential and derivative of the trace of a matrix

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.

- How to prove CYK algorithm has $O(n^3)$ running time
- Fermats Little Theorem
- Weights - Objects into bags puzzle
- Relationship between degrees of continued fractions
- Rewriting repeated integer division with multiplication
- Largest prime factor of 600851475143

- If there is one perfect square in an arithmetic progression, then there are infinitely many
- Is $\mathbb{Z}/p^\mathbb{N} \mathbb{Z}$ widely studied, does it have an accepted name/notation, and where can I learn more about it?
- Fermats Little Theorem
- Is ${\sqrt2^{\sqrt2^{\sqrt2^{\sqrt2^\sqrt2}}}}^{…}=4$ correct?
- Do these inequalities regarding the gamma function and factorials work?
- How to find solutions of $x^2-3y^2=-2$?
- Why is $x^{-1} = \frac{1}{x}$?
- $T(1) = 1 , T(n) = 2T(n/2) + n^3$? Divide and conquer
- Special Cases of Quadratic Reciprocity and Counting Fixed Points
- Calculating 7^7^7^7^7^7^7 mod 100

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.

- Validity of conditional statement when the premise is false.
- Fourier Uniqueness Theorem: Proof?
- Probability problem: cars on the road
- How to solve simultaneous inequalities?
- How to show $f'(0)$ exist and is equal to $1$?
- Finite field, every element is a square implies char equal 2
- Probability of men and women sitting at a table alternately
- Find the sign of $\int_{0}^{2 \pi}\frac{\sin x}{x} dx$
- The set of all $x$ such that $xHx^{-1}\subseteq H$ is a subgroup, when $H\leq G$
- Modular Inverses
- Is there an exact term for $\sqrt{2+\sqrt{4+\sqrt{8+\dots}}}$
- Taylor series convergence for $e^{-1/x^2}$
- How to prove: $a+b+c\le a^2+b^2+c^2$, if $abc=1$?
- How a group represents the passage of time?
- Given that $\;\sin^3x\sin3x = \sum^n_{m=0}C_m\cos mx\,,\; C_n \neq 0\;$ is an identity . Find the value of n.