Divisibility of generalized Mersenne numbers
Alex Chan · 2025
Read Divisibility of generalized Mersenne numbers by Alex Chan (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2512-22645.txt.
Introduction
Alex Chan proves a divisibility test for a generalized family of repunits. Usual Mersenne numbers are one less than a power of two. Generalized Mersenne numbers here are repunits, strings of ones. They are written in two different bases, a-to-the-m and a-to-the-k, sharing the same length. Chan's theorem gives a criterion determining when one such number divides the other.
The main proof handles the general case across all choices of the bases' exponents and the length. Chan also supplies a second, alternative proof specialized to one case of the theorem, giving readers two routes to the same criterion. The note is a compact contribution to elementary number theory's long study of repunit divisibility.
Catalog record
| CREATOR | Alex Chan |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 10 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2512-22645
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Divisibility of generalized Mersenne numbers Alex Chan Abstract Introduction . In this article, I present a theorem determining a criterion for divisibility of two generalized Mersenne numbers, which are repunits of the same length in base- a^{m} and base- a^{k} . In addition to the general proof, I present an alternative proof for a special case of the theorem. In this paper d,m,k,a are any positive integers, d>1,a>1 . There are several interpretations of the term ”generalized Mersenne number”. In this work, I define generalized Mersenne number M_{d}(x):=\sum_{j=0}^{d-1}x^{j} . Acknowledgments. The author thanks Prof. N. Osipov, A. Kalmynin and Prof. A. Skopenkov for their continued support throughout the different stages of the project. Theorem . The following conditions are equivalent. (1) The number M_{d}(a^{m}) is divisible by the number M_{d}(a^{k}) . (2) m is divisible by k and \gcd(\frac{m}{k};d)=1 . Proof. Define Q:=\frac{M_{d}(a^{m})}{M_{d}(a^{k})} Proof that (1)\Leftarrow(2) . Suppose that m is divisible by k and \gcd{(\frac{m}{k},d)}=1 . Let n=\frac{m}{k} so that \gcd{(n,d)}=1 . The corresponding quotient can be written as Q=\frac{(a^{md}-1)(a^{k}-1)}{(a^{m}-1)(a^{kd}-1)}=\frac{(b^{nd}-1)(b-1)}{(b^{n}-1)(b^{d}-1)} where b=a^{k}\geq 2 . We have \gcd{(b^{n}-1,b^{d}-1)}=b^{\gcd{(n,d)}}-1=b-1 . Thus, Q=\frac{b^{nd}-1}{\mathop{\text{}}{\rm lcm}(b^{n}-1,b^{d}-1)} and Q is an integer since b^{nd}-1 is a common multiple of b^{n}-1 and b^{d}-1 . Proof that (1)\Rightarrow(2) . Suppose the quotient Q=\frac{(a^{md}-1)(a^{k}-1)}{(a^{m}-1)(a^{kd}-1)} to be an integer. We now prove that m is divisible by k and that \gcd(\frac{m}{k};d)=1 separately. Proof that (1) \Rightarrow m is divisible by k . Using the so-called Zsigmondy’s theorem (see [ Bi , Theorem V] or the original Zsigmondy’s paper [ Zs ] ), show that m is divisible by k . Case when kd=2 . If kd=2 then k=1 and the claim is trivially true. Case when kd=6 and a=2 . If kd=6 and a=2 , then either k=1 (then m is divisible by k ) or (k,d)\in\{(2,3),(3,2)\} . In the case (k,d)=(2,3) the quotient Q=\frac{2^{2m}+2^{m}+1}{21} is an integer only for m=2n with n not divisible by 3 . In the case (k,d)=(3,2) the quotient Q=\frac{2^{m}+1}{9} is an integer only for m=3n with n odd. Consequently, in both cases m is divisible by k . All other cases. In remaining cases, by Zsigmondy’s theorem there exists a prime divisor p of a^{kd}-1 such that \mathop{\text{}}{\rm ord}_{p}{(a)}=kd . Due to kd>k we conclude that a^{k}\not\equiv 1\pmod{p} . Since Q is an integer, we obtain a^{md}\equiv 1\pmod{p} . Hence md is divisible by kd or, equivalently, m is divisible by k . Proof that (1) \Rightarrow \gcd(\frac{m}{k};d)=1 . Letting n=\frac{m}{k} again, we get Q=\frac{M_{d}(b^{n})}{M_{d}(b)} with b=a^{k}\geq 2 . Assuming Q to be an integer, we need to prove that \gcd{(n,d)}=1 . Let \gcd{(n,d)}=l and n_{1}=n/l , d_{1}=d/l . Then M_{d}(b^{n})\equiv lM_{d_{1}}(b^{l})\pmod{M_{d}(b)} (1) as we will see later. Also, we have M_{d}(b)=M_{d_{1}}(b^{l})M_{l}(b) so that 0<lM_{d_{1}}(b^{l})=\frac{l}{M_{l}(b)}M_{d}(b)<M_{d}(b) for all b\geq 2 and l>1 . Thus, M_{d}(b^{n}) cannot be divisible by M_{d}(b) for l>1 . Therefore, l=1 . It remains to prove (1). We use the following well-known fact: for any N divisible by d , the congruence b^{N}\equiv 1\pmod{M_{d}(b)} holds. We have M_{d}(b^{n})=\sum_{i=0}^{d-1}b^{ni}=\sum_{q=0}^{l-1}\sum_{r=0}^{d_{1}-1}b^{ln_{1}(d_{1}q+r)}\equiv\sum_{q=0}^{l-1}\sum_{r=0}^{d_{1}-1}b^{ln_{1}r}=l\sum_{r=0}^{d_{1}-1}b^{ln_{1}r}=\\ =l\sum_{r=0}^{d_{1}-1}b^{l(j_{r}+d_{1}q_{r})}\equiv l\sum_{r=0}^{d_{1}-1}b^{lj_{r}}=l\sum_{r=0}^{d_{1}-1}b^{lr}=lM_{d_{1}}(b^{l})\pmod{M_{d}(b)}. Here n_{1}r=j_{r}+d_{1}q_{r} for some integers j_{r},q_{r} ( 0\leq j_{r}<d_{1} ) such that \{j_{0},j_{1},\dots,j_{d_{1}-1}\}=\{0,1,\dots,d_{1}-1\} due to \gcd{(n_{1},d_{1})}=1 . In the ring \mathbb{Z}[x] , the congruence (1) rewritten as M_{d}(x^{n})\equiv lM_{d_{1}}(x^{l})\pmod{M_{d}(x)} holds too (and follows the same proof). ∎ Remark . 1. M_{d}(x^{m}) is divisible by M_{d}(x^{k}) in the ring of polynomials \mathbb{Z}[x] if and only if m , k , d satisfy the same condition. The proof of the claim “if” almost exactly follows one given in part I. At the same time, the proof of the claim “only if” is simplified by considering the complex roots of polynomials with their multiplicities instead of Zsigmondy’s theorem. 2. Proof that (1) \Rightarrow \gcd(\frac{m}{k};d)=1 can be performed via Zsigmondy’s theorem and the well-known LTE-lemma (see [ LTE ] ). Rewrite Q=M_{d}(b^{n})/M_{d}(b) in the form Q=\frac{(b^{nd}-1)(b-1)}{(b^{n}-1)(b^{d}-1)}. Assume Q to be an integer while \gcd{(n,d)}>1 . Let q be a common prime divisor of n and d . Let n_{1}=n/q and d_{1}=d/q . Case when q\geq 3 . By Zsigmondy’s theorem, there is a prime divisor p of b^{q}-1 such that \mathop{\text{}}{\rm ord}_{p}{(b)}=q . Then b\not\equiv 1\pmod{p} . As a corollary we get p\neq q and p\neq 2 . Let c=b^{q} . We have \nu_{p}((b^{n}-1)(b^{d}-1))=\nu_{p}((c^{n_{1}}-1)(c^{d_{1}}-1))= =\nu_{p}(c^{n_{1}}-1)+\nu_{p}(c^{d_{1}}-1)=2\nu_{p}(c-1)+\nu_{p}(n_{1})+\nu_{p}(d_{1}). while \nu_{p}((b^{nd}-1)(b-1))=\nu_{p}(b^{nd}-1)=\nu_{p}(c^{qn_{1}d_{1}}-1)= =\nu_{p}(c-1)+\nu_{p}(qn_{1}d_{1})=\nu_{p}(c-1)+\nu_{p}(n_{1})+\nu_{p}(d_{1}). Thus, \nu_{p}((b^{n}-1)(b^{d}-1))>\nu_{p}((b^{nd}-1)(b-1)) and Q cannot be an integer. Contradiction. Case when q=2 and b+1\neq 2^{t} . In this case b+1 has a prime divisor p\neq 2 . Clearly, b\not\equiv 1\pmod{p} . We can get a contradiction in the same way as above. Case when q=2 and b=2^{t}-1 where t\geqslant 2 . Here, we have n=2n_{1} , d=2d_{1} . Then \nu_{2}(b^{n}-1)=\nu_{2}(b^{2}-1)-1+\nu_{2}(n)=t+\nu_{2}(n)=t+1+\nu_{2}(n_{1}) and similarly \nu_{2}(b^{d}-1)=t+1+\nu_{2}(d_{1}),\quad\nu_{2}(b^{nd}-1)=t+2+\nu_{2}(n_{1})+\nu_{2}(d_{1}). Thus, we obtain \nu_{2}((b^{n}-1)(b^{d}-1))=2t+2+\nu_{2}(n_{1})+\nu_{2}(d_{1})> >t+3+\nu_{2}(n_{1})+\nu_{2}(d_{1})=\nu_{2}((b^{nd}-1)(b-1)) and Q cannot be an integer again. Contradiction. Hence, \gcd(n,d)=1 . Proof that (1)\Rightarrow(2) from an anonymous reviewer . Proof that (1) \Rightarrow m is divisible by k . Suppose that the quotient Q^{\prime}=\frac{(a^{md}-1)(a^{k}-1)}{a^{kd}-1} is an integer. Then m must be divisible by k . Indeed, let \displaystyle D=\gcd{(a^{md}-1,a^{kd}-1)}=a^{d\gcd{(m,k)}}-1, \displaystyle a^{md}-1=DA^{\prime},\quad a^{kd}-1=DA^{\prime\prime} for some A^{\prime} and A^{\prime\prime} such that \gcd{(A^{\prime},A^{\prime\prime})}=1 . Then DA^{\prime}(a^{k}-1)=DA^{\prime\prime}Q^{\prime} . Hence, A^{\prime}(a^{k}-1)=A^{\prime\prime}Q^{\prime}. Then A^{\prime}(a^{k}-1) is divisible by A^{\prime\prime} . Hence A^{\prime\prime} is a divisor of a^{k}-1 because \gcd{(A^{\prime},A^{\prime\prime})}=1 . Thus, DA^{\prime\prime} is a divisor of D(a^{k}-1) , i.e., a^{kd}-1 is a divisor of (a^{d\gcd{(m,k)}}-1)(a^{k}-1) . In particular, a^{kd}-1\leqslant(a^{d\gcd{(m,k)}}-1)(a^{k}-1)<a^{d\gcd{(m,k)}+k}-1 that yields kd<d\gcd{(m,k)}+k or \frac{k}{\gcd{(m,k)}}<\frac{d}{d-1}\leqslant 2 (recall that d\geqslant 2 ). Then k=\gcd{(m,k)} so that m is divisible by k . Proof that (1) \Rightarrow \gcd(\frac{m}{k};d)=1 . Let n=m/k and assume the number \frac{(b^{nd}-1)(b-1)}{(b^{n}-1)(b^{d}-1)}=\frac{b^{nd}-1}{b^{n}-1}:\frac{b^{d}-1}{b-1}=\frac{b^{nd}-1}{b^{d}-1}:\frac{b^{n}-1}{b-1} to be an integer (where b=a^{k}\geqslant 2 ). Let us introduce M:=\frac{b^{\gcd{(n,d)}}-1}{b-1}. Clearly, we have \frac{b^{d}-1}{b-1}\equiv\frac{b^{n}-1}{b-1}\equiv 0\pmod{M}. As a corollary of our assumption, we get \displaystyle 0\equiv\frac{b^{nd}-1}{b^{n}-1}=1+b^{n}+\ldots+b^{n(d-1)}\equiv d\pmod{M}, \displaystyle 0\equiv\frac{b^{nd}-1}{b^{d}-1}=1+b^{d}+\ldots+b^{d(n-1)}\equiv n\pmod{M}. Therefore, \gcd{(n,d)} is divisible by M . In the case \gcd{(n,d)}>1 we obtain \gcd{(n,d)}<2^{\gcd{(n,d)}}-1\leqslant M which is a contradiction. Thus, \gcd{(n,d)}=1 as desired. Alternative proof that (1)\Rightarrow m is divisible by k . Define g=\mathop{\text{}}{\rm ord}_{M_{d}(a^{k})}{(a)} . We now prove that g=kd . Indeed, a^{kd}-1 is divisible by M_{d}(a^{k}) , so kd is divisible by g . On the other hand, M_{d}(a^{k})>a^{k(d-1)} , so g>k(d-1) . Thus, g=kd . Hence, (1) \Rightarrow a^{md}-1 is divisible by M_{d}(a^{k})\Rightarrow m is divisible by k . Special case of the theorem . Proposition. The following conditions are equivalent. (1) The number M_{d}(n^{m}) is divisible by the number M_{d}(n^{k}) for any integer n . (2) m is divisible by k and \gcd(\frac{m}{k};d)=1 . This result could be known. I learned it from [ Sy ] . I. Syukrin presented an idea of a technical proof using canonical decomposition of numbers. Here I present a simple proof using roots of polynomials. (3) The polynomial M_{d}(x^{m}) is divisible in \mathbb{Z}[x] by the polynomial M_{d}(x^{k}) . Equivalence of (3) and (1) follows from [ Sk , Problem 3.4.2.b] (there the assumption that P does not have roots is superfluous). We now prove that both (3) and (2) are equivalent to the following statement. (4) The polynomial (x^{md}-1)(x^{k}-1) is divisible in \mathbb{Z}[x] by the polynomial (x^{m}-1)(x^{kd}-1) . We prove the equivalences (2)\Leftrightarrow(4)\Leftrightarrow(3). Equivalence of (3) and (4) is obvious. Proof that (2)\Rightarrow(4) . This statement follows the same proof as the proof that (1) \Leftarrow (2) in the Theorem. Proof that (2)\Leftarrow(4) . Since (x^{md}-1)(x^{k}-1) is divisible in \mathbb{Z}[x]