Menu Close

Question-198785

Tinku Tara 0 Comments
Pin




Question Number 198785 by sonukgindia last updated on 24/Oct/23
Answered by AST last updated on 24/Oct/23
(1/(197))≡x(mod 3000)⇒197x≡1(mod 3000) 197x≡1(mod 3)⇒−x≡^3 1⇒x≡^3 2 197x≡1(mod 8)⇒5x≡1(mod 8)⇒x≡^8 5 197x≡1(mod 125)⇒72x≡1(mod 125) ⇒−53x≡1(mod 125)⇒[3x≡^(25) −1⇒x≡^(25) 8] 53x≡^(125) 124+125×13⇒x≡33(mod 125) x=3k+2;x=8q+5⇒8q+5≡2(mod 3) ⇒q≡0(mod 3)⇒x=24v+5≡33(mod 125) ⇒24v≡28(mod 125)⇒6v≡^(125) 7⇒v≡22(mod 125) ⇒x=24(125y+22)+5⇒x≡24×22+5=533 ⇒x≡533(mod 3000)
$$\frac{\mathrm{1}}{\mathrm{197}}\equiv{x}\left({mod}\:\mathrm{3000}\right)\Rightarrow\mathrm{197}{x}\equiv\mathrm{1}\left({mod}\:\mathrm{3000}\right) \\ $$$$\mathrm{197}{x}\equiv\mathrm{1}\left({mod}\:\mathrm{3}\right)\Rightarrow−{x}\overset{\mathrm{3}} {\equiv}\mathrm{1}\Rightarrow{x}\overset{\mathrm{3}} {\equiv}\mathrm{2} \\ $$$$\mathrm{197}{x}\equiv\mathrm{1}\left({mod}\:\mathrm{8}\right)\Rightarrow\mathrm{5}{x}\equiv\mathrm{1}\left({mod}\:\mathrm{8}\right)\Rightarrow{x}\overset{\mathrm{8}} {\equiv}\mathrm{5} \\ $$$$\mathrm{197}{x}\equiv\mathrm{1}\left({mod}\:\mathrm{125}\right)\Rightarrow\mathrm{72}{x}\equiv\mathrm{1}\left({mod}\:\mathrm{125}\right) \\ $$$$\Rightarrow−\mathrm{53}{x}\equiv\mathrm{1}\left({mod}\:\mathrm{125}\right)\Rightarrow\left[\mathrm{3}{x}\overset{\mathrm{25}} {\equiv}−\mathrm{1}\Rightarrow{x}\overset{\mathrm{25}} {\equiv}\mathrm{8}\right] \\ $$$$\mathrm{53}{x}\overset{\mathrm{125}} {\equiv}\mathrm{124}+\mathrm{125}×\mathrm{13}\Rightarrow{x}\equiv\mathrm{33}\left({mod}\:\mathrm{125}\right) \\ $$$${x}=\mathrm{3}{k}+\mathrm{2};{x}=\mathrm{8}{q}+\mathrm{5}\Rightarrow\mathrm{8}{q}+\mathrm{5}\equiv\mathrm{2}\left({mod}\:\mathrm{3}\right) \\ $$$$\Rightarrow{q}\equiv\mathrm{0}\left({mod}\:\mathrm{3}\right)\Rightarrow{x}=\mathrm{24}{v}+\mathrm{5}\equiv\mathrm{33}\left({mod}\:\mathrm{125}\right) \\ $$$$\Rightarrow\mathrm{24}{v}\equiv\mathrm{28}\left({mod}\:\mathrm{125}\right)\Rightarrow\mathrm{6}{v}\overset{\mathrm{125}} {\equiv}\mathrm{7}\Rightarrow{v}\equiv\mathrm{22}\left({mod}\:\mathrm{125}\right) \\ $$$$\Rightarrow{x}=\mathrm{24}\left(\mathrm{125}{y}+\mathrm{22}\right)+\mathrm{5}\Rightarrow{x}\equiv\mathrm{24}×\mathrm{22}+\mathrm{5}=\mathrm{533} \\ $$$$\Rightarrow{x}\equiv\mathrm{533}\left({mod}\:\mathrm{3000}\right) \\ $$
Commented by qaz last updated on 24/Oct/23
197x≡1(mod 3000) ⇒197x+3000a=1 ⇒3000a=45a≡1(mod 197) ⇒45a+197b=1 ⇒197b=17b≡1(mod 45) ⇒17b+45c=1 ⇒45c=11c≡1(mod 17) ⇒11c+17d=1 ⇒17d≡6d≡1(mod 11) ⇒d≡2(mod 11) ⇒c≡−3(mod 17) ⇒ b≡8(mod 45) ⇒a≡−35(mod 197) ⇒x≡533(mod 3000)
$$\mathrm{197}{x}\equiv\mathrm{1}\left({mod}\:\mathrm{3000}\right) \\ $$$$\Rightarrow\mathrm{197}{x}+\mathrm{3000}{a}=\mathrm{1}\:\:\:\Rightarrow\mathrm{3000}{a}=\mathrm{45}{a}\equiv\mathrm{1}\left({mod}\:\mathrm{197}\right) \\ $$$$\Rightarrow\mathrm{45}{a}+\mathrm{197}{b}=\mathrm{1}\:\:\:\:\:\:\:\:\:\:\Rightarrow\mathrm{197}{b}=\mathrm{17}{b}\equiv\mathrm{1}\left({mod}\:\mathrm{45}\right) \\ $$$$\Rightarrow\mathrm{17}{b}+\mathrm{45}{c}=\mathrm{1}\:\:\:\:\:\:\:\:\:\:\:\:\:\Rightarrow\mathrm{45}{c}=\mathrm{11}{c}\equiv\mathrm{1}\left({mod}\:\mathrm{17}\right) \\ $$$$\Rightarrow\mathrm{11}{c}+\mathrm{17}{d}=\mathrm{1}\:\:\:\:\:\:\:\:\:\:\:\:\Rightarrow\mathrm{17}{d}\equiv\mathrm{6}{d}\equiv\mathrm{1}\left({mod}\:\mathrm{11}\right) \\ $$$$\Rightarrow{d}\equiv\mathrm{2}\left({mod}\:\mathrm{11}\right) \\ $$$$\Rightarrow{c}\equiv−\mathrm{3}\left({mod}\:\mathrm{17}\right)\:\Rightarrow\:\:{b}\equiv\mathrm{8}\left({mod}\:\mathrm{45}\right)\:\:\:\Rightarrow{a}\equiv−\mathrm{35}\left({mod}\:\mathrm{197}\right)\:\:\:\Rightarrow{x}\equiv\mathrm{533}\left({mod}\:\mathrm{3000}\right) \\ $$
Answered by AST last updated on 24/Oct/23
2. n^5 ≡155^(777^(888) ) ≡(−9)^(777^(888) ) ≡^(41) −(9)^(777^(888) ) 777^(888) ≡(17)^(888) (mod 40) 17^(888) =17^(16(55)+8) ≡7^8 (mod 40)≡9^4 =81=1(mod 40) ⇒−(9)^(777^(888) ) =−(9)^(40q+1) ≡−(9)^(40q) 8≡−9(mod 41) ⇒n^5 ≡32(mod 41)⇒n≡2(mod 41)
$$\mathrm{2}.\:{n}^{\mathrm{5}} \equiv\mathrm{155}^{\mathrm{777}^{\mathrm{888}} } \equiv\left(−\mathrm{9}\right)^{\mathrm{777}^{\mathrm{888}} } \:\overset{\mathrm{41}} {\equiv}−\left(\mathrm{9}\right)^{\mathrm{777}^{\mathrm{888}} } \\ $$$$\mathrm{777}^{\mathrm{888}} \equiv\left(\mathrm{17}\right)^{\mathrm{888}} \left({mod}\:\mathrm{40}\right) \\ $$$$\mathrm{17}^{\mathrm{888}} =\mathrm{17}^{\mathrm{16}\left(\mathrm{55}\right)+\mathrm{8}} \equiv\mathrm{7}^{\mathrm{8}} \left({mod}\:\mathrm{40}\right)\equiv\mathrm{9}^{\mathrm{4}} =\mathrm{81}=\mathrm{1}\left({mod}\:\mathrm{40}\right) \\ $$$$\Rightarrow−\left(\mathrm{9}\right)^{\mathrm{777}^{\mathrm{888}} } =−\left(\mathrm{9}\right)^{\mathrm{40}{q}+\mathrm{1}} \equiv−\left(\mathrm{9}\right)^{\mathrm{40}{q}} \mathrm{8}\equiv−\mathrm{9}\left({mod}\:\mathrm{41}\right) \\ $$$$\Rightarrow{n}^{\mathrm{5}} \equiv\mathrm{32}\left({mod}\:\mathrm{41}\right)\Rightarrow{n}\equiv\mathrm{2}\left({mod}\:\mathrm{41}\right) \\ $$
Answered by AST last updated on 24/Oct/23
3. n^5 ≡6^k (mod 41)⇒6^(5q) ≡6^k (mod 41) 6^(5q−k) ≡6^(40) (mod 41)⇒5q≡k(mod 40) ⇒k≡5q(mod 40)⇒k≡5q(mod 41) where 5q≤40 ⇒x≡6^0 ,6^5 ,6^(10) ,6^(15) ,6^(20) ,6^(25) ,6^(30) ,6^(35) x∈{[1],[3],[9],[14],[27],[32],[38]}
$$\mathrm{3}.\:{n}^{\mathrm{5}} \equiv\mathrm{6}^{{k}} \left({mod}\:\mathrm{41}\right)\Rightarrow\mathrm{6}^{\mathrm{5}{q}} \equiv\mathrm{6}^{{k}} \left({mod}\:\mathrm{41}\right) \\ $$$$\mathrm{6}^{\mathrm{5}{q}−{k}} \equiv\mathrm{6}^{\mathrm{40}} \left({mod}\:\mathrm{41}\right)\Rightarrow\mathrm{5}{q}\equiv{k}\left({mod}\:\mathrm{40}\right) \\ $$$$\Rightarrow{k}\equiv\mathrm{5}{q}\left({mod}\:\mathrm{40}\right)\Rightarrow{k}\equiv\mathrm{5}{q}\left({mod}\:\mathrm{41}\right)\:{where}\:\mathrm{5}{q}\leqslant\mathrm{40} \\ $$$$\Rightarrow{x}\equiv\mathrm{6}^{\mathrm{0}} ,\mathrm{6}^{\mathrm{5}} ,\mathrm{6}^{\mathrm{10}} ,\mathrm{6}^{\mathrm{15}} ,\mathrm{6}^{\mathrm{20}} ,\mathrm{6}^{\mathrm{25}} ,\mathrm{6}^{\mathrm{30}} ,\mathrm{6}^{\mathrm{35}} \\ $$$${x}\in\left\{\left[\mathrm{1}\right],\left[\mathrm{3}\right],\left[\mathrm{9}\right],\left[\mathrm{14}\right],\left[\mathrm{27}\right],\left[\mathrm{32}\right],\left[\mathrm{38}\right]\right\} \\ $$

Pin

Leave a Reply

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