# 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$?

-
P.S.: By the way, $k+l>1+1=2$ because $5\cdot 3=15\not \equiv 1 \mod 2^{127}$ and $\mathrm{ord}_{\mathbb{Z}_{2^{127}}}(15)=2^{123}$. Of course, I can program an algorithm that would search for the pair with smallest sum. But the search would have to be done with small bounds for $k$ and $l$ otherwise it would take unrealistic amount of time to finish. Even with these small bounds for $k$ and $l$, the algorithm may not give an answer if the values $k$ and $l$ with smallest sum are greater than the bounds used in algorithm. –  Dash Feb 22 '14 at 2:24
This isn't a tight bound in either direction, but heuristically Birthday Paradox-style arguments suggest that after you've had roughly $\sqrt{2^{127}}\approx 2^{64}$ numbers of the form $5^k$ and the same number of numbers of the form $3^{-l}$ then you should expect a collision, and that you shouldn't expect a collision much before that point, so your $M$ should be in the general range of $2^{64}$ 'on average'. –  Steven Stadnicki Feb 22 '14 at 2:56

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}$$

-
I checked the results you obtained and they work. Thanks for that. But I have few questions about the way you obtained them. First, when you wrote "Conversely, given a solution to the second equation, we can try to lift $(k,l)$ from $\mathbb{Z}/2^{n-2}\mathbb{Z}$ to $\mathbb{Z}/2^{n-1}\mathbb{Z}$. I don't see why it is true for mod $2^{n}$ for any $n$ positive integer. The other way around is true. –  Dash Mar 28 '14 at 6:35
Second, when obtaining the value of $c$ such that $5^{c}3^2\equiv 1 \bmod 2^{127}$, does your code search through all even numbers until it finds? I am not able to replicate your experiment (that is just because I'm good at programming). Finally, you mentioned that $5^{c}3^2\equiv 1 \bmod 2^{127}$ has order $2^{125}$. I think you meant that is the order of $5 \bmod 2^{127}$, right? –  Dash Mar 28 '14 at 6:35
Let me adress your questions in two different comments: 1. You are right, we can't always lift a solution of from $\mod 2^{n-1}$ to $\mod 2^{n}$. That's why I said "try". However, it works sufficiently often that a little DFS gives the answer immediately: If $5^k3^2\equiv 1 \bmod 2^{n-1}$, try $5^k3^2$ and proceed recursively, if this fails try $k \to 2^{n-3}+k$. This works as a general method if we know that there must be a solution to $5^k3^2\equiv 1$. In this case we know by order arguments. –  benh Mar 28 '14 at 7:24
I hope the last comment also answered the first question of your second comment. Regarding the second question, I meant something else: Consider the set of all solutions $$G:=\{(k,l) \mid 5^k3^l \equiv 1 \bmod 2^{127}\},$$ then this set forms a subgroup $G\subset\Bbb Z /2^{126}\Bbb Z \times \Bbb Z/2^{126} \Bbb Z$. This subgroup $G$ is itself isomorphic to $\Bbb Z/2^{125} \Bbb Z$. Therefore it is enough to see that the element $(c,2)$ has order $\Bbb 2^{125}$ in $Z /2^{125}\Bbb Z \times \Bbb Z/2^{125} \Bbb Z$ to see that $(c,2)$ is a generator for $G$. –  benh Mar 28 '14 at 7:29

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.$

-
@user129118 So the minimal $k+l$ is at most $2^{124}$... This seems like it might be way more than the actual minimum. I've looked at trying a pigeon-hole type argument on the set of $5^k3^l$ of which there are $2^{250}$ "pigeons", and only $2^{127}$ "holes", so some residue class gets a lot of pigeons in it, any two of which produce a solution to $5^k3^l=1$ mod $2^{127}.$ I don't know if this leads anywhere. –  coffeemath Feb 16 '14 at 22:31
Oh, I understood that is not exactly a tight lower bound for $M$ but at least it decreased the upper bound. I will continue to look for some suitable lower bound. Thank you very much for the help. I hope anyone out there knows any result the can be applied to what I need. –  Dash Feb 17 '14 at 3:19

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.)

-