solve-the-system-of-congruence-x-1-mod-5-x-2-mod-7-x-3-mod-9-x-4-mod-11-

Question Number 66832 by Rio Michael last updated on 20/Aug/19

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

\begin{matrix} x \equiv 1 (m o d 5) \\ x \equiv 2 (m o d 7) \\ x \equiv 3 (m o d 9) \\ x \equiv 4 (m o d 11) \end{matrix}}

Answered by mr W last updated on 26/Aug/19

x = 5 h + 1 \dots (1)

x = 7 i + 2 \dots (2)

x = 9 j + 3 \dots (3)

x = 11 k + 4 \dots (4)

x = 11 k + 4 = (11 k + 1) + 3 \overset{!}{=} 9 j + 3

\Rightarrow 11 k + 1 = 9 j

\Rightarrow 9 j - 11 k = 1

\Rightarrow j = 11 m + 5^{* *)}

\Rightarrow k = 9 m + 4

x = 9 (11 m + 5) + 3 = (99 m + 46) + 2 \overset{!}{=} 7 i + 2

\Rightarrow 99 m + 46 = 7 i

\Rightarrow 7 i - 99 m = 46

\Rightarrow i = 99 l + 49^{* *)}

\Rightarrow m = 7 l + 3

x = 7 (99 l + 49) + 2 = (693 l + 344) + 1 \overset{!}{=} 5 h + 1

\Rightarrow 693 l + 344 = 5 h

\Rightarrow 5 h - 693 l = 344

\Rightarrow h = 693 n + 346^{* *)}

\Rightarrow l = 5 n + 2

x = 5 (693 n + 346) + 1 = 3465 n + 1731

\Rightarrow g e n e r a l s o l u t i o n i s

x = 3465 n + 1731 w i t h n = 0, 1, 2, 3, \dots .

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

a r e t h e r e a n y e a s i e r a n d m o r e d i r e c t

w a y s t o s o l v e ?

t o u n d e r s t a n d^{* *)} i n m y s o l u t i o n

s e e a l s o m y e x p l a n a t i o n i n Q 19198 .

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

o k a y s i r l^{'} l l c h e c k b u t t h a n k s f o r t h i s

Commented by Rasheed.Sindhi last updated on 22/Aug/19

S i r m r W, I t h i n k i t c a n b e s o l v e d

b y^{'} C h i n e s e r e m a i n d e r {t h e o r m}^{'}, b u t

u n f o r t i n u a t e l y a t t h e m o m e n t I^{'} v e f o r g o t t e n i t .

Commented by Prithwish sen last updated on 22/Aug/19

By chinese remainder theorem

∵ 5, 7, 9, 11 are pairwise prime

let m = 5.7.9.11 = 3465

∴ M_{1} = \frac{m}{5} = 693, M_{2} = \frac{m}{7} = 495, M_{3} = \frac{m}{9} = 385

M_{4} = \frac{m}{11} = 315

\gcd (693, 5) = 1 \Rightarrow 693 u + 5 v = 1 \Rightarrow u = 2 v = - 277

∴ 693 x \equiv 1 (\mod 5) has unique soln . x \equiv 2 (\mod 5)

\gcd (495, 7) = 1 \Rightarrow 495 u + 7 v = 1 \Rightarrow u = 3 v = - 212

∴ 495 x \equiv 1 (\mod 7) has unique soln . x \equiv 3 (\mod 7)

\gcd (385, 9) = 1 \Rightarrow 385 u + 9 v = 1 \Rightarrow u = 4 v = - 171

∴ 385 x \equiv 1 (\mod 9) has unique soln . x \equiv 4 (\mod 9)

\gcd (315, 11) = 1 \Rightarrow 315 u + 11 v = 1 \Rightarrow u = - 3 v = 86

∴ 315 x \equiv 1 (\mod 11) has unique soln . x \equiv - 3 (\mod 11)

i . e x \equiv 8 (\mod 11)

∴ x_{0} = 1 . (693.2) + 2 . (495.3) + 3 . (385.4) + 4 . (315.8)

= 19056

∴ T he soln . is x \equiv 19056 (\mod 3465)

i . e x \equiv 1731 (\mod 3465)

Commented by mr W last updated on 22/Aug/19

t h a n k y o u f o r y o u r e f f o r t s i r!

Commented by Prithwish sen last updated on 23/Aug/19

you are welcome sir .

Commented by Rio Michael last updated on 25/Aug/19

t h a n k s a l o t y o u a l l, i r e a l l y w a n t t o l e a r n t h i s p a r t o f m a t h e m a t i c s, h o w d o i g o

a b o u t i t ? p l e a s e h e l p m e .

Commented by mr W last updated on 25/Aug/19

a t f i r s t p l e a s e t r y n o t t o w r i t e

e n d l e s s l o n g r o w s i n y o u r p o s t s s i r .

u s u a l l y i i g n o r e p o s t s i f i m u s t

s c r o l l h o r i z o n t a l l y w h e n i r e a d

t h e m .

b a c k t o y o u r q u e s t i o n, i f y o u w a n t

t o l e a r n “ c h i n e s e {r e m a i n d e r}^{″} m e t h o d,

i c a n n o t h e l p y o u . p l e a s e r e f e r t o

W i k i p e d i a f o r m o r e d e t a i l s . i f

y o u w a n t t o l e a r n a b o u t m y m e t h o d,

t r y t o u n d e r s t a n d h o w t o s o l v e

a x + b y = c a s i e x p l a i n e d i n q u e s t i o n

N o 19198 .

Commented by Rio Michael last updated on 29/Aug/19

y e s i k n o w h o w t o s o l v e l i n e a r d i o p h a n t i n e e q u a t i o n s

Commented by Rio Michael last updated on 29/Aug/19

i^{'} l l v i s i t w i k i p e d i a

Answered by Rasheed.Sindhi last updated on 22/Aug/19

A n A rithmetic W ay

\begin{matrix} x \equiv 1 (m o d 5) \dots (i) \\ x \equiv 2 (m o d 7) \dots . (i i) \\ x \equiv 3 (m o d 9) \dots . . (i i i) \\ x \equiv 4 (m o d 11) \dots (i v) \end{matrix}}

(i) \Rightarrow x = 6, 11, 16, 21, \dots

E a c h n u m b e r c a n b e o b t a i n e d b y

a d d i n g 5 i n p r e v i o u s .

W e c a n s e e t h a t 16 i s a l s o s o l u t i o n o f

(i i) (\dots . m o d 7)

A n y o t h e r s u c h n u m b e r (w h i c h i s c o m m o n

s o l u t i o n t o (i) & (i i)) w i l l b e 35 (l c m o f

5 & 7) g r e a t e r t h a n 16 \dots

16, 51, 86, 121, 156, \dots

156 i s a l s o s o l u t i o n o f (i i i) (\dots m o d 9)

S o n e x t s u c h s o l u t i o n i s 315 (l c m (5, 7, 9))

g r e a t e r t h a n 156

156, 471, 786, 1101, 1416, 1731

1731 i s a l s o s o l u t i o n o f (i v) (\dots . m o d 11)

N e x t s u c h n u m b e r i s g r e a t e r b y a n y

m u l t i p l e o f l c m (5, 7, 9, 11) = 3465 .

1731, 5196, 8661, \dots

Commented by Rasheed.Sindhi last updated on 22/Aug/19

S i r m r W

I h a d s o l v e d t h e a b o v e p r o b l e m i n

t h a t w a y s o m e t i m e a g o (A t t h a t t i m e I {d i d n}^{'} t k n o w

c h i n e s e r e m a i n d e r t h e o r m .) T h e a b o v e

m e t h o d {d i d n}^{'} t u s e a l g e b r a . . a n d {i t}^{'} s

m y o w n m e t h o d .

Commented by mr W last updated on 22/Aug/19

S i r R a s h e e d,

t h a n k y o u v e r y m u c h f o r t h i s n e w

w a y! i a p p r e c i a t e i t!

Commented by Rasheed.Sindhi last updated on 22/Aug/19

T han k s A L ot S ir!