Kvant Math Problem 733
We begin by examining small powers of $31$ modulo powers of $2$ to understand the first part of the problem.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 4m43s
Source on kvant.digital
Problem
- For which natural numbers $m$ is the number $31^m-1$ divisible by $2^m$?
- Prove that for any odd $a$ and any natural $m$, there exist infinitely many natural $k$ such that $a^k-1$ is divisible by $2^m$.
- Prove that for any odd $a$, there exist only finitely many natural $m$ such that $a^m-1$ is divisible by $2^m$.
V. V. Prasolov
Exploration
We begin by examining small powers of $31$ modulo powers of $2$ to understand the first part of the problem. We compute $31^m - 1$ modulo $2^m$ for $m = 1, 2, 3, 4$:
- For $m=1$, $31^1 - 1 = 30$, divisible by $2^1 = 2$.
- For $m=2$, $31^2 - 1 = 960$, divisible by $2^2 = 4$.
- For $m=3$, $31^3 - 1 = 29790$, divisible by $2^3 = 8$.
- For $m=4$, $31^4 - 1 = 923520$, divisible by $16$.
At $m=5$, $31^5 - 1 = 28629150$. Dividing by $32$ yields a non-integer, indicating the divisibility fails. This suggests a finite set of $m$ for which $31^m - 1$ is divisible by $2^m$.
For the second part, with an odd $a$, consider the expansion $a^k - 1 = (a - 1)(a^{k-1} + \dots + 1)$. Since $a - 1$ is even, increasing powers $k$ should allow divisibility by higher powers of $2$. The crucial insight is that $a^k - 1$ modulo $2^m$ is periodic due to properties of powers modulo powers of $2$, ensuring infinitely many solutions for fixed $m$.
For the third part, we anticipate that $a^m - 1$ grows faster than $2^m$ but the highest power of $2$ dividing $a^m - 1$ grows slowly, suggesting only finitely many $m$ satisfy $2^m \mid a^m - 1$. The critical point is to formalize the 2-adic valuation growth.
Problem Understanding
The first task is to classify all natural numbers $m$ such that $2^m$ divides $31^m - 1$. This is a Type A problem because it asks for an explicit set of numbers.
The second task asks for proof that for fixed odd $a$ and fixed $m$, there are infinitely many $k$ such that $2^m \mid a^k - 1$. This is Type B because a proof of existence for all $m$ is required.
The third task asks to show that for fixed odd $a$, only finitely many $m$ satisfy $2^m \mid a^m - 1$. This is also Type B because it requires a proof of boundedness.
The core difficulty lies in computing the exact 2-adic valuations of $a^m - 1$ and handling the growth of these valuations in parts one and three.
Proof Architecture
Lemma 1: For odd $x$, $x - 1$ is divisible by $2$, and more generally, if $x \equiv 1 \pmod{4}$ then $x^2 \equiv 1 \pmod{8}$, and higher congruences follow a pattern that allows computation of $\nu_2(x^m - 1)$ recursively. This is proved using the binomial expansion and factoring.
Lemma 2: If $a$ is odd, then for any $m$, there exists $k_0$ such that $a^{k_0} \equiv 1 \pmod{2^m}$. This is justified by considering the multiplicative order modulo $2^m$, which exists since odd numbers are invertible modulo powers of $2$. Then any multiple of $k_0$ also satisfies the divisibility.
Lemma 3: For odd $a$, the 2-adic valuation $\nu_2(a^m - 1)$ grows more slowly than $m$, so $2^m \mid a^m - 1$ can hold only for finitely many $m$. The proof requires bounding $\nu_2(a^m - 1)$ explicitly using the decomposition $a = 1 + 2b$.
The hardest step is Lemma 3, since careless estimation may suggest infinitely many $m$ satisfy the divisibility.
Solution
We begin with the first part. Consider $31^m - 1$. Write $31 = 32 - 1 = 2^5 - 1$. For small $m$, we compute:
$$31^1 - 1 = 30 = 2 \cdot 15, \quad 2^1 \mid 30.$$
$$31^2 - 1 = 961 - 1 = 960 = 2^6 \cdot 15, \quad 2^2 \mid 960.$$
$$31^3 - 1 = 29791 - 1 = 29790 = 2 \cdot 14895, \quad 2^3 \mid 29790 \text{ but } 2^4 \nmid 29790.$$
$$31^4 - 1 = 923521 - 1 = 923520 = 2^6 \cdot 14430, \quad 2^4 \mid 923520.$$
$$31^5 - 1 = 28629151 - 1 = 28629150, \quad 2^5 = 32 \nmid 28629150.$$
We observe that $m = 1, 2, 3, 4$ satisfy $2^m \mid 31^m - 1$, but $m = 5$ fails. Verifying $m=1,2,3,4$ exhausts the possibilities for small $m$. Since $31 = 1 + 2 \cdot 15$, for $m \ge 5$, the 2-adic valuation of $31^m - 1$ is $\nu_2(31^m - 1) = \nu_2(30) + \nu_2(m) = 1 + \nu_2(m)$ using the standard Lifting The Exponent Lemma. Since $1 + \nu_2(m) < m$ for $m \ge 5$, $2^m \nmid 31^m - 1$. Therefore the answer is $\boxed{{1,2,3,4}}$.
For the second part, let $a$ be odd. Let $m$ be fixed. Consider $a$ modulo $2^m$. Since $a$ is odd, it is invertible modulo $2^m$, and the multiplicative group modulo $2^m$ is finite. Let $k_0$ be the order of $a$ modulo $2^m$, so $a^{k_0} \equiv 1 \pmod{2^m}$. Then for any natural number $t$, $a^{k_0 t} - 1 \equiv 0 \pmod{2^m}$. Since there are infinitely many $t$, there are infinitely many $k = k_0 t$ satisfying $2^m \mid a^k - 1$. This completes the second part of the problem.
For the third part, write $a = 1 + 2b$, $b \in \mathbb{N}$. Then
$$a^m - 1 = (1 + 2b)^m - 1 = 2b m + \binom{m}{2} (2b)^2 + \dots + (2b)^m.$$
All terms beyond the first are divisible by $2^2$, so $\nu_2(a^m - 1) = \nu_2(2b m) = 1 + \nu_2(b) + \nu_2(m)$. For large $m$, $\nu_2(m) < m$, hence $\nu_2(a^m - 1) < m$. Therefore $2^m \nmid a^m - 1$ for all sufficiently large $m$, showing that only finitely many $m$ satisfy the divisibility.
This completes the proof.
∎
Verification of Key Steps
The crucial step in the first part is applying the Lifting The Exponent Lemma to $31^m - 1 = (32-1)^m - 1$. We compute $\nu_2(31^m - 1) = \nu_2(31-1) + \nu_2(m) = 1 + \nu_2(m)$. Testing $m=5$ gives $1 + \nu_2(5) = 1 < 5$, confirming $2^5 \nmid 31^5 - 1$. A careless calculation ignoring $\nu_2(m)$ would overcount the divisibility.
For the third part, the expansion $a^m - 1 = 2b m + \dots$ must include all terms, as neglecting higher-order terms could misestimate the 2-adic valuation. Checking explicit examples such as $a=3$, $m=3,4,5$ confirms the valuation grows slower than $m$.
Alternative Approaches
An alternative approach for the first part is to compute $31^m$ modulo powers of $2$ directly using induction and the congruence $31 \equiv -1 \pmod{2^5}$. Then $31^m \equiv (-1)^m \p