system of congruences

Images are sometimes not shown due to bandwidth/network limitations. Refreshing the page usually helps.

You are currently reading a thread in /sci/ - Science & Math

You are currently reading a thread in /sci/ - Science & Math

Thread images: 1

anon

system of congruences 2016-01-09 20:45:29 Post No. 7772137

[Report] Image search: [iqdb] [SauceNao] [Google]

system of congruences 2016-01-09 20:45:29 Post No. 7772137

[Report] Image search: [iqdb] [SauceNao] [Google]

How do i solve system of congruences if gcd of mods is not equal to 1(which is ussualy done with chinese remainder theorem)?

For example this system

x(congruent) to 21 by mod 36

x(congruent) to 5 by mod 8

I ussualy solve this with chinese theorem of remainder but in this case gcd is not 1 equal to 1..

Anyone has any tips on how to solve this ?

>>

make it so that the gcd is 1

>>

How do i make this system so that gcd is 1 ? I dont get it,i dont think you can do it.

>>

>>7772137

For the system you provided, try the following:

The first equation says that [math]x[/math] is of the form [math]36t + 21[/math]. The second equation says that [math]x[/math] is of the form [math]8r + 5[/math].

So we have [math]36t+21 = 8r + 5[/math]

[math]4*(9t-2r) = -16[/math]

[math]2r - 9t = 4[/math]

There, now we solve for integers [math]r[/math] and [math]t[/math] that satisfy this equation (which I would think you should have learned how to do) and plug back into the original equation to find [math]x[/math].

This procedure can be generalized to more than 2 equations.

>>

>>7772155

Yes you can. Make it like this:

x(congruent) to 3 by mod 9

x(congruent) to 5 by mod 8

>>

solution is 21+k*72 I guess

>>

>>7772199

That method does not work in general.

For example, consider

[math]x \equiv 1[/math] (mod 8)

[math] x \equiv 3 [/math] (mod 6)

If we did your method, we'd "reduce" the problem to

[math]x \equiv 1[/math] (mod 2)

[math] x \equiv 3 [/math] (mod 6)

But there is clearly a solution of the latter system that is not a solution of the original system.

>>

I managed to get r=-16 and t=-4 now my question is where do i put it again?

>>

>>7772217

I assume you meant to reply to >>7772196. Learn how to use 4chan.

We had that [math]x = 36t + 21[/math], so plug [math]t[/math] into that to find a value of [math]x[/math].

If you find all [math]t[/math] that satisfy [math]2r-9t=4[/math], you can in this way find all [math]x[/math] that satisfy the original system.

>>

>>7772222

Then give an algoritm. You can't just "find" stuff.

I don't get why you don't recommend the standard way (in every discrete math book) of solving this to the OP.

>>

>>7772214

>But there is clearly a solution of the latter system that is not a solution of the original system.

Which one?

>>

>>7772232

3, silly.

>>

>>7772222

Uhm this part is pretty confusing to me ,from here im geting that x =-123 now if i add 36 on this until i get into >0 <=21 range i get 21 which is correct answer,now my question is when i get x (when i put t in it) why do i have to search for r ? Isnt t only necessary here?

>>

>>7772238

Yes.

>>

>>

>>7772241

I hadn't realized that this was homework, OP. This board is not for homework problems. I thought you had a general inquiry. Do not ask homework problems in the future.

>>

Let me get this right.

The key here is to express first equation and 2nd as a value like for example 36t+21=8r+5

no i solve equation and get t and i just put it in x=36t+21 for example and if i get x to be negative i just increase it by 36 in this case untill i get to >0 <=36(mod) value which will be the answer?Does this work for all cases or?This seems pretty easy ,i guess this will not work for every case...

>>

>>7772252

Im not OP...

OP has a name (anon)

>>

>>7772252

How did you determine this was homework?This has nothing to do with homework,i just want to learn these stuff as i need it for things not related to school.

>>

>>7772214

Here it should reduce to

x(congruent) to 1 by mod 8

x(congruent) to 0 by mod 3

Anyway, I used to solved this years ago with this method, bit rusty now. I'll think some more and will post general way of solving later.

>>

Ok OP, here's how I generally solve system of congruences when the moduli aren't relativiely prime, I'll use the problem in your OP as example:

Start with:

[math]x \equiv 21 (\text{mod} 36)[/math]

[math]x \equiv 5 (\text{mod} 8)[/math]

Step 1) make prime decomposition of all moduli with shared divisors:

[math]x \equiv 21 (\text{mod} 2^{2}3^{2})[/math]

[math]x \equiv 5 (\text{mod} 2^{3})[/math]

Step 2) replace the congruences by making a congruence for each factor:

[math]x \equiv 21 (\text{mod} 2^{2})[/math]

[math]x \equiv 21 (\text{mod} 3^{2})[/math]

[math]x \equiv 5 (\text{mod} 2^{3})[/math]

Becomes:

[math]x \equiv 1 (\text{mod} 2^{2})[/math]

[math]x \equiv 3 (\text{mod} 3^{2})[/math]

[math]x \equiv 5 (\text{mod} 2^{3})[/math]

Step 3) for all the congruences in which the moduli share factors, keep the one with highest power. BUT you need to check if the congruence you keep, also satisfies the ones you will delete (if this isn't the case, there's no solution):

[math]x \equiv 1 (\text{mod} 2^{2})[/math] -> delete (since 2^2 is smaller then 2^3) if check turn out OK

[math]x \equiv 3 (\text{mod} 3^{2})[/math] -> keep (theres no other congruence with factor 3 in prime decomposition)

[math]x \equiv 5 (\text{mod} 2^{3})[/math] -> keep

Check:

[math]x \equiv 5 (\text{mod} 2^{2})=1[/math] OK

Step 4) you can now use chinese remainder theorem to solve the system

Thread images: 1

Thread DB ID: 417771

All trademarks and copyrights on this page are owned by their respective parties. Images uploaded are the responsibility of the Poster. Comments are owned by the Poster.

This is a 4chan archive - all of the shown content originated from that site. This means that 4Archive shows their content, archived. If you need information for a Poster - contact them.

If a post contains personal/copyrighted/illegal content, then use the post's