1. ## Modulo equation

Here's the question:

Determine the value of $\displaystyle \ x \ , \ 0 \leq x < 15$, if $\displaystyle x$ satisfies:

$\displaystyle x \equiv 2 \ (\mathrm{mod} \ 3)$
$\displaystyle x \equiv 4 \ (\mathrm{mod} \ 5)$
From these congruences, I can write

$\displaystyle \frac {x-2}{3} = k \ , \ k \in \mathbb{Z}$

$\displaystyle \frac {x-4}{5} = p \ , \ p \in \mathbb{Z}$

From which we get that

$\displaystyle x = 3k + 2$

$\displaystyle x = 5p + 4$

Ergo,

$\displaystyle 3k + 2 = 5p + 4$

Now, I managed to find different values for p and k through trial and error so that the left side and right side of the equation become the same number (which is 14). And that's the answer for the question.

But my question is: isn't this possible to do algebraically or at least numerically rather than through trial and error?

Correct me if I am wrong; but isn't this a Diophantine equation which has to be solved with Euclides algorithm?

Thanks!

2. ## Re: Modulo equation

More specifically it's an example of the Chinese remainder theorem.
Chinese remainder theorem - Wikipedia, the free encyclopedia

And yes, this involves the extended Euclidean algorithm.
The wiki page contains an algorithm and an example of how it works.

The solution in your case is simple enough not to need the Euclidean algorithm though:

$\displaystyle x \equiv 2 \cdot 5 \cdot [5^{-1}]_3 + 4 \cdot 3 \cdot [3^{-1}]_5 \pmod{3 \cdot 5}$

$\displaystyle x \equiv 2 \cdot 5 \cdot 2 + 4 \cdot 3 \cdot 2 \pmod{15}$

$\displaystyle x \equiv 14 \pmod{15}$

3. ## Re: Modulo equation

I did not understand what you did there.

4. ## Re: Modulo equation

In the wiki article there is a section about the case of two equations:
Chinese remainder theorem - Case of two equations - Wikipedia, the free encyclopedia

The equations:
have the solution:
which is $\displaystyle \pmod{n_1 \cdot n_2}$,
and which assumes that $\displaystyle n_1$ and $\displaystyle n_2$ are coprime.

I substituted the values from your equations.

In particular $\displaystyle [5^{-1}]_3$ represents the inverse of 5 (mod 3).
This is the number that multiplied by 5 yields 1 (mod 3).

Since:
$\displaystyle 5 \cdot 2 \equiv 10 \equiv 1 \pmod 3$
we conclude that:
$\displaystyle 5^{-1} \equiv 2 \pmod 3$

5. ## Re: Modulo equation

Hmm, okay.

But, could you please thoroughly show me the Diophantine/Euclides algorithm approach? Thx!

6. ## Re: Modulo equation

I think you mean the Chinese remainder theorem/Euclidean algorithm approach?

Well, I recommend you read the wiki article.
It explains it much better than I can.

If you have questions, perhaps I can answer those...?

7. ## Re: Modulo equation

I just want to know how I can solve this "equation"

$\displaystyle 3k + 2 = 5p + 4$

when considering it as a linear Diophantine equation.

Now, the Euclidean algorithm is used for calculating the greatest common factor here. But how is that useful and how is it actually used in equations like these?

So, I would appreciate it if you could show me the procedure of using the Euclidean algorithm in order to find a value for x?

8. ## Re: Modulo equation

here is an equivalent approach. it may seem mysterious why this works, but it really is just the chinese remainder theorem in disguise.

x = 2 (mod 3)
x = 4 (mod 5).

therefore, since gcd(3,5) = 1:

5x = 10 (mod 15)
3x = 12 (mod 15), so:

8x = 22 = 7 (mod 15).

so 2(8x) = 2(7) = 14 (mod 15)
16x = x = 14 (mod 15) (because 16 = 1 mod 15).

the question in your mind should be, how did i know to multiply by 2? well, gcd(8,15) = 1, so 8 is invertible (mod 15). finding the inverse of 8 involves the euclidean algorithm, and for a larger modulus, i would have to use it, but 15 is a pretty small modulus, and the only possible inverses for 8 are 1,2,4,7,8,11,13 and 14.

the point is, you need to study how integers mod n behave in more depth. the divisors of n MATTER. congruences mod 6 are going to be less user-friendly than congruences mod 7 (it is possible to write down equations which simply cannot be solved mod 6). the numbers co-prime to n matter, they are the only ones we can safely "undo" multiplication by.

2x = 5 (mod 6) has no solution. why? because gcd(2,6) IS NOT 1.

to the general case:

if x = a (mod m) and x = b (mod n), and gcd(m,n) = 1, then:

nx = na (mod mn) and mx = mb (mod mn). if we add these two equations, we get:

(m+n)x = na + mb (mod mn). now this has a (unique) solution iff gcd(m+n,mn) = 1.

suppose gcd(m+n,mn) ≠ 1, say it was d instead. let p be some prime dividing d.

since p divides d, which divides mn, p divides mn, and since gcd(m,n) = 1, p divides either m or n (but not both).

so p cannot possibly divide m+n (if p divides m, then n = (m+n) - m. if p divided both of these, it would divide n, too

a similar argument holds if p divides n). so if there is any prime which divides d, we get a contradiction.

so gcd(m+n,mn) = 1. so m+n is invertible mod mn.

this gives us the solution x = (m+n)^(-1)(na + mb) (mod mn).

although this "looks" different, it really is the same answer.

9. ## Re: Modulo equation

Originally Posted by SweatingBear
I just want to know how I can solve this "equation"

$\displaystyle 3k + 2 = 5p + 4$

when considering it as a linear Diophantine equation.

Now, the Euclidean algorithm is used for calculating the greatest common factor here. But how is that useful and how is it actually used in equations like these?

So, I would appreciate it if you could show me the procedure of using the Euclidean algorithm in order to find a value for x?
Well, your example is perhaps too simple to illustrate the extended Euclidean algorithm, but here goes.

First I'll rewrite your equation to -5x + 3y = 2.

With the extended Euclidean algorithm we find x and y, such that -5x + 3y = gcd(5,3) = 1.

To this end we iterate through a sequence of $\displaystyle -5x_i + 3y_i = d_i$, ending in $\displaystyle d_i=0$

For the setup we start with $\displaystyle x_1=1, y_1=0, x_2=0, y_2=1$.
Code:
i   -5x_i + 3y_i = d_i   q_i
1      1      0    -5
2      0      1     3    -2
In each iteration we divide $\displaystyle d_{i-1}$ by $\displaystyle d_i$ to find the quotient $\displaystyle q_i$.
In the first step that gives a quotient of -2.

Then we subtract q_i times the equation from the previous step.
Code:
i   -5x_i + 3y_i = d_i   q_i
1      1      0    -5
2      0      1     3    -2
3      1      2     1     3
4                   0
That is:
$\displaystyle x_{i+1}=x_{i-1} - q_i x_i$
$\displaystyle y_{i+1}=y_{i-1} - q_i y_i$
$\displaystyle d_{i+1}=d_{i-1} - q_i d_i$
This is repeated until we hit zero, which already happened at step 4.

Now we've found in step 3 that:
$\displaystyle -5 \cdot 1 + 3 \cdot 2 = 1$
Multiply the entire equation by 2 to find:
$\displaystyle -5 \cdot 2 + 3 \cdot 4 = 2$
which is the solution you requested.

10. ## Re: Modulo equation

Let's try this again:

You have -5p+3k=2 for which you want to find integers p and k.

$\displaystyle -5 \cdot 1 + 3 \cdot 0 = -5$
$\displaystyle -5 \cdot 0 + 3 \cdot 1 = 3$

Dividing -5 by 3 gives 2 with remainder 1.
So we add the second equation times 2 to the first equation:

$\displaystyle \begin{matrix}-5 \cdot 1 + 3 \cdot 0 &=& -5 & \\ -5 \cdot 0 + 3 \cdot 1 &=& 3 & \qquad \times 2 + \\ \hline \\ -5 \cdot 1 + 3 \cdot 2 &=& 1 & \end{matrix}$

This is the lowest value we can get for the right hand side.
Since we need a right hand side of 2, we multiply by 2:
$\displaystyle -5 \cdot 2 + 3 \cdot 4 = 2$

So your solution is $\displaystyle x=3 \cdot 4+2=14$