system of congruences

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.

>>7772235
ok

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