solve-the-system-of-linear-congruences-x-2-mod-3-x-4-mod-5-x-7-mod-9-x-11-mod-13-using-the-Brute-force-method-

Question Number 71838 by Rio Michael last updated on 20/Oct/19

s o l v e t h e s y s t e m o f l i n e a r c o n g r u e n c e s

x \equiv 2 (m o d 3)

x \equiv 4 (m o d 5)

x \equiv 7 (m o d 9)

x \equiv 11 (m o d 13)

u s i n g t h e B r u t e f o r c e m e t h o d

Commented by mind is power last updated on 20/Oct/19

\Leftrightarrow

x \equiv 4 (5)

x \equiv 7 (9)

x \equiv 11 (13)

x \equiv 4 (5), x \equiv 7 (9) \Leftrightarrow x \equiv 34 (45)

our system \Leftrightarrow {\begin{cases} x \equiv 34 (45) \\ x \equiv 11 (13) \end{cases} \Leftrightarrow x \equiv 349 (585)

solution x \equiv 349 (585)

Commented by mr W last updated on 21/Oct/19

x \equiv 2 (m o d 3) a n d

x \equiv 7 (m o d 9) a r e c o n t r a d i c t o r y!

x = 9 k + 7 = 3 (3 k + 2) + 1 = 3 m + 1 \neq 3 m + 2

Commented by mind is power last updated on 21/Oct/19

yeah

Answered by mr W last updated on 21/Oct/19

x = 13 a + 11 = 9 b + 7

9 b - 13 a = 4

\Rightarrow b = 13 c - 1, a = 9 c + 1

x = 9 (13 c - 1) + 7 = 117 c - 2 = 5 d + 4

117 c - 5 d = 6

\Rightarrow d = 117 e + 69, c = 5 e + 3

x = 5 (117 e + 69) + 4 = 585 e + 349 \overset{!}{=} 3 f + 2

3 (f - 195 e) = 347 \Rightarrow i m p o s s i b l e

x \equiv 2 (m o d 3) i s c o n t r a d i c t i o n!

s o l u t i o n i s x = 585 n + 349

Commented by Rio Michael last updated on 21/Oct/19

t h a n k y o u s o m u c h s i r