# How to solve linear system with modulus operation?

I came across linear equation $G(x,y) = g_k(x,y) l_k(x,y)$ mod $(y^{2^{k}})$ while reading factoring algorithm see section 3 for bivariate polynomials. I need to find the $G(x,y)$ and $l_k(x,y)$.

Given : $g_k(x,y)$, where $deg_y(g_k(x,y)) < y^{2^{k}}$ and $deg_x(g_k(x,y)) < d$.

Find : $G(x,y)$ and $l_k(x,y)$. (non trivial)

I know that $G(x,y) = g_k(x,y) l_k(x,y)$ forms a linear system with $y^{2^{k +1}} \times 2d$ many equations and I can solve those equations. But I don't know how to solve correctly $G(x,y) = g_k(x,y) l_k(x,y)$ mod $(y^{2^{k}})$.

Here is a problem, suppose after multiplying $g_k(x,y)$ and $l_k(x,y)$, I got a term $y^{2^{k}}$, but after doing mod operation this term is going to become $0$. So my question is, how to resolve this issue.

• Choose $G = g_k$ and $l_k = 1$. I think you're missing something. – Yuval Filmus Mar 18 '17 at 8:26
• @Yuval Filmus yes, I have edited my question. I am looking for non trivial $G$ and $l_k$ – aaag Mar 18 '17 at 8:29
• You can solve the equation for every $l_k$ by calculating $G$ using the formula $G = g_k l_k \bmod{y^{2^k}}$. – Yuval Filmus Mar 18 '17 at 8:40
• But sill there is a problem that I have mentioned in the second last line. – aaag Mar 18 '17 at 8:49
• Why is terms being 0 a problem? Do you know how to compute modular inverses? – Discrete lizard Mar 27 '17 at 6:59