Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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
up vote 2 down vote accepted

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

share|cite|improve this answer
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}$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.