How do I solve a system of equations containing a modulus function?

Question

I'm trying to solve this system of equations for $a$: $$\frac{3n+1}{2^{a-1}} \mod 2 = 1$$ $$n \mod 2 = 1$$ for any odd input $n$.

I know that there is only $1$ solution for every possible $n$ value. For example, if $n=9$, then $a=3$, however, I am unable to solve algebraically for $n$. Is it possible to do so?

Answer 1

By definition if $x \mod 2 = 1$, then $x$ is odd.

If $n$ is guaranteed odd, then the second equation is guaranteed.

The numerator $3n + 1$ of the first equation is always positive and even. But after dividing by $2^{a-1}$ we want the output to be odd. Thus, this problem is in a way about prime factors. Think of the prime factorization:

$$3n + 1 = 2^{x} \cdot \prod_{i=1}^{b} p^{\, x_i}_{\,i}$$.

$x$ represents the number of $2$'s in the prime factorization of $3n + 1$. By definition of the primes greater than $2$, $p_{\, i}$ must be odd for every $i$. With this, we know

$$ \frac{3n+1}{2^{a-1}} = 2^{x - a + 1} \cdot \prod_{i=1}^{b} p^{\, x_i}_{\,i}$$

and this number can only be odd if $a = x + 1$ (if $a < x + 1$, there would be a $2$ left which makes it even, and if $a > x + 1$, the modulus would be a fraction).

This all being said, I don't think there is an analytical closed-form formula for the number of $2$'s in the prime factorization of a number.

Answer 2

Fixed $\; a>1 \;$, different solutions can be found for $\; n$

if $\; a \;$ even then $\quad n \equiv \frac{5 \cdot 2^{a-1}-1}{3} \pmod {2^a}\;$ are solutions

if $\; a \; $ odd then $\quad n \equiv \frac{2^{a-1}-1} {3} \pmod {2^a}\;$ are solutions

Or given $n$ odd you can analyze its binary representation starting from the least significant bit for example:

$ \cdots 11\quad ,\quad \cdots 1101\quad, \quad \cdots 110101 \quad, \quad \cdots11010101 \quad, \quad \dots \quad $

which corresponds to

$ a=2\quad ,\quad a=4 \quad, \quad a=6\quad, \quad a=8\quad, \quad \dots \quad $

or

$ \cdots 001\quad ,\quad \cdots 00101\quad, \quad \cdots 0010101 \quad, \quad \cdots001010101 \quad, \quad \dots \quad $

which corresponds to

$ a=3\quad ,\quad a=5\quad, \quad a=7\quad, \quad a=9\quad, \quad \dots \quad $