We have $\gcd(2^{2019}, 3^{2019})=1$. Solve $2^{2019}k \equiv 1 \mod{3^{2019}}$ and $3^{2019}j \equiv 1 \mod{2^{2019}}$ for $k$ and $j$ integers

Question

We have $\gcd(2^{2019}, 3^{2019})=1$. Solve $2^{2019}k \equiv 1 \mod{3^{2019}}$ and $3^{2019}j \equiv 1 \mod{2^{2019}}$ for $k$ and $j$ integers. I have tried to find the solution of the diophantine $1=2^{2019}k -3^{2019}j$ equation but I have not succeeded.

Answer 1

By Euler's theorem,

$$ 2^{\phi(3^{2019})}\equiv 1 \ \mathrm{mod} \ 3^{2019}, $$

and we have $\phi(3^{2019})=(3-1)3^{2018} = 2 \cdot 3^{2018}>2019$.

Thus, we can take $$ k=2^{2\cdot 3^{2018} - 2019}. $$

It is possible to find $j$ by the similar process.

Answer 2

$ 2 \times2^{-1} ≡ 1 ≡ 1 + 3^{2019} \mod 3^{2019}$

$$k ≡ (2^{-1})^{2019} ≡ \left({1 + 3^{2019} \over 2}\right)^{2019} \mod 3^{2019}$$

$ 3 \times3^{-1} ≡ 1 ≡ 1 + 2^{2019} \mod 2^{2019}$

$$j ≡ (3^{-1})^{2019} ≡ \left({1 + 2^{2019} \over 3}\right)^{2019} \mod 2^{2019}$$

Result confirmed in Python

>>> b2 = 2**2019
>>> b3 = 3**2019
>>> k = pow((1+b3)//2, 2019, b3)
>>> j = pow((1+b2)//3, 2019, b2)
>>>
>>> k*b2 % b3, j*b3 % b2
(1L, 1L)

---

We can reduce computation further, by doing only j, with the smaller pow-of-2 mod.

$$k ≡ {1 - (3^{2019} )j \over 2^{2019}} ≡ -\Bigl\lfloor {(3^{2019} )j \over 2^{2019}} \Bigr\rfloor \mod 3^{2019}$$

Answer 3

A somewhat dirty answer comes from a trick occasionally used in similar situations. My goal is to give you more than what was required, namely integers $u$ and $v$ such that $$3^{2019}u+2^{2019}v=1.$$ The catch is that while I give a recipe for a pair of such integers $(u,v)$, the resulting formula is not really suited for efficient calculations.

We have the obvious identity $$3-2=1.$$ Raise both sides of this to the power $2\cdot2019-1=4037$ to arrive at $$ (3-2)^{4037}=1. $$ Expand the left hand side using the binomial formula. The exponents $j,k$ in a term involving $3^j2^k$ satisfy $j+k=4037$, so you see that all the terms are divisible by either $3^{2019}$ or $2^{2019}$. Collect the terms together according to which holds.

---

One more general setting, where the same trick works is the case of a ring $R$ together with two ideals $I,J$ such that $I+J=R$. The trick then gives a proof for the fact that for all positive integers $n,m$ we still have $I^n+J^m$ even though the powers of ideals are more often than not strictly smaller the higher the exponent. Anyway, the assumption gives the existence of $i\in I, j\in J$ such that $i+j=1$. Then also $(i+j)^{n+m+1}=1_R$, and we can proceed as above. The identity $i+j=1$ implies that $i$ and $j$ commute, and hence the binomial formula works even without assuming that $R$ would be commutative.