I want to find the smallest solution, $x$, for $$a^x = b \bmod 2^N$$ by using p-adic logarithm.
We suppose $a \bmod 4 =1$ and $b \bmod 4 = 1$. Another case can be solved easily or converted to $a, b \bmod 4 = 1$ case. For $a \bmod 4=1$, and $b \bmod 4 = 1$, p-adic logarithm can be defined as you can find in the link above. Then by using 2-adic logarithm, $x$ can be write as below. $$x = \frac{\log{b}}{\log{a}}$$ However, this solution is not always the smallest solution. For example, let's consider the problem, $$5^x = 9 \bmod 16$$ by using 2-adic logarithm. Since $9\bmod 4 = 1$ and $5\bmod 4=1$, 2-adic logarithm can be defined for $9$ and $5$. Then $x = \log(9) / \log(5)$ . Let's calculate the $\log{9}$ and $\log{5}$ by formal power series. $$\log(1 + 8) = 8 - (1/2) 8^2 + ... = 8$$ $$\log(1 + 4) = 4 - (1/2) 4^2 + ... = -4 = 12$$ Then, $\log(9) / \log(5) = 2 / 3$. Since $3$ is coprime to $16$, inverse of $3$, $3^{-1}=11 \bmod 16$, can be found by extended euclidean algorithm (or by expanding $1/3=1-2+2^2-2^3+2^4-...$). Then, $x=2/3=2\times 11=6 \bmod \phi(16)$. Here, $\phi(n)$ is the Euler function of $n$. We find the solution, $x=6$. Let's check this is actually the solution, $$5^6 = 15625 = 9 \bmod 16$$. However, this is not the smallest solution. The smallest solution of $x$ is $x=2$ as below. $$5^2=25=9 \bmod 16$$ We can find such case infinitely. My question is, can we construct the smallest solution by using p-adic logarithm?
You can't just render $8/12\equiv 2/3\bmod 16$. The denominator $12$ does not have a multiplicative inverse $\bmod 16$ and therefore the familiar rules for division do not apply.
We start with the equation
$12x\equiv 8\bmod 16$
The modulus on $x$ in the logarithmic equation is not the Euler totient of the modulus in the original equation, rather it is the original modulus itself, in this case $16$. The reason for this is connected with $\log(1\pm u)$ having the same valuation as $u$ itself. Here, $1-9/5^x$ is to be rendered with $2$-adic valuation $\le 1/16$ to satisfy the original equation $\bmod 16$, so we must have $|\log(9/5^x)|\le(1/16)$ forcing $\log 9\equiv x\log 5\bmod 16$, not just $\bmod 8$. Similarly in an exponential equation to be satisfied $\bmod 2^n$, the logarithms must be equated $\bmod 2^n$ not $\bmod \phi(2^n)$. The relation $|\log(1\pm u)|=|u|$ also holds $p$-adically for other primes $p$, so more generally an exponential equation $\bmod p^n$ must have a logarithmic equation also holding $\bmod p^n$.
To solve the logarithmic equation above, properly rendered $\bmod 16$, you can divide both sides by $4$ but then, you also have to divide the modulus itself by $\text{gcd}(16,4)=4$. Thus properly,
$3x\equiv 2\bmod 4$
Thereby $x\equiv 2\bmod 4$ showing that $x=6$ is a solution but also $x=2$ is the minimal one.
This reduction in the modulus may also be rendered in $2$-adics. When you (correctly) render the following $2$-adic logarithms
$\log 5 =...1100$
$\log 9 = ...1000$
you can then assert that
$(...1100)x=...1000$
but you cannot divide by the coefficient of $x$ because this has terminal zeroes and thus no multiplicative inverse. You have to cancel the terminal zeroes in $...1100$ with those of $...1000$. Fortunately the constant term $...1000$ has enough terminal zeroes to do that in $2$-adic integers, so you end with
$(...11)x=...10$
You have now enabled the division, but at the price of having only two bits to work with. Thus you obtain $x=...10$ or, in modular arithmetic, $x\equiv 2\bmod 4$. The cancellation required to enable the division is equivalent to reducing the modulus in the earlier treatment.
Despite this reduction, it is easily proven that the residue of $x\bmod 4$ is sufficient to fix $5^x\bmod 16$. From the binomial theorem:
$5^{4k+2}=(4+1)^{4k+2}=\text{(binomial terms with factor 4^2=16)}+4(4k+2)+1\equiv 9\bmod 16$
thus showing that the residue of $x$ need be rendered only $\bmod 4$ to solve the original equation $\bmod 16$.