what-is-the-first-three-smallest-positive-integer-that-leaves-a-reminder-of-1-when-divided-by-3-and-5-qnd-7-

Question Number 89668 by Mr.Panoply last updated on 18/Apr/20

w h a t i s t h e f i r s t t h r e e s m a l l e s t p o s i t i v e

i n t e g e r t h a t l e a v e s a r e m i n d e r o f 1 . w h e n

d i v i d e d b y 3 a n d 5 q n d 7 ?

Commented by mr W last updated on 18/Apr/20

l c m (3, 5, 7) = 3 \times 5 \times 7 = 105

t h e n u m b e r i s 105 n + 1

Answered by Joel578 last updated on 18/Apr/20

x \equiv 1 (\mod 3)

x \equiv 1 (\mod 5)

x \equiv 1 (\mod 7)

a_{1} = a_{2} = a_{3} = 1

m_{1} = 3, m_{2} = 5, m_{3} = 7

\Rightarrow m = m_{1} m_{2} m_{3} = 105

\Rightarrow M_{1} = \frac{m}{m_{1}} = 35, M_{2} = = \frac{m}{m_{2}} = 21, M_{3} = \frac{m}{m_{3}} = 15

Now find y_{k} such that M_{k} y_{k} \equiv 1 (\mod m_{k})

\Rightarrow y_{1} = 2, y_{2} = 1, y_{3} = 1

y = a_{1} M_{1} y_{1} + a_{2} M_{2} y_{2} + a_{3} M_{3} y_{3}

= 70 + 21 + 15 = 106

x = y \mod m = 106 \mod 105 = 1

In general, x = 105 k + 1, k = 0, 1, 2, \dots

Commented by Mr.Panoply last updated on 19/Apr/20

T h a n k y o u \dots s o m u c h