Here is my problem:

$$2^x \equiv a \pmod{3^n}.$$

where, $a\not\equiv 0 \pmod{3}$ and $n\in \mathbb{Z^{+}}$

I want to learn that,


$x=\left\{ {{3^n-\binom{n}{2}}-1}\right\}-f(n)$

$a=\sum_{j=0}^{n-1} 3^{n-j-1} 2^{3^j - \binom{j+1}{2} -1}=2^{3^{n-1}-\frac {n(n-1)}{2}-1}+3\cdot2^{{3^{n-2}-\frac {(n-1)(n-2)}{2}-1}}+3^2\cdot2^{{3^{n-3}-\frac {(n-2)(n-3)}{2}-1}}+\cdots+3^{n-1}$

Is it possible to find a general solution that depends on $n$?

I found these values with algorithmic ways:


The exact form of the problem is:

$$2^{\left\{ {{3^n-\binom{n}{2}}-1}\right\}-f(n)}\equiv \sum_{j=0}^{n-1} 3^{n-j-1} 2^{3^j - \binom{j+1}{2} -1} \pmod{3^n}.$$

Question: For $f(n)$ is it possible to find a closed-form expression depends on $n$ , which that $f:\mathbb{N}\to\mathbb{N}$ such that $f(n)\in\mathbb{N}_{>0}$ ?

Small supplement:

Is it possible to find an algebraic closed form for $n\to\infty$ , can the simpler function $f'(n)$ be found, which gives $\lim_{n\to\infty} \frac{ f(n)}{f'(n)}=1$ ?

I mean, for example, if $f(n)=2^n+n^2+n$

We get, for $f'(n)=2^n.$

Is something like this possible?

  • 1
    $\begingroup$ Well, more or less by definition, $x$ is the discrete logarithm (of $a$ to the base $2$ in $\Bbb Z/3^n$). So I guess the question is: Is there a formula/method/algorithm to compute its value, for given $a$ and $n$? $\endgroup$ – Torsten Schoeneberg Apr 14 '18 at 16:53
  • 4
    $\begingroup$ Wow, 29 edits. I think I'll wait until the question settles down. $\endgroup$ – Gerry Myerson Jul 8 '18 at 3:55
  • 2
    $\begingroup$ Now up to 38 edits! Student, if you can go one month without making any more edits, let me know, and I'll come back to have a look at the question. $\endgroup$ – Gerry Myerson Jul 9 '18 at 7:22
  • 3
    $\begingroup$ Which of the 45(!) versions of the question would you like me to comment on? I have already told you, I will refuse to even glance at the question as long as you are changing it every couple of hours. When you can go a month without making any changes in the question, that's when I'll take it seriously. $\endgroup$ – Gerry Myerson Jul 10 '18 at 12:58
  • 3
    $\begingroup$ @Gerry Myerson dear Teacher, I finished one month, as you want. Please tell me what I need to do now.. Best Regards. $\endgroup$ – Elvin Aug 8 '18 at 4:24

We know that there is a solution, since $2$ is a primitive root for all powers of $3$.

For smallish values of $n$, we could solve this by iterating up the powers of three: solve $\bmod 3$ giving $x_1$, then calculate for the $3$ possible values $\bmod 9$, checking $x_1, x_1{+}2, x_1{+}4$ to find $x_2,$ then the $3$ possible values $\bmod 27$, $x_2, x_2{+}6, x_2{+}12$ to find $x_3$ etc. up to $x_n$.

At each step you have the (smallest) solution $x_k$ to $2^{\large{x_k}}\equiv a \bmod 3^k$. Then $x_k{+}\phi(3^k)$ and $x_k{+}2\phi(3^k)$ also solve this. Larger solutions will be greater than $\phi(3^{k+1})$ so one of these three values will be $x_{k+1}$, solving as the smallest solution to $2^{\large{x_{k+1}}}\equiv a \bmod 3^{k+1}$.

This process is relatively quick when you are using exponentiation by squaring.

For example this can quickly solve $2^x\equiv 4827836 \bmod 3^{17}$ as $x\equiv 16391041 \bmod \phi(3^{17})$. That is to say, $x = 16391041$ is the smallest solution and Euler's theorem means that you can add any multiple of $\phi(3^{17}) = 86093442$ for another valid result.

Your example of $2^x\equiv 8164718 \bmod 3^{15}$ solves to $x\equiv 5032989 \bmod \phi(3^{15})$.

  • 1
    $\begingroup$ @Student: There is no unique solution, if that is what you mean. What Joffan writes amounts to: The solutions to your example are $5032989, 5032989+\phi(3^{15}),5032989+2\phi(3^{15}),...$. $\endgroup$ – Torsten Schoeneberg Apr 14 '18 at 17:11
  • 1
    $\begingroup$ @Student A function-like expression? no, that isn't possible. $\endgroup$ – Joffan Apr 14 '18 at 18:12
  • 1
    $\begingroup$ I guess that is a matter of perception. This seems like a simple way to me; certainly better than calculating every value of $2^x$ up to $\phi(3^n)$. It involves (at most) $3n$ calculations of $2^m \bmod 3^k$. $\endgroup$ – Joffan Apr 14 '18 at 19:25
  • 2
    $\begingroup$ I note that this method is Hensel lifting applied to the sequence of polynomials $u^{x_k} - a$, picking the lift that keeps $2$ as a root at each step. $\endgroup$ – Eric Towers Apr 14 '18 at 20:04
  • 2
    $\begingroup$ @Student: Except for "trivial" problems, like $a = 2^y$ for small values of $y$, we only have algorithmic solutions. The one here has the advantage that we get all solutions for $3^1, 3^2, \dots, 3^n$ for the same amount of effort. But we do not know a direct method. There is always hope that, in the future, someone will have insight into the hidden structure of the problem and find a more direct method. $\endgroup$ – Eric Towers Apr 15 '18 at 20:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.