Solving simultaneous congruences

[Quadrat]

Homework Statement

[/B]
Find all integers $n$ which satisfies $n\equiv_7 13$ and $n \equiv_5 2$

Homework Equations

-

The Attempt at a Solution

[/B]
I get that $n\equiv_7 13$ is the same thing as $n\equiv_7 -1$ and more generally $n={-1}+7x$, {$x\cup \mathbb{Z}$} for any multiple of 7.

The other congruence could be written as $n=2+5y$, {$y\cup \mathbb{Z}$}.

I can input different integers for $x$ and $y$ and by doing that I can see that $27$ solves both congruences. Since $5$ and $7$ is relative prime the solution should be $n=27+(5*7)$ and more generally $n=27+(5*7)z$, {$z\cup \mathbb{Z}$}.

But I believe this is just a cheap way of finding the solution. How can one go about to make a better solution? It would prolly involve diophantine equations? It feels like I just got lucky this time. Anyone got a tips on how to attack these types of problems in a better way? Thanks

 

[S.G. Janssens]

You may want to look into the Chinese remainder theorem.

 

[HallsofIvy]

n= 13 (mod 7) is the same as n= 6 (mod 7) or n= 6+ 7k for some integer k. Similarly, n= 2 (mod 5) is the same as n= 2+ 5i for some integer i. Then 6+ 7k= 2+ 5i which gives 5i- 7k= 4, a Diophantine equation.

 

[Quadrat]

n= 13 (mod 7) is the same as n= 6 (mod 7) or n= 6+ 7k for some integer k. Similarly, n= 2 (mod 5) is the same as n= 2+ 5i for some integer i. Then 6+ 7k= 2+ 5i which gives 5i- 7k= 4, a Diophantine equation.

Oh, of course! So when I use Euclid's algorithm I end up with $7=1*5+2$ and $5=2*2+1$. How can I make any sense of this in my case? I've seen examples where you do the extended Euclid's algorithm and you get all these terms which you substitute to end up with something that solves the linear relation but I only get two lines with a remainder $\neq0$.

 

[HallsofIvy]

Oh, of course! So when I use Euclid's algorithm I end up with $7=1*5+2$ and $5=2*2+1$. How can I make any sense of this in my case? I've seen examples where you do the extended Euclid's algorithm and you get all these terms which you substitute to end up with something that solves the linear relation but I only get two lines with a remainder $\neq0$.

I would write those as 7- 5= 2 and 5- 2(2)= 1. So 5- 2(7- 5)= 3(5)- 2(7)= 1. Can you finish that? What do you need to do to get "= 4"?

 

[Quadrat]

I would write those as 7- 5= 2 and 5- 2(2)= 1. So 5- 2(7- 5)= 3(5)- 2(7)= 1. Can you finish that? What do you need to do to get "= 4"?

Thanks HallsofIvy. Right! So I just multiply both sides by 4 (and keep the coefficiants unchanged) and end up with $12(5)-8(7)=4$. So all the solutions for the variables as you named them $i$ and $k$ would be $i=12-8*m$ and $k=(-8)+12*m$, {m∪ℤ}, right?

But how do I get from this to finding n via this method?

 

[HallsofIvy]

The initial problem was to find n such that n= 13 (mod 7)= 6 (mod 7) which is the same as n= 6+ 7k for some k, and n= 2 (mod 5) which is the same as n= 2+ 5i for some integer i. That led to the Diophantine equation 5i- 7k= 4. You are correct that 12(5)- 8(7)= 4 but from that point you have several errors: i= 12 and k= 8 (NOT -8) satisfy the equation, the "-" was already in the equation. Also if we add any multiple of the coefficient, 5 (NOT the solution, 12), to k, k= 8+ 5m, and any multiple of the coefficient, 7, (NOT the solution, 8) to i, i= 12+ 7m will satisfy that equation: 5(12+ 7m)- 7(8+ 5m)= 60+ 35m- 56- 35m= 4 for all m.

The original problem was to find n such that n= 13= 6 (mod 7) and n= 2 (mod 5). The first is the same as saying n= 6+ 7k and the second is the same as n= 2+ 5i for integers k and i. Now that we have found that k= 8+ 5m and i= 12+ 7m, we can find n: if k= 8+ 5m then n= 6+ 7(8+ 5m)= 6+ 56+ 35m= 62+ 35m for any integer, m. If i= 12+ 7m, then n= 2+ 5(12+ 7m)= 2+ 60+ 35m= 62+ 35m for any integer m. Use that to find n in terms of the general integer, m.