1
$\begingroup$

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?

  • 2
    See the [Chinese remainder theorem](http://en.wikipedia.org/wiki/Chinese_remainder_theorem).2012-01-06

2 Answers 2

2

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

  • 0
    Yes, i'll fix this2012-04-20
2

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