Menu Close

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

Tinku Tara 0 Comments
Pin




Question Number 89668 by Mr.Panoply last updated on 18/Apr/20
what is the first three smallest positive integer that leaves a reminder of 1. when divided by 3 and 5 qnd 7?
$${what}\:{is}\:{the}\:{first}\:{three}\:{smallest}\:{positive}\: \\ $$$${integer}\:{that}\:{leaves}\:{a}\:{reminder}\:{of}\:\mathrm{1}.\:{when} \\ $$$${divided}\:{by}\:\mathrm{3}\:{and}\:\mathrm{5}\:{qnd}\:\mathrm{7}? \\ $$
Commented by mr W last updated on 18/Apr/20
lcm(3,5,7)=3×5×7=105 the number is 105n+1
$${lcm}\left(\mathrm{3},\mathrm{5},\mathrm{7}\right)=\mathrm{3}×\mathrm{5}×\mathrm{7}=\mathrm{105} \\ $$$${the}\:{number}\:{is}\:\mathrm{105}{n}+\mathrm{1} \\ $$
Answered by Joel578 last updated on 18/Apr/20
x ≡ 1 (mod 3) x ≡ 1 (mod 5) x ≡ 1 (mod 7) a_1 = a_2 = a_3 = 1 m_1 = 3, m_2 = 5, m_3 = 7 ⇒ m = m_1 m_2 m_3 = 105 ⇒ M_1 = (m/m_1 ) = 35, M_2 = = (m/m_2 ) = 21, M_3 = (m/m_3 ) = 15 Now find y_k such that M_k y_k ≡ 1 (mod m_k ) ⇒ 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 = 105k + 1, k = 0,1,2,...
$${x}\:\equiv\:\mathrm{1}\:\left(\mathrm{mod}\:\mathrm{3}\right) \\ $$$${x}\:\equiv\:\mathrm{1}\:\left(\mathrm{mod}\:\mathrm{5}\right) \\ $$$${x}\:\equiv\:\mathrm{1}\:\left(\mathrm{mod}\:\mathrm{7}\right) \\ $$$${a}_{\mathrm{1}} \:=\:{a}_{\mathrm{2}} \:=\:{a}_{\mathrm{3}} \:=\:\mathrm{1} \\ $$$${m}_{\mathrm{1}} \:=\:\mathrm{3},\:{m}_{\mathrm{2}} \:=\:\mathrm{5},\:{m}_{\mathrm{3}} \:=\:\mathrm{7} \\ $$$$\Rightarrow\:{m}\:=\:{m}_{\mathrm{1}} {m}_{\mathrm{2}} {m}_{\mathrm{3}} \:=\:\mathrm{105} \\ $$$$\Rightarrow\:{M}_{\mathrm{1}} \:=\:\frac{{m}}{{m}_{\mathrm{1}} }\:=\:\mathrm{35},\:{M}_{\mathrm{2}} \:=\:=\:\frac{{m}}{{m}_{\mathrm{2}} }\:=\:\mathrm{21},\:{M}_{\mathrm{3}} \:=\:\frac{{m}}{{m}_{\mathrm{3}} }\:=\:\mathrm{15} \\ $$$$ \\ $$$$\mathrm{Now}\:\mathrm{find}\:{y}_{{k}} \:\mathrm{such}\:\mathrm{that}\:{M}_{{k}} {y}_{{k}} \:\equiv\:\mathrm{1}\:\left(\mathrm{mod}\:{m}_{{k}} \right) \\ $$$$\Rightarrow\:{y}_{\mathrm{1}} \:=\:\mathrm{2},\:{y}_{\mathrm{2}} \:=\:\mathrm{1},\:{y}_{\mathrm{3}} \:=\:\mathrm{1} \\ $$$$ \\ $$$${y}\:=\:{a}_{\mathrm{1}} {M}_{\mathrm{1}} {y}_{\mathrm{1}} \:+\:{a}_{\mathrm{2}} {M}_{\mathrm{2}} {y}_{\mathrm{2}} \:+\:{a}_{\mathrm{3}} {M}_{\mathrm{3}} {y}_{\mathrm{3}} \\ $$$$\:\:\:\:=\:\mathrm{70}\:+\:\mathrm{21}\:+\:\mathrm{15}\:=\:\mathrm{106} \\ $$$${x}\:=\:{y}\:\mathrm{mod}\:{m}\:=\:\mathrm{106}\:\mathrm{mod}\:\mathrm{105}\:=\:\mathrm{1} \\ $$$$\mathrm{In}\:\mathrm{general},\:{x}\:=\:\mathrm{105}{k}\:+\:\mathrm{1},\:{k}\:=\:\mathrm{0},\mathrm{1},\mathrm{2},… \\ $$
Commented by Mr.Panoply last updated on 19/Apr/20
Thank you... so much
$${Thank}\:{you}…\:{so}\:{much} \\ $$

Pin

Leave a Reply

Your email address will not be published. Required fields are marked *