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 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.
 A: 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. 
A: $ 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}$$
A: 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.
