Question

Find the smallest positive integer x such that x≡0 (mod 16) and x≡2 (mod 25).

Answer 1

They are in 1 question. I'll rephrase it.

Answer 2

for this i would grind it till you find it

Answer 3

ooh, booleon AND sorry

Answer 4

I want to use Chinese Remainder Theorem, but I don't know how to use it.

Answer 5

16, 32, 48, ... one has to be 2 mod 25

Answer 6

I want to use Chinese Remainder Theorem, but I don't know how to use it.

Answer 7

I can look at my book and try to work it out, but it'll take a little while. We never covered chiense remainder theorem in discrete class since we ran outta time

Answer 8

@satellite73 ?

Answer 9

there is an actual algorithm for finding this
you can start with \(x=16t\) then \[16t\equiv 2 (25)\] but at this step it is probably easiest to keep adding 16 until you get it

Answer 10

I want to explicitly use the Chinese Remainder Theorem.

Answer 11

ok, my book says to construct solution of
x≡a_1(mod m_1)
x≡a_2(mod m_2)
x≡a_3(mod m_3)
by letting x=a_1M_1y_1+a_2M_2y_2+...+a_n*M_n*y_n

where M_n equals the product of all moduli except m_n and M_ky_k≡1(mod m_k)

Answer 12

what is y?

Answer 13

take a look at this example
your is going to be easier because you are only solving 2
http://www.youtube.com/watch?v=3PkxN_r9up8

Answer 14

I'm not providing the reasoning of what the solution is simultaenous, but I'll just try to work out the problem
x≡0 (mod 16)
x≡2(mod 25)
since the two are pairwise relatively prime, we can continue
M_1=25
M_2=16
a_1=0
a_2=2

we know 25y_1≡1(mod 16)
and we know that 16y_2≡1(mod 25)

Answer 15

in other words y_1=9 and y_2=11

Answer 16

thus the solution is x=a_1M_1y_1+a_2M_2y_2, or x=0+2*16*11=352

Answer 17

@kc_kennylau , does this make sense?

Answer 18

Thanks :)

Answer 19

but how do you know that y_2=11?

Answer 20

M_ky_k≡1(mod m_k)

Answer 21

brute force? :/

Answer 22

\(\large M_kY_k≡1(mod m_k)\)

Answer 23

so yes, I solved 16y_2≡1(mod 25) by brute force, though I am sure there is an easier way to do it.

Answer 24

but there is no easier way to do it :P

Answer 25

anyway thanks :D

Answer 26

np - looked around and I think the solution to a linear congruence is beyond the scope of my DM course (and perhaps what you are learning)