# Modular algorithm question

1. Feb 28, 2008

### booney1983

how can i solve this problem?

[ x1= a (mod 100) , a= 20 (mod 37) ]

[ x2= b (mod 100) , b= 15 (mod 37) ]

[ x3= c (mod 100) , c= 18 (mod 37) ]

must be ; x2= a.k + y (mod100)

and

x3= b.k + y (mod100)

i need find b and c.. thank you best regards..

2. Feb 28, 2008

### HallsofIvy

Staff Emeritus
Looks to me like "Chinese remainder theorem". In any case, it is certainly not "Calculus and Analysis. I am moving this to the number theory forum.

3. Feb 29, 2008

### CRGreathouse

Are these the same y and k, the same y, but some arbitrary k, or what?

4. Mar 8, 2008

### booney1983

yes same y and k

5. Mar 8, 2008

### robert Ihnot

booney1983: yes same y and k

That's not especially helpful since no effort to define them was given. As for y I see that you use it in the two final equations. So I am wondering if it could not simply be dropped and is meaningless?

What is b.k? I have guessed it means b times k. The symbol "*" is sometimes used for multiplication. Maybe some countries think differently.

Last edited: Mar 9, 2008
6. Mar 9, 2008

### CRGreathouse

Here's how I'm interpreting the question:

Find b and c such that the following equations are satisfied in terms of the other variables.
1. $$x_1\equiv a\pmod{100}$$
2. $$a\equiv20\pmod{37}$$
3. $$x_2\equiv b\pmod{100}$$
4. $$b\equiv15\pmod{37}$$
5. $$x_3\equiv c\pmod{100}$$
6. $$c\equiv18\pmod{37}$$
7. $$x_2\equiv a\cdot k+y\pmod{100}$$
8. $$x_3\equiv b\cdot k+y\pmod{100}$$

It's trivial to determine the values of b and c mod 100: $b\equiv ak+y$, $c\equiv bk+y$. The CRT could then be used to determine b and c mod 3700.

Last edited: Mar 9, 2008
7. Mar 10, 2008

### robert Ihnot

One simple solution is X1=X2=X3=18 Mod 100. a=2018, b=718, c=18. k=1, y=0. which renders the last two equations redundant, while 5 and 6 are taken care of since X3=c.

Last edited: Mar 10, 2008