Question

\(\large \begin{align} \color{black}{
x\equiv 3(mod~5)\hspace{.33em}\\~\\
x\equiv 5(mod~7)\hspace{.33em}\\~\\
x\equiv 7(mod~11)\hspace{.33em}\\~\\
}\end{align}\)
find \(x\).

Answer 1

\(\large \begin{align} \color{black}{gcd(5,7)=\gcd(5,11)=\gcd(11,7)=1\hspace{.33em}\\~\\}\end{align}\)

Answer 2

I don't know if this is technically how you're expected to solve it since I know there's like a chinese remainder theorem or something for this but I couldn't remember it, so I am going to try to figure it out like this: \[\Large x=5a+3 \\ \Large x=7b+5 \\ \Large x=11c+7\] From here you can equate all of the x's in 3 different ways like this: \[\Large 5a+3=7b+5 \\ \Large 5a+3=11c+7 \\ \Large 7b+5=11c+7\] Then rearrange them like this: \[\Large 5a-7b=2 \\ \Large 5a-11c=4 \\ \Large 7b-11c=2\] Plug it into a 3x3 matrix like this: \[\Large \left[\begin{matrix}5 & -7 & 0 \\ 5 & 0&-11 \\ 0 & 7 & -11\end{matrix}\right] \left(\begin{matrix}a \\ b \\ c\end{matrix}\right) = \left(\begin{matrix}2 \\ 4 \\ 2\end{matrix}\right)\] Multiply by the inverse... And wait, there is no inverse since the determinant is 0 if you look down the antidiagonal... :,( Nevermind good luck, I'll keep tring.

Answer 3

yes the chinese remainder

Answer 4

but i there must be an easy way without matrix

Answer 5

You want the remainders to be 3,5,7 when you divide by 5,7,11 respectively. One way to work it is by trial and error :
\(x \equiv 3\pmod 5\) :
3, 8, 13, 18, ...

\(x \equiv 5\pmod 7\) :
5, 12, 19, 26, 33, ...

\(x \equiv 7\pmod {11}\) :
7, 18, 29, 40,...

keep going till you find a common term among all 3 sequences

Answer 6

chinese remainder thm gives you answer in one line, but lets see another easy way to work this system (similar to matrix method but w/o using matrices directly)

Answer 7

Look at first congruence : \(x \equiv 3\pmod 5\)

that means \(x = 3 + 5k\) where \(k\) is an integer

substitute this in second congruence

Answer 8

\(x \equiv 5 \pmod 7\)
\(3+5k \equiv 5 \pmod 7\)

solve \(k\)

Answer 9

we want an integer solution

Answer 10

oh wait \(k=-1\)

Answer 11

\(x \equiv 5 \pmod 7\)
\(3+5k \equiv 5 \pmod 7\)

subtracting 3 both sides you get
\(5k \equiv 2 \pmod 7\)

now notice that k = 6 satisfies this congruence
so the solution is \(k \equiv 6 \pmod 7\)
which is same as \(k = 7m+6\) where \(m\) is any integer

Answer 12

yes! k = -1 is same as 6 in mod 7

Answer 13

So far we have this :
x = 3 + 5k
k = 7m + 6

combining you get x = 33 + 5*7m
plug this in third congruence and solve m

Answer 14

\(x\equiv 7 \pmod {11}\)
\(33 + 5\cdot 7 m \equiv 7 \pmod {11}\)

solve \(m\)

Answer 15

\(\large \begin{align} \color{black}{

33+35m=7+11n \hspace{.33em}\\~\\
}\end{align}\)

Answer 16

it will be easy to work it using mod properties

Answer 17

is the last second paragraph above

did u mean

\(\large 11\) divides 33 so the remainder would be 0 :

Answer 18

Yes ! sorry it was a typo let me fix it :)

Answer 19

\(x\equiv 7 \pmod {11}\)
\(33 + 5\cdot 7 m \equiv 7 \pmod {11}\)

\(\color{Red}{11}\) divides \(33\) so the remainder would be \(0\) :
\(0+ 5\cdot 7 m \equiv 7 \pmod {11}\)
\(35 m \equiv 7 \pmod {11}\)

Answer 20

35 leaves a remainder of 2 when divide by 11, so

\(35 m \equiv 7 \pmod {11}\)
simplifies to
\(2 m \equiv 7 \pmod {11}\)

see what value of \(m\) satisfies this congruence

Answer 21

m should be integer ?

Answer 22

in number theory we only deal with integers

Answer 23

unless otherwise explicitly stated all variables are assumed to be integers :)

Answer 24

Notice when you're working in mod11, you just have 11 values to test : {0,1,2,..,10}

Answer 25

oh \(m=9\) ?

Answer 26

Right!

Answer 27

since you're in mod11, the solution is m = 9 + 11n
where n is ANY/ALL integers

Answer 28

plug that in previous equation for x and you're done!

Answer 29

```
So far we have this :
x = 3 + 5k
k = 7m + 6

combining you get x = 33 + 5*7m
plug this in third congruence and solve m
```

Answer 30

plugin m = 9 + 11n above ^

Answer 31

x = 33 + 5*7m

x = 33 + 5*7(9+11n)

simplifying you get
x = 348 + 5*7*11n

thats the final unique incongruent solution in mod 5*7*11

Answer 32

x=348

Answer 33

notice 348 is the first positive number that satisfies all the 3 given congruences

Answer 34

thank u both

Answer 35

chinese remainder thm is just a compressed version of our previous method :
\[x \equiv 3\pmod 5\\x\equiv 5\pmod 7\\x\equiv 7 \pmod {11}\]
As promised chinese remainder thm gives you answer in one line
\[x \equiv 3 (7\cdot 11)[ (7\cdot 11 )^{-1}\pmod 5] \\+\\5 (5\cdot 11)[ (5\cdot 11)^{-1}\pmod 7] \\+ \\7 (5\cdot 7)[ (5\cdot 7)^{-1}\pmod {11}]\\ \pmod{5\cdot 7 \cdot 11} \]

you shoudl get 348 after working it :P

Answer 36

but i dont get how will u find the mod of inverse

\(\large \begin{align} \color{black}{

(7\cdot 11)^{-1} (mod~5)\hspace{.33em}\\~\\
}\end{align}\)

Answer 37

that notation refers to "multiplicative inverse"

Answer 38

finding \((7\cdot 11)^{-1}\) is same as solving the congruence :
\[7\cdot 11 x \equiv 1 \pmod 5\]

Answer 39

its basically asking you for the value of x that produces 1 when multiplied by 7.11 in mod 5

Answer 40

consider a simpler example : \(2^{-1} \pmod {5}\)

Answer 41

To find \(2^{-1} \pmod {5}\), we solve
\[ 2x\equiv 1 \pmod {5}\]

Answer 42

x=3 ?

Answer 43

Yes! since x = 3 satisfues above congruence, the multiplciative inverse of 2 in mod 5 is 3 :
\[2^{-1} \pmod{5} = 3\]

Answer 44

maybe lets work the previous chinese monster expression to get more practice

Answer 45

\[x \equiv 3 (7\cdot 11)[ \color{Red}{(7\cdot 11 )^{-1}\pmod 5}] \\+\\5 (5\cdot 11)[ (5\cdot 11)^{-1}\pmod 7] \\+ \\7 (5\cdot 7)[ (5\cdot 7)^{-1}\pmod {11}]\\ \pmod{5\cdot 7 \cdot 11}\]

work that red part first

Answer 46

finding \((7\cdot 11)^{-1}\) is same as solving the congruence :
\[7 \cdot 11x \equiv 1\pmod{5}\]

find a \(x\) that satisfies above congruence

Answer 47

\(x=231\)

Answer 48

you're in mod5 so you can play with smaller numbers : 0,1,2,3,4

Answer 49

i mean that red part value is 231

Answer 50

\[7 \cdot 11x \equiv 1\pmod{5}\]

notice \(7\equiv 2\) and \(11\equiv 1\) in mod 5, so :
\[2 \cdot 1x \equiv 1\pmod{5}\]

Answer 51

x=3

Answer 52

yes so the red part evaluates to 3

Answer 53

ohh

Answer 54

\[\color{Red}{(7\cdot 11 )^{-1}\pmod 5} = 3\]

Answer 55

similarly work other two inverses also :
\[x \equiv 3 (7\cdot 11)[ \color{Red}{(7\cdot 11 )^{-1}\pmod 5}] \\+\\5 (5\cdot 11)[ \color{Red}{(5\cdot 11)^{-1}\pmod 7}] \\+ \\7 (5\cdot 7)[\color{Red}{ (5\cdot 7)^{-1}\pmod {11}}]\\ \pmod{5\cdot 7 \cdot 11}\]

Answer 56

once you have the inverse you just plug them in and simplify
you will end up with 348

Answer 57

next 2nd red part =6

Answer 58

Right!

Answer 59

next 4

Answer 60

i think i got 6, one sec..

Answer 61

yes 6 sry

Answer 62

yes! next plug and chug

Answer 63

\[x \equiv 3 (7\cdot 11)[ \color{Red}{3}] \\+\\5 (5\cdot 11)[ \color{Red}{6}] \\+ \\7 (5\cdot 7)[\color{Red}{ 6}]\\ \pmod{5\cdot 7 \cdot 11}\]

Answer 64

that is like 3813

Answer 65

Correct! 3813 in mod 5*7*11

Answer 66

reduce it

Answer 67

lol there must a short way

Answer 68

short way for what

Answer 69

for evaluating
\(x \equiv 3 (7\cdot 11)[ \color{Red}{3}] \\+\\5 (5\cdot 11)[ \color{Red}{6}] \\+ \\7 (5\cdot 7)[\color{Red}{ 6}]\\ \pmod{5\cdot 7 \cdot 11}\)

Answer 70

ofcourse you can use mod properties for each sum

Answer 71

\[3(7*11)(3) = 693 \equiv -77 \pmod {5*7*11}\]

but its not so much important how you work it.. your goal is just to get a positive integer less than 5*7*11

Answer 72

\[x \equiv 3 (7\cdot 11)[ \color{Red}{3}] \\+\\5 (5\cdot 11)[ \color{Red}{6}] \\+ \\7 (5\cdot 7)[\color{Red}{ 6}]\\ \pmod{5\cdot 7 \cdot 11}\]

simplifies to

\[x \equiv 3813 \pmod{5\cdot 7 \cdot 11}\]

Answer 73

which further reduces to
\[x \equiv 348\pmod{5\cdot 7 \cdot 11}\]

because 3813 = 9(5*7*11) + 348

Answer 74

yes i got that by my weird calculations

Answer 75

we're good then :) calculations can get more weird than this. Try below classic problems involving chinese remainder thm when free

Answer 76

i got this lol
\(\large \begin{align} \color{black}{

\dfrac{4}{5}+\dfrac{2}{7}+\dfrac{9}{11}\hspace{.33em}\\~\\
\dfrac{733}{385}\hspace{.33em}\\~\\
\dfrac{348+385}{385}\hspace{.33em}\\~\\
348\hspace{.33em}\\~\\
}\end{align}\)

Answer 77

oh thnks for the problem exersize

Answer 78

looks interesting xD i don't get how you worked it though, could u elaborate ?

Answer 79

yes wait

Answer 80

\(\large \begin{align} \color{black}{

\dfrac{3\times 7\times 11\times 3+5\times 5\times 11\times 6+7\times 5\times 7\times 6}{5\times 7\times11}
\hspace{.33em}\\~\\
\implies \dfrac{3\times 7\times 11\times 3}{{5\times 7\times11}}+\dfrac{5\times 5\times 11\times 6}{{5\times 7\times11}}+\dfrac{7\times 5\times 7\times 6}{5\times 7\times11}
\hspace{.33em}\\~\\
\implies \dfrac{9}{{5}}+\dfrac{30}{{7}}+\dfrac{42}{11}
\hspace{.33em}\\~\\
\implies \dfrac{4}{{5}}+\dfrac{2}{{7}}+\dfrac{9}{11}
\hspace{.33em}\\~\\









}\end{align}\)

Answer 81

that continues to the previous one

Answer 82

Very interesting xD but il need to think about it more as i suspect this way of simplification can get us into problems sometimes hmm

Answer 83

i dont think it is testified by me

\(\large \begin{align} \color{black}{

\implies \dfrac{4}{{5}}+\dfrac{2}{{7}}+\dfrac{9}{11}
\hspace{.33em}\\~\\
\implies \dfrac{-1}{{5}}+\dfrac{2}{{7}}+\dfrac{-2}{11}
\hspace{.33em}\\~\\
\implies \dfrac{-37}{385}
\hspace{.33em}\\~\\
\implies \dfrac{385-37}{385}
\hspace{.33em}\\~\\
\implies \dfrac{348}{385}
\hspace{.33em}\\~\\
\implies 348
}\end{align}\)

see it is also working with negatives

Answer 84

yeah i dont see anything wrong, looks cool :D

Answer 85

simply use chines remainder theorem