Question and Answers Forum

All Questions      Topic List

None Questions

Previous in All Question      Next in All Question      

Previous in None      Next in None      

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} \\ $$

Terms of Service

Privacy Policy

Contact: info@tinkutara.com