Question

solve
3x ≡ 1 (mod 5)
4x ≡ 6 (mod 14)
5x ≡ 11 (mod 3)

Answer 1

I found x = 82 or x = 187

but what are ALL solutions?

Answer 2

did you use chinese remainder thm?

Answer 3

I think I did.

Answer 4

It only said Theorem but didn't explicitly said "Chinese Remainder Theorem" Let me post the link

Answer 5

chinese remainder thm gives you the solution
\[x\equiv 82\pmod{5*7*3}\]

Answer 6

You can divide eq1 by 3 and eq3 by 5, since they are moduli over primes.

Answer 7

here: https://books.google.com/books?id=eVwvvwZeBf4C&lpg=PA58&pg=PA68#v=onepage&q&f=false

Answer 8

Oh so I was supposed to divide the second congruence by 2?

Answer 9

that is chinese remainder theorem

Answer 10

it doesn't affect the final solution
dividing by 2 simplifies the work, thats all

Answer 11

I don't think you can divide eq2. Actually division is the wrong word.

Answer 12

what about the solution 187 (mod 5*14*3) ??

Answer 13

in mod 5*14*3, you should get "two" incongruent solutions

Answer 14

```
I found x = 82 or x = 187

but what are ALL solutions?
```

Yes, those are all the incongruent solutions in mod 5*14*3

Answer 15

oh so in a sense {82 + 5*7*3k, k integer} is equal to the set {82 + 5*14*3k} U {187 + 5*14*3k} ??

Answer 16

Lets take equation 1 as an example

3x ≡ 1 (mod 5)
says that if you divide 3x by 5 you get a remainder of one. We want to know
x (mod 5) is. Since 5 is a prime number we can determine the remainder of x:5 uniquely.

In particular x ≡ 2 (mod 5).

Similarly for equation three

5x ≡ 11 (mod 3) -> 5x ≡ 2 (mod 3) -> x ≡ 1 (mod 3)

Answer 17

Since 14 is not a prime number 4x ≡ 6 (mod 14) doesn't have a unique solution for x (mod 14)

Answer 18

I see. Thank you both :')

Answer 19

So the next step is to find all x (mod 14) that solve 4x ≡ 6 (mod 14).

Answer 20

```
oh so in a sense {82 + 5*7*3k, k integer} is equal to
the set {82 + 5*14*3k} U {187 + 5*14*3k} ??
```

Precisely @sourwing !

Answer 21

@ganeshie8 thank you!!