Question Number 203566 by BaliramKumar last updated on 22/Jan/24
$$'\mathrm{P}'\:\mathrm{is}\:\mathrm{a}\:\mathrm{prime}\:\mathrm{number}\:\left(\mathrm{P}>\mathrm{1000}\right).\: \\ $$$$\mathrm{If}\:\:\:\mathrm{P}\:\equiv\:\mathrm{r}\:\left(\mathrm{mod}\:\mathrm{1000}\right).\:\mathrm{how}\:\mathrm{many}\:\mathrm{value}\:\mathrm{of}\:'\mathrm{r}'. \\ $$
Answered by MM42 last updated on 22/Jan/24
$${p}=\mathrm{1000}{k}+{r}\:\:\&\:\:\mathrm{0}<{r}<\mathrm{1000}\: \\ $$$$\Rightarrow“{p}''\:{is}\:{prime}\:{number}\: \\ $$$$\Rightarrow“{r}''\:{must}\:{be}\:{an}\:{odd}\:{number}\:\&\:{r}\neq\mathrm{5}{k}' \\ $$$${A}=\left\{\mathrm{1},\mathrm{3},\mathrm{5},…,\mathrm{999}\right\}\Rightarrow{n}\left({A}\right)=\mathrm{500} \\ $$$${B}=\left\{\mathrm{5},\mathrm{15},…,\mathrm{995}\right\}\Rightarrow{n}\left({B}\right)=\mathrm{100} \\ $$$${ans}=\mathrm{500}−\mathrm{100}=\mathrm{400}\:\checkmark \\ $$$${for}\:{example} \\ $$$$\mathrm{3001},\:\mathrm{2003}\:,\:\mathrm{4007}\:,…,\:\mathrm{1993}\:,\mathrm{6997}\:,\mathrm{1999}\:,.. \\ $$$$ \\ $$
Commented by BaliramKumar last updated on 23/Jan/24
![Can we use Euler′s totient function? I don′t know if it′s true forever. φ(1000) = φ[(2×5)^3 ] = (2−1)(5−1)2^(3−1) ×5^(3−1) = 400](https://www.tinkutara.com/question/Q203609.png)
$$\mathrm{Can}\:\mathrm{we}\:\mathrm{use}\:\mathrm{Euler}'\mathrm{s}\:\mathrm{totient}\:\mathrm{function}? \\ $$$$\mathrm{I}\:\mathrm{don}'\mathrm{t}\:\mathrm{know}\:\mathrm{if}\:\:\mathrm{it}'\mathrm{s}\:\mathrm{true}\:\mathrm{forever}. \\ $$$$\phi\left(\mathrm{1000}\right)\:=\:\phi\left[\left(\mathrm{2}×\mathrm{5}\right)^{\mathrm{3}} \right]\:=\:\left(\mathrm{2}−\mathrm{1}\right)\left(\mathrm{5}−\mathrm{1}\right)\mathrm{2}^{\mathrm{3}−\mathrm{1}} ×\mathrm{5}^{\mathrm{3}−\mathrm{1}} \:=\:\mathrm{400} \\ $$
Commented by MM42 last updated on 23/Jan/24
$${I}\:{don}'{t}\:{khow} \\ $$