1.1 Elementary Number Theory
Trivial by induction on \(k\).
For any even \(x \in \mathbb {N}\), the odd part of \(x/2\) is equal to the odd part of \(x\).
Since \(x\) is even, \(x = 2 \cdot (x/2)\). The dyadic valuation of \(2 \cdot (x/2)\) is one more than that of \(x/2\) (if \(x/2 {\gt} 0\)), but the odd part remains the same.
For any \(k, x \in \mathbb {N}\), the odd part of \(2^k \cdot x\) is equal to the odd part of \(x\).
This is a standard property of the odd part (dyadic valuation). Multiplying by a power of 2 only changes the valuation, not the odd part.
For any \(k \in \mathbb {N}\) and any odd \(m \in \mathbb {N}\), the odd part of \(2^k \cdot m\) is \(m\).
By Lemma 3, the odd part of \(2^k \cdot m\) is the odd part of \(m\). Since \(m\) is odd, it is its own odd part.
Let \(y\) be an odd natural number such that \(y \pmod3 \neq 0\). Then there exist natural numbers \(x\) and \(k\) such that \(x\) is odd and
Since \(y \pmod3 \neq 0\), we have either \(y \equiv 1 \pmod3\) or \(y \equiv 2 \pmod3\). We consider these two cases:
If \(y \equiv 1 \pmod3\), we choose \(x = (4y - 1)/3\) and \(k = 2\). If \(y \equiv 2 \pmod3\), we choose \(x = (2y - 1)/3\) and \(k = 1\).
In both cases, it is straightforward to verify that \(x\) is an odd natural number and \(3x+1=2^k y\).
Let \(y\) be a natural number such that \(y \equiv 0 \pmod3\). Then for all natural numbers \(n\) and \(k\),
Suppose for contradiction that \(3n + 1 = 2^k y\) for some natural numbers \(n\) and \(k\). Taking both sides modulo \(3\), the left-hand side reduces to \(1 \pmod3\). Since \(y \equiv 0 \pmod3\), the right-hand side is a multiple of \(3\), which reduces to \(0 \pmod3\). This yields \(1 \equiv 0 \pmod3\), a contradiction.
Let \(y {\gt} 1\) be a natural number such that \(y \equiv 1 \pmod6\). Then there exists an odd natural number \(x {\gt} 1\) such that
We choose \(x = (4y - 1)/3\). Since \(y \equiv 1 \pmod6\), it follows that \(4y - 1\) is an odd multiple of \(3\), so \(x\) is an odd integer. Furthermore, since \(y {\gt} 1\), we have \(x {\gt} 1\). It is straightforward to verify that \(3x + 1 = 4y = 2^2 y\).
Let \(y\) be a natural number such that \(y \equiv 5 \pmod6\). Then there exists an odd natural number \(x {\gt} 1\) such that
We choose \(x = (2y - 1)/3\). Since \(y \equiv 5 \pmod6\), it follows that \(2y - 1\) is an odd multiple of \(3\), so \(x\) is an odd integer. Furthermore, since \(y \equiv 5 \pmod6\), we have \(y \ge 5\), which implies \(x \ge 3 {\gt} 1\). It is straightforward to verify that \(3x + 1 = 2y\).
For any \(k, m, n \in \mathbb {N}\), if \(m \equiv n \pmod{2^{k+1}}\), then \(m \equiv n \pmod2\).
This follows from the fact that \(2\) divides \(2^{k+1}\).
For any \(a, b, c \in \mathbb {N}\), if \(a \equiv b \pmod c\), then \(c \mid (a - b)\) in the integers.
Standard property of modular arithmetic.
For any \(a, b, c \in \mathbb {N}\), if \(c \mid (a - b)\) in the integers, then \(a \equiv b \pmod c\) in the natural numbers.
Standard property of modular arithmetic.
For any \(s, k \in \mathbb {N}\), \(3^s\) and \(2^k\) are coprime.
The only prime factor of \(3^s\) is 3, and the only prime factor of \(2^k\) is 2. Since 2 and 3 are distinct primes, any power of 3 and any power of 2 are coprime.
We define the indicator function \(X: \mathbb {N} \to \mathbb {N}\) such that \(X(n) = 0\) if \(n\) is even and \(X(n) = 1\) if \(n\) is odd. Formally,
If \(n \equiv 0 \pmod2\), then \(X(n) = 0\).
If \(n\) is even, \((-1)^n = 1\), so \(X(n) = (1 - 1)/2 = 0\).
If \(n \equiv 1 \pmod2\), then \(X(n) = 1\).
If \(n\) is odd, \((-1)^n = -1\), so \(X(n) = (1 - (-1))/2 = 1\).
For all \(n \in \mathbb {N}\), \(X(n) = n \pmod2\).
By cases on the parity of \(n\).
If \(m \equiv n \pmod2\), then \(X(m) = X(n)\).
This follows from Lemma 16.