# Solving equations of the type : $y=k_2\pmod{k_1},y=k_1\pmod{k_2}$ for $y$

I solved today the equations:

$y=4\pmod 3$ and $y=3\pmod 4$ where $y$ is an integer.

(Probably infinite number of solutions) by writing down:

• $3k_1=y-4$

• $4k_2=y-3$

$\Rightarrow 3k_1=-1+4k_2$

and one solution (in integers) is for $k_2=5,k_1=1 \rightarrow y=19$

Is there a 'smarter' solving this kind of equations? Is there a sufficient/necessary conditions for a solution to exist?

-
what is y%3=4 and y%4=3? –  Paul Jan 6 '12 at 12:54
@Paul - y modulo 3 is 4 and y modulo 4 is 3 –  Belgi Jan 6 '12 at 12:55
Do you know how to type the equations in LaTeX? I recommend you to learn it. It makes your equation more readable. –  Paul Jan 6 '12 at 12:57
I'll start learning LaTex in the near future –  Belgi Jan 6 '12 at 12:59
See the Chinese remainder theorem. –  lhf Jan 6 '12 at 13:00

You should look at methods of solving diophantine equations.

Assume you want to find integers $x,y\in\mathbb{Z}$ such that $ax+by=c$ where $a,b,c\in\mathbb{Z}$. It is well-known that solution exist iff $c$ divides $\operatorname{gcd}(a,b)$. Moreover if you know that a pair $(x_0, y_0)$ is a solution, then general solution is given by $$x=x_0+\frac{b}{\operatorname{gcd}(a,b)}\cdot t$$ $$y=y_0-\frac{a}{\operatorname{gcd}(a,b)}\cdot t$$ where $t\in\mathbb{Z}$. Now you can apply all this results to your equation $3k_1-4k_2=-1$ and get the following result $k_1=1+3t$, $k_2=-1+4t$ where $t\in\mathbb{Z}$. Hence $y=3k_1+4=1+12t$, where $t\in\mathbb{Z}$.

-
You mean Diophantine =] –  Tara B Apr 20 '12 at 18:13
Yes, i'll fix this –  Norbert Apr 20 '12 at 18:14
$y=k_1+k_2 \pmod {k_1\cdot k_2}$
$k_1+k_2=k_1 \pmod{k_2}=k_2 \pmod{k_1}$