Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|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
1  
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
2  
See the Chinese remainder theorem. –  lhf Jan 6 '12 at 13:00

2 Answers 2

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|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|improve this answer

Your Answer

 
discard

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.