Product of prime powers equal to $1$ in the ring of integers modulo $2^{127}$ I am working with the multiplicative ring of integers modulo $2^{127}$.
Consider the set  $E=\{(k,l) \mid 5^k \cdot 3^l \equiv 1\mod 2^{127}, k > 0, l> 0\}$.
I wonder if anybody knows or has an idea where to look for a result related to a lower bound for $M=\min\{k+l \mid (k,l)\in E \}$.
We have that $0<M\leq \mathrm{ord}_{\mathbb{Z}_{2^{127}}}(5)+\mathrm{ord}_{\mathbb{Z}_{2^{127}}}(3)$ where $\mathrm{ord}_{\mathbb{Z}_{2^{127}}}(5)=2^{125}$ and $\mathrm{ord}_{\mathbb{Z}_{2^{127}}}(3)=2^{125}$ (orders of these primes in the multiplicative ring $\mathbb{Z}_{2^{127}}$).
I also would like to generalize the above for primes other than 5 and 3.
Is there a result about a tighter lower bound for $M$?
 A: Let $k=l=n$ so that $5^k3^l=15^n=(16-1)^n=(2^4-1)^n$. Now take $n=2^{123}$ and apply the binomial theorem, which gives all but the last two terms clearly divisible by $2^{127}$ and the last two terms are
$$-2^{123}\cdot 2^4 +1,$$
which is $1$ mod $2^{127}.$ So here $k+l=2^{124},$ which is a fourth of the value ord(3)+ord(5).
Maybe a lower value can be obtained on using other imposed relations between the exponents $k,l.$
A: Claim:

Let $c=40647290924413185736448652556727923386$, then the set of solutions is
  given by $$A = \{(k,l) \in (\Bbb Z/2^{126} \Bbb Z)^2 \mid 5^k3^l \equiv 1\bmod 2^{127}\}=
 \{(cn, 2 n) \mid n \in \Bbb Z\}$$

This gives an explicit formula for all solutions of $0\leq l+k < 2^{126}$, namely $$l+k = (2n \bmod 2^{126})+(cn \bmod 2^{126})$$ with $0<n<2^{125}$. I find it hard to calculate the minimum of that expression.
Reason:
The set $A = \{(k,l) \mid 5^k3^l \equiv 1\bmod 2^{127}\}$ can be interpreted as a subspace of $(\Bbb Z/2^{126} \Bbb Z)^2$. We only need to find a generator of that subspace to give an explicit characterization of $A$.
This is hard in general, but in the case of the modulus $2^{n}$ we can do the following: Given $k,l \in \Bbb Z/ 2^{n-1} \Bbb Z$ such that  $5^k3^l \equiv 1 \bmod 2^{n}$ we also know that $5^k3^l \equiv 1 \bmod 2^{n-1}$. Conversely, given a solution to the second equation, we can try to lift $(k,l)$ from $ \Bbb Z/ 2^{n-2} \Bbb Z$ to $ \Bbb Z/ 2^{n-1} \Bbb Z$.
Now by consideration $\bmod \,2^3$ it is clear that both $k$ and $l$ are even. We can therefore lift a solution of $5^k3^2 \bmod 2^3$ (my little python code did that pretty instantly) to find that $$5^{c}3^2\equiv 1 \bmod 2^{127}$$ which is of order $2^{125}$ in $\Bbb Z/2^{126} \Bbb Z$ and therefore a generator of $A$. 

EDIT: One can use continued fractions of $c/2^{m}$ to obtain small
 values of $(cn \bmod 2^{m})$ and thus also of $l+k$. The lowest I found so far is $$\begin{eqnarray}
 l&=&11726533429350798020\\
 k&=&\;\,\;\;391079140617450804\\l+k&=&12117612569968248824<\sqrt{2^{127}}<2^{64}.
 \end{eqnarray}$$
A: To flesh my 'birthday paradox' heuristic from a comment out into at least a partial answer:
The core concept is that among the first $m$ values of $5^k$ and the first $n$ values of $3^{-l}$, we have $mn$ different potential collisions, and if we treat these interactions as independent events then we should expect each of them to yield an actual collision with probability $2^{-127}$; this means that within approximately $2^{127}$ potential collisions we should expect an actual collision.  Since $m+n$ is minimized for a given value of $mn$ when $m=n$, then we should expect the minimum value of $m+n$ to occur where $m\approx n$.  Plugging this in to $mn\approx 2^{127}$ yields $m\approx n\approx 2^{64}$ and $m+n\approx 2^{65}$ (up to relatively small constant factors).
Of course, this is a heuristic argument, not an exact one; but as long as $m\gg \log_5 2^{127}\approx 55$ and $n\gg\log_3 2^{127}\approx 80$, then I would expect the sets $\{5^k\ |\ 0\leq k\lt m\}$ and $\{3^{-l}\ |\ 0\leq l\lt n\}$ to be roughly equidistributed mod $2^{127}$; since the numbers we're talking about are many orders of magnitude larger then this assumption seems reasonable.
Note that if the goal were to minimize $|k|+|l|$ then this heuristic argument can be extended to provide an explicit upper bound of  $2\lceil\sqrt{2^{127}}\rceil$: among the $2^{127}$ values of $5^k3^l\bmod 2^{127}$ for $1\leq k\leq \lceil\sqrt{2^{127}}\rceil$, $1\leq l\leq \lceil\sqrt{2^{127}}\rceil$ there must (by the pigeonhole principle) be a collision, say $5^{k_0}3^{l_0} \equiv 5^{k_1}3^{l_1}$.  Then dividing out, we obtain $5^{k_0-k_1}3^{l_0-l_1}\equiv 1$, where clearly $0\leq |k_0-k_1|\leq\lceil\sqrt{2^{127}}\rceil$, and likewise for the $l$ values.  (This argument doesn't work for the actual problem, of course, because there's no guarantee that $k_0-k_1$ and $l_0-l_1$ have the same signs.)
