A Cyclotomic Totient Oracle for Mersenne Numbers
One residue of a cyclotomic value determines Euler’s totient, and hence the factorisation
R001 · Novelty unconfirmed
The setting
Let \(p\) be prime and let \(N = 2^p - 1\) be the corresponding Mersenne number. Write \(\Phi_n\) for the \(n\)-th cyclotomic polynomial and \(\varphi\) for Euler’s totient function.
The factorisation of a Mersenne number is a classical object of study, and one widely-used route to it is to evaluate cyclotomic polynomials at \(2\). The question this note answers is: how much arithmetic information does a single residue of \(\Phi_N(2)\) carry?
The answer is: all of it, in a very strong sense. Because \(N = 2^p - 1\) forces a rigid congruence structure on the divisors of \(N\), the residue \(\Phi_N(2) \bmod N^2\) collapses onto a one-parameter family \(1 + cN\) — and the parameter \(c\) turns out to be exactly \(\frac{2\varphi(N)}{p}\), with nothing to disambiguate.
Novelty. A literature search found the mod-\(N\) necklace divisibility (\(\sum_{d\mid N}\mu(N/d)2^d \equiv 2\varphi(N)/p \bmod N\), Moreau 1872 / Moree 2005) but not the mod-\(N^2\) congruence below with its coefficient \(2\varphi(N)/p\), and not the decoding step. The search could not reach MathSciNet or zbMATH, so this is absence of evidence, not proof of novelty. The step “\(\varphi(N)\) \(\Rightarrow\) factorisation” is classical (Miller 1976; Rabin 1980) and is cited, not claimed.
Not a factoring algorithm. The theorem is an information statement. The closing proposition shows evaluating the residue is randomised-polynomial-time equivalent to factoring, so this is a reformulation, not an attack.
Two structural lemmas
Lemma 1 (divisor structure of Mersenne numbers). Let \(p\) be prime and \(N = 2^p - 1\). Then
- \(\operatorname{ord}_q(2) = p\) for every prime \(q \mid N\);
- \(q \equiv 1 \pmod{2p}\) for every prime \(q \mid N\);
- every divisor \(d \mid N\) satisfies \(d \equiv 1 \pmod p\);
- \(\operatorname{ord}_N(2) = p\).
Proof.
If \(q \mid 2^p - 1\) then \(2^p \equiv 1 \pmod q\), so \(\operatorname{ord}_q(2) \mid p\). As \(p\) is prime the order is \(1\) or \(p\); it is not \(1\), since \(2 \equiv 1 \pmod q\) would force \(q \mid 1\).
\(\operatorname{ord}_q(2) \mid q - 1\) gives \(p \mid q-1\). Here \(N\) is odd, so \(q\) is odd and \(2 \mid q - 1\); since \(\gcd(2,p) = 1\) we get \(2p \mid q - 1\).
By (2) each prime power \(q^e \parallel N\) satisfies \(q^e \equiv 1 \pmod p\), and a product of such terms is \(\equiv 1 \pmod p\).
\(2^p = N + 1 \equiv 1 \pmod N\), so \(\operatorname{ord}_N(2) \mid p\); and \(2 \not\equiv 1 \pmod N\) because \(N \ge 3\).
Nobody should read Lemma 1 as claiming \(N\) is squarefree: that is open in general, and for prime \(p\) it is equivalent to the non-existence of a base-2 Wieferich prime of prime order dividing \(N\). Squarefreeness, and \(\operatorname{ord}_{N^2}(2)\), are both unused below.
Lemma 2 (exact collapse identity). For integers \(a \ge 2\), \(n \ge 2\), put \(T_d := \dfrac{a\,(a^{d-1}-1)}{a-1} \in \mathbb{Z}\) for \(d \ge 1\), so \(T_1 = 0\). Then the following holds in \(\mathbb{Z}\), exactly:
\[\Phi_n(a) \;=\; \prod_{d \mid n}\bigl(1 + T_d\bigr)^{\mu(n/d)}.\]
Proof. Since \((a-1)(1+T_d) = (a-1) + a(a^{d-1}-1) = a^d - 1\), we may substitute \(a^d - 1 = (a-1)(1+T_d)\) into the Möbius product:
\[\prod_{d\mid n}(a^d-1)^{\mu(n/d)} = (a-1)^{\sum_{d\mid n}\mu(n/d)} \prod_{d\mid n}(1+T_d)^{\mu(n/d)}.\]
For \(n \ge 2\) the exponent \(\sum_{d \mid n}\mu(n/d)\) vanishes. The left-hand side is \(\Phi_n(a)\) by Möbius inversion applied to \(x^n - 1 = \prod_{d\mid n}\Phi_d(x)\).
Lemma 2 is the engine: it converts the Möbius product — whose factors \(a^d - 1\) are not units modulo \(n\) in general — into a product of factors \(1 + T_d\) whose deviation from \(1\) is controlled by \(T_d\).
The main theorem
Theorem 1 (The cyclotomic totient congruence) Let \(p\) be prime and \(N = 2^p - 1\). Then
\[\Phi_N(2) \;\equiv\; 1 + \frac{2\varphi(N)}{p}\,N \pmod{N^2}.\]
Proof. By Lemma 1(3), \(d \equiv 1 \pmod p\) for every \(d \mid N\), so \((d-1)/p \in \mathbb{Z}_{\ge 0}\). Since \(2^p = N+1\) exactly,
\[2^d \;=\; 2\,(2^p)^{(d-1)/p} \;=\; 2\,(1+N)^{(d-1)/p} \;\equiv\; 2 + 2N\,\frac{d-1}{p} \pmod{N^2},\tag{1}\]
because \((1+N)^m \equiv 1 + mN \pmod{N^2}\) for every \(m \ge 0\) — every term of degree \(\ge 2\) in \(N\) vanishes.
Apply Lemma 2 with \(a = 2\), so that \(T_d = 2^d - 2\):
\[\Phi_N(2) = \prod_{d \mid N}\bigl(1 + (2^d - 2)\bigr)^{\mu(N/d)}.\]
By (1), \(2^d - 2 \equiv 2N(d-1)/p \equiv 0 \pmod N\), so every factor is \(\equiv 1 \pmod N\). In particular every factor is a unit modulo \(N^2\), with \((1+u)^{-1} \equiv 1 - u \pmod{N^2}\) whenever \(u \equiv 0 \pmod N\). Multiplying out — and using \(u_d u_e \equiv 0 \pmod{N^2}\) for such \(u\)’s — collapses the product to a sum:
\[\Phi_N(2) \;\equiv\; 1 + \sum_{d \mid N}\mu(N/d)\,(2^d - 2) \pmod{N^2}.\tag{2}\]
Substituting (1) into (2) gives, modulo \(N^2\),
\[\sum_{d\mid N}\mu(N/d)(2^d-2) \;\equiv\; \frac{2N}{p}\sum_{d\mid N}\mu(N/d)(d-1).\]
Finally, the classical identity \(\sum_{e \mid n}\mu(e)\frac{n}{e} = \varphi(n)\) gives
\[\sum_{d\mid N}\mu(N/d)(d-1) \;=\; \sum_{d\mid N}\mu(N/d)\,d \;-\; \sum_{d\mid N}\mu(N/d) \;=\; \varphi(N) - 0 \;=\; \varphi(N).\]
Substituting into (2) proves the claim.
Why one residue determines \(\varphi(N)\)
Theorem 2 (Exact recovery) Let \(R := \Phi_N(2) \bmod N^2\) with \(0 \le R < N^2\), and put \(c := \dfrac{2\varphi(N)}{p}\). Then \(0 < c \le N-1\), and
\[R \;=\; 1 + cN, \qquad c \;=\; \frac{R-1}{N}, \qquad \varphi(N) \;=\; \frac{p\,c}{2}.\]
Proof. Positivity is clear since \(\varphi(N) \ge 1\). And \(\varphi(N) \le N-1\), so
\[c \;=\; \frac{2\varphi(N)}{p} \;\le\; \frac{2(N-1)}{p} \;\le\; N-1 \qquad (p \ge 2).\]
By the main theorem, \(R \equiv 1 + cN \pmod{N^2}\) with \(1 \le c \le N-1\). Since
\[1 \;\le\; 1 + cN \;\le\; 1 + N(N-1) \;=\; N^2 - N + 1 \;<\; N^2,\]
the representative \(R \in [0, N^2)\) equals \(1 + cN\) on the nose.
The bound \(c \le N-1\) is what makes this a decoding rather than an encoding. Because \(c\) never reaches \(N\), the number \(1 + cN\) already lies in \([0, N^2)\) — it is its own residue class, and there is nothing to disambiguate. Were \(c\) allowed to reach \(N\), the residue would pin down only \(c \bmod N\); recovering \(c\) itself would mean searching the multiples of \(N\) below \(N^2\), which is the factoring problem the residue was supposed to sidestep.
Corollary (the full divisor lattice). Given \(N\) and \(\varphi(N)\), the factorisation of \(N\) can be computed in randomised polynomial time in \(\log N\); consequently the single residue \(R\) determines \(\varphi(N)\), \(\lambda(N)\), \(\omega(N)\) and the complete divisor lattice of \(N\).
This is the classical fact that any multiple of the Carmichael exponent \(\lambda(N)\) factors \(N\) (Miller 1976; Rabin 1980): writing \(\varphi(N) = 2^s t\) with \(t\) odd and taking \(b \equiv a^t \bmod N\) for random \(a \in (\mathbb{Z}/N)^\times\), a nontrivial square root of \(1\) among the \(b^{2^i}\) splits \(N\) via \(\gcd(x-1, N)\). It is cited here rather than claimed.
One caution worth stating: \(\lambda(N)\) is not a function of \(\varphi(N)\) alone — \(\varphi(8) = \varphi(10) = \varphi(12) = 4\) while \(\lambda = 2, 4, 2\) — so \(\lambda\) and \(\omega\) become available only after the factorisation, and no “\(\lambda\)-oracle” is being claimed.
A worked example
Take \(p = 11\), so \(N = 2^{11} - 1 = 2047 = 23 \cdot 89\) and \(N^2 = 4190209\). Evaluating the Möbius product of Lemma 2 modulo \(N^2\) gives
\[\Phi_{2047}(2) \;\equiv\; 720545 \pmod{4190209}.\]
Since \(720545 = 1 + 352 \cdot 2047\), the recovery formula returns \(c = 352\). And independently
\[\varphi(2047) \;=\; 2047\left(1 - \tfrac{1}{23}\right)\left(1 - \tfrac{1}{89}\right) \;=\; 22 \cdot 88 \;=\; 1936 \;=\; \frac{p\,c}{2}.\]
The residue carries the totient exactly, from two arithmetic operations and no search.
What this is not
Proposition (no factoring algorithm). For \(N = 2^p - 1\) with \(p\) prime, the following are equivalent under randomised polynomial-time reductions: (a) factor \(N\); (b) compute \(\varphi(N)\); (c) compute \(\Phi_N(2) \bmod N^2\).
Proof.
- \(\Rightarrow\) (b) is exact recovery (two arithmetic operations). (b) \(\Rightarrow\) (a) is the randomised factoring reduction above. (a) \(\Rightarrow\) (c): given the factorisation, enumerate the divisors of \(N\) and evaluate \(\prod_{d \mid N}(2^d-1)^{\mu(N/d)} \bmod N^2\) by repeated squaring — that is \(O(2^{\omega(N)}\log N)\) modular multiplications, polynomial in \(\log N\) because \(\omega(N) = O(\log N)\). Finally (a) \(\Leftrightarrow\) (b) is classical.
So the theorem moves the difficulty into a single residue rather than removing it. Any claim that the residue can be evaluated without factoring would, by the proposition, already be a factoring algorithm. What the result does say is that the entire divisor lattice is compressed losslessly into \(2\log_2 N\) bits, and decompressed in polynomial time.
The hypotheses are necessary
The theorem is genuinely confined to prime exponents and to the base \(a = 2\).
Composite exponents fail. For \(p = 4\), \(N = 15\): \(\Phi_{15}(2) = 151\) and \(151 \equiv 1 + 10\cdot 15 \pmod{225}\), so \(c = 10\), whereas \(2\varphi(15)/4 = 4\). The failure is structural: \(3 \mid 2^4 - 1\) has \(\operatorname{ord}_3(2) = 2\), a proper divisor of \(4\), so Lemma 1(3) fails already at \(d = 3\) and (1) breaks.
Other bases fail. For \(a \ge 3\), \(n = a^p - 1\) we have \(a - 1 \mid n\), so \(g := \gcd(a-1, n) \ge 2\) and the congruence degrades. For \(a = 3\), \(p = 3\): \(\Phi_{26}(3) = 398581 \equiv 417 \pmod{676}\), giving \(c = 16\), while \(3\varphi(26)/3 = 12\). Both hypotheses fail together for \(a \ge 3\): the congruence itself, and the bound \(c \le N-1\).
Verification
Every number below can be checked. The verification script recomputes each one from the Möbius definition of \(\Phi_n\) in exact integer arithmetic, and stops if any result disagrees.
| check | range | result |
|---|---|---|
| main identity, \(\Phi_N(2) \bmod N^2 = 1 + cN\) | all prime \(p \le 47\) (15 exponents, including composite \(N\)) | 0 failures |
| \(p = 61\), \(N = 2^{61}-1\) a Mersenne prime | \(c = 75\,601\,410\,138\,153\,900\) | matches |
| bound \(0 < c \le N-1\) | \(p \le 47\) and \(p = 61\) | holds throughout |
| composite exponent \(p = 4\) fails | \(N = 15\), \(c = 10\) vs \(4\) | reproduced |
| base \(a = 3\) fails | \(\Phi_{26}(3) = 398581\), \(c = 16\) vs \(12\) | reproduced |
| worked example | \(p = 11\), \(N = 2047\) | \(c = 352\), \(\varphi = 1936\) |
Limitations
- The congruence is not sufficient to factor: by the proposition above, computing the residue is as hard as the thing it decodes.
- Decoding to a full factorisation is randomised (Miller–Rabin), not deterministic. Deterministic factoring from \((N, \varphi(N))\) is open.
- The family is exactly \(a = 2\), \(n = 2^p - 1\) with \(p\) prime. No other family is claimed.
- For \(a \ge 3\) the coefficient obeys no formula we can prove; \(\Phi_{a^p-1}(a) \equiv 1 \pmod{a^p - 1}\) is observed in every computed case and is not claimed as a theorem.
- Novelty rests on a literature search that could not reach MathSciNet or zbMATH. A referee who produces an earlier source for the mod-\(N^2\) congruence would reduce the contribution to the proof, the decoding step, and the \(a \ge 3\) obstruction.
References
- G. A. Miller, Riemann’s hypothesis and tests for primality, J. Comput. System Sci. 13 (1976) 300–317. (Multiple of \(\lambda(N)\) factors \(N\).)
- M. O. Rabin, Probabilistic algorithm for testing primality, J. Number Theory 12 (1980) 128–138.
- C. Moreau, Sur les permutations circulaires distinctes, Nouvelles Annales de Mathématiques 11 (1872) 309–314. (Aperiodic necklace counts.)
- P. Moree, On the divisibility of \(\sum \mu(n/d)a^d\) by \(n\), unpublished note / survey of the necklace congruence, 2005.