Thread: Modulo equation

Here's the question:

Determine the value of , if satisfies:

From these congruences, I can write





From which we get that





Ergo,



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!

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:

I did not understand what you did there.

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 ,
and which assumes that and are coprime.


I substituted the values from your equations.

In particular represents the inverse of 5 (mod 3).
This is the number that multiplied by 5 yields 1 (mod 3).

Since:

we conclude that:

Hmm, okay.

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

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...?

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



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?

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.

Originally Posted by SweatingBear

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



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 , ending in

For the setup we start with .

Code:

i   -5x_i + 3y_i = d_i   q_i
1      1      0    -5     
2      0      1     3    -2

In each iteration we divide by to find the quotient .
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:

This is repeated until we hit zero, which already happened at step 4.


Now we've found in step 3 that:

Multiply the entire equation by 2 to find:

which is the solution you requested.

Let's try this again:

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

We start with:



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



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:


In your original equation, you had x=3k+2.
So your solution is